对由n个元素所组成的序列按排序码排序时，下列各常用排序算法的排序码平均比较次数分别是：二路归并排序为______，冒泡排序为______，快速排序为______。其中，归并排序和快速排序所需要的辅助存储分别是______和______。
A: O(1)
B: O(nlog2n)
C: O(n)
D: O(n2)
E: O(n(log2n)2)
F: O(log2n)
A: O(1)
B: O(nlog2n)
C: O(n)
D: O(n2)
E: O(n(log2n)2)
F: O(log2n)
B
举一反三
- 快速排序在最坏情况下的时间复杂度是（ ），此时其退化成了（ ）。 A: O(n^2)，冒泡排序 B: O(n^2)，简单选择排序 C: O(n*log2(n))，冒泡排序 D: O(n*log2(n))，归并排序
- 快速排序的平均时间复杂度为（）？ A: O(n) B: O(nlog(n)) C: O(log(n)) D: O(n^2)
- 对n个记录文件进行快速排序，平均比较次数为______。 A: O(nlog<sub>2</sub>n) B: O(n<sup>2</sup>) C: O(log<sub>2</sub>n) D: O(n)
- 对n个记录文件进行快速排序，平均比较次数为______。 A: O(nlog2n) B: O(n2) C: O(log2n) D: O(n)
- 对n个记录文件进行快速排序，平均比较次数为______。 A: O(nlog2n) B: O(n2) C: O(log2n) D: O(n)
内容
- 0
快速排序的空间复杂度为（ ）。 A: O(log2n) B: O(n^3) C: O(n^2) D: O(n)
- 1
快速排序的空间复杂度为（ ）。 A: O(n^2) B: O(log2n) C: O(n) D: O(n^3)
- 2
在内部排序中，通常要对被排序数据序列进行多趟扫描。各种排序方法有其不同的排序实施过程和(时间)复杂性。对给定的整数序列(541，132，984，746，518，181，946，314，205，827)进行从小到大的排序时，采用冒泡排序的第一趟扫描结果是 (61) 。设被排序数据序列有n个元素，冒泡排序算法的复杂性是 (62) 。 A: O(nlog<sub>2</sub>n) B: O(n<sup>2</sup>) C: O(log<sub>2</sub>n)<sup>2</sup> D: O(n<sup>2</sup>log<sub>2</sub>n)
- 3
冒泡排序算法的时间复杂度为()。 A: O(n) B: O(log<br/>n) C: O(n^2) D: O(nlogn)
- 4
当所有n个待排序记录的排序码都相等时，直接插入排序、堆排序、起泡排序、简单选择排序的排序码比较次数和元素移动次数分别为(①)、O(n)和O(n)、n-1和0、n(n-1)/2和0。 A: n-1和0 B: n(n-1)/2和n C: n(n-1)/2和0 D: O(n)和O(n)