违法和不良信息举报 联系客服
免费注册 登录

若要求对大小为n的数组进行排序的平均时间复杂度为O（n^2）??，且是不稳定的（即如果待排序的序列中两个数据元素具有相同的值，在排序前后它们的相对位置有可能发生改变），则可选择的排序方法是（ ）

题目
若要求对大小为n的数组进行排序的平均时间复杂度为O（n^2）??，且是不稳定的（即如果待排序的序列中两个数据元素具有相同的值，在排序前后它们的相对位置有可能发生改变），则可选择的排序方法是（ ）

A.快速排序
B.归并排序
C.直接选择排序
D.冒泡排序
如果没有搜索结果或未解决您的问题，请直接 联系老师 获取答案。
相似问题和答案

第1题：

如果待排序序列中两个数据元素具有相同的值，在排序后它们的位置发生颠倒，则称该排序是不稳定的。下列不稳定的排序方法是

A．冒泡排序

B．归并排序

C．直接插入排序

D．直接选择排序


正确答案：D
解析：排序方法有很多种，在这些排序方法中，直接插入排序、冒泡排序、归并排序和基数排序是稳定的排序方法，直接选择排序、希尔排序、快速排序和堆排序是不稳定的。

第2题：

对n个元素的数组进行(63)，其平均时间复杂度和最坏情况下的时间复杂度都是O(nlogn)。

A．希尔排序

B．快速排序

C．堆排序

D．选择排序


正确答案：C
解析：本题考查排序算法。
  希尔排序的时间复杂度约为O(n1.4)。
  快速排序在最坏情况下的时间复杂度为O(n2)。
  选择排序的时间复杂度为O(n2)。
  无论在什么情况下，堆排序的时间复杂度都是O(nlogn)。

第3题：

如果待排序序列中两个元素具有相同的值，在排序前后它们的相互位置发生颠倒，则称该排序算法是不稳定的。(41)是稳定的排序方法，因为这种方法在比较相邻元

A．冒泡排序

B．希尔排序

C．快速排序

D．简单选择排序


正确答案：A
解析：本题考查排序算法。冒泡排序的思想是比较相邻的元素，将较大者交换到后面，对于值相同的元素，则无需交换。希尔排序则是按照一定的间隔将元素分成若干组，在同组内进行直接插入排序，这样较小的元素以较大的步幅向前移动。但是在希尔排序中，值相同的元素不一定分在同一组，因此，在排序前后它们的相互位置可能发生颠倒。快速排序是先设定一个枢轴元素(基准元素，通常是序列的第一个元素)，从序列的两端开始扫描，将大于枢轴元素的元素向序列后端换，小于枢轴元素者向序列前端换。在此过程中，值相同的元素会交换位置，因此快速排序不是稳定的排序方法。n个元素进行简单选择排序的基本方法是：通过n-i次元素之间的比较，从n-i+1个元素中选出最小元素，并与第i(1≤I≤n)个元素进行交换，当i等于n时所有记录有序排列。简单选择排序是一种不稳定的排序方法。

第4题：

● 如果待排序序列中两个元素具有相同的值，在排序前后它们的相互位置发生颠倒，则称该排序算法是不稳定的。 （41） 是稳定的排序方法，因为这种方法在比较相邻元素时，值相同的元素并不进行交换。

（41）

A. 冒泡排序

B. 希尔排序

C. 快速排序

D. 简单选择排序


正确答案：A

第5题：

直接选择排序的平均时间复杂度为(17)。最好情况下时间复杂度为O(n)的排序算法是(18)。在最好和最花情况下的时间复杂度均为O(nlogn)且稳定的排序方法是(19)。

A．O(n)

B．O(nlogn)

C．O(n2)

D．O(logn)


正确答案：C

第6题：

如果在待排序序列中有两个元素具有相同的值，排序使它们的位置发生颠倒，则称该排序算法是不稳定的，下列哪种排序算法是不稳定的? ( )

A．堆排序

B．归并排序

C．基数排序

D．起泡排序


