工学
填空题在插入和选择排序中，若初始数据基本正序，则应选用（）排序算法；若初始数据基本反序，则应选用（）排序算法。
题目
参考答案和解析
相似问题和答案
第1题：
下面排序算法中，初始数据集的排列顺序对算法的性能无影响的是()
A.堆排序
B.插入排序
C.冒泡排序
D.快速排序
第2题：
下列排序方法中，排序所花费时间不受数据初始排列特性影响的算法是______。
A．直接插入排序
B．冒泡排序
C．直接选择排序
D．快速排序
解析：不同的方法各有优缺点，可根据需要运用到不同的场合。在选取排序算法时需要考虑以下因素：待排序的记录个数n、记录本身的大小、关键字的分布情况、对排序稳定性的要求、语言工具的条件及辅助空间的大小。依据这些因素可得以下结论：
.若待排序的记录数目n较小时，可采用插入排序和选择排序；
.若待排序记录按关键字基本有序，则宜采用直接插入排序或冒泡排序；
.当n很大且关键字的位数较少时，采用链式基数排序较好；
.若n较大，则应采用时间复杂度为O(nlogn)的排序方法——快速排序、堆排序、归并排序。
第3题：
A.直接选择排序
B.冒泡排序
C.直接插入排序
D.希尔排序
第4题：
下列排序算法中，()算法可能会出现下面情况：初始数据有序时，花费的时间反而最多。
A.堆排序
B.冒泡排序
C.快速排序
D.希尔排序
第5题：
若待排序的记录数目较少且已按关键字基本有序，则宜采用______排序算法。
A．快速排序
B．插入排序
C．选择排序
D．冒泡排序
解析：不同的排序方法各有优缺点，可根据需要运用到不同的场合。在选取排序算法时需要考虑以下因素：待排序的记录个数n、记录本身的大小、关键字的分布情况、对排序稳定性的要求、语言工具的条件及辅助空间的大小。依据这些因素可得以下结论：若待排序的记录数目n较小时，可采用插入排序和选择排序；若待排序记录按关键字基本有序，则宜采用直接插入排序或冒泡排序；当n很大且关键字的位数较少时，采用链式基数排序较好；若n较大，则应采用时间复杂度为O(nlogn)的排序方法——快速排序、堆排序、归并排序。
第6题：
下面的排序算法中，初始数据集的排列顺序对算法的性能无影响的是()
A.插入排序
B.堆排序
C.冒泡排序
D.快速排序
第7题：
A、直接插入排序
B、冒泡排序
C、快速排序
D、直接选择排序
第8题：
以下关于快速排序算法的描述中，错误的是( )。在快速排序过程中，需要设立基准元素并划分序列来进行排序。若序列由元素{12，25，30，45，52，67，85}构成，则初始排列为( )时，排序效率最高(令序列的第一个元素为基准元素)。
A．快速排序算法是不稳定的排序算法
B．快速排序算法在最坏情况下的时间复杂度为0(nlgn)
C．快速排序算法是一种分治算法
D．当输入数据基本有序时，快速排序算法具有最坏情况下的时间复杂度
解析：最坏情况是每次划分选取的基准都是当前无序区中关键字最小(或最大)的记录，划分的结果是基准左边的子区间为空(或右边的子区间为空)，而划分所得的另一个非空的子区间中记录数目，仅仅比划分前的无序区中记录个数减少一个。因此，快速排序必须做n-1次划分，第i次划分开始时区间长度为n-i+1，所需的比较次数为n-i(1≤i≤n-1)，故总的比较次数达到最大值：cmax=n(n-1)／2=O(2)在最好情况下，每次划分所取的基准都是当前无序区的“中值”记录，划分的结果是基准的左、右两个无序子区间的长度大致相等。总的关键字比较次数：O(nlgn)
第9题：
在插入和选择排序中，若初始化数据基本正序，则选用插入;若初始化数据基本反序，则选用选择。
此题为判断题(对，错)。
第10题：
下列排序算法中时间复杂度不受数据初始状态影响，恒为O(n2)的是
A、堆排序
B、起泡排序
C、直接选择排序
D、快速排序