正确答案：A
解析：一般来说，排序过程中比较是在相邻两个记录之间进行的排序方法是稳定的，快速排序、堆排序和希尔排序等属于不稳定的排序。

第7题：

假设要排序包含n个元素的数组，请给出在各种不同的划分情况下，快速排序的时间复杂度(用 O记号)。最佳情况为(4)，平均情况为(5)，最坏情况为(6)。

(2)假设要排序的n个元素都具有相同值时，快速排序的运行时间复杂度属于哪种情况? (7)。 (最佳、平均、最坏)


正确答案：这是一道考查快速排序算法时间复杂度的分析题。当每次能作均匀划分时算法为最佳情况此时时间复杂度可以通过计算递归式T(n)=2T(n/2)+O(n)得到时间复杂度为O(nlogn)。当每次为极端不均匀划分时即长度为n的数组划分后一个子数组为n-1一个为0算法为最坏情况此时时间复杂度可以通过计算递归式T(n)=T(n-1)+O(n)得到时间复杂度为O(n2)。 对于平均情况的分析较为复杂假设数组每次划分为9/10：1/10此时时间复杂度可以通过计算递归式 T(n)=T(9/10)+T(1/10)+O(n)得到时间复杂度为O(nlogn)因此在平均情况下快速排序仍然有较好的性能时间复杂度为O(nlogn)。 当所有的n个元素具有相同的值时可以认为数组已经有序此时每次都划分为长度为n-1和0的两个子数组属于最坏情况。
这是一道考查快速排序算法时间复杂度的分析题。当每次能作均匀划分时，算法为最佳情况，此时时间复杂度可以通过计算递归式T(n)=2T(n/2)+O(n)，得到时间复杂度为O(nlogn)。当每次为极端不均匀划分时，即长度为n的数组划分后一个子数组为n-1，一个为0，算法为最坏情况，此时时间复杂度可以通过计算递归式T(n)=T(n-1)+O(n)，得到时间复杂度为O(n2)。 对于平均情况的分析较为复杂，假设数组每次划分为9/10：1/10，此时时间复杂度可以通过计算递归式 T(n)=T(9/10)+T(1/10)+O(n)，得到时间复杂度为O(nlogn)，因此在平均情况下快速排序仍然有较好的性能，时间复杂度为O(nlogn)。 当所有的n个元素具有相同的值时，可以认为数组已经有序，此时每次都划分为长度为n-1和0的两个子数组，属于最坏情况。

第8题：

对n个元素的数组进行()，其平均时间复杂度和最坏情况下都为O(nlogn)。

A.希尔排序

B.快速排序

C.堆排序

D.选择排序


正确答案：C

第9题：

若要求对大小为n的数组进行排序的时间复杂度为O(nlog2n)，且是稳定的（即如果待排序的序列中两个数据元素具有相同的值，在排序前后它们的相对位置不变），则可选择的排序方法是（ ）。

A.快速排序 B.归并排序 C.堆排序 D.冒泡排序


正确答案：B

第10题：

快速排序算法是，在排序过程中，在待排序数组中确定一个元素为基准元素，根据基准元素把待排序数组划分成两个部分，前面一部分元素值小于基准元素，而后面一部分元素值大于基准元素。然后再分别对前后两个部分进一步进行划分。根据上述描述，快速排序算法采用了 （ ） 算法设计策略。已知确定着基准元素操作的时间复杂度为O(n)，则快速排序算法的最好和最坏情况下的时间复杂度为 （请作答此空） 。

A.O(n)和O(nlgn)
B.O(n)和O(n2)
C.O(nlgn)和O(nlgn)
D.O(nlgn)和O(n2)

答案：D
解析：
将数据分成若干份，每份单独处理后再合并，其思想为分治。
理想情况下，快速排序每次将数据划分为规模相近的两部分，并递归至不可再划分，因此其时间复杂度为O(nlgn)。在最坏情况下，每次划分都极不均匀，如一个类别中仅有一个元素，另一个类别中包含剩余所有元素。这时划分的复杂度为O(n)，次操作的总复杂度为O(n2)。

更多相关问题
相关内容