题目内容
(请给出正确答案)
[单选题]
对n个元素进行冒泡排序,第一趟共要比较()对元素。
A.n-1
B.n/2
C.n+1
D.n
答案
查看答案
A.n-1
B.n/2
C.n+1
D.n
第2题
下列排序算法中,()排序在某趟结束后不一定选出一个元素放到其最终的位置上。
A.选择
B.冒泡
C.归并
D.堆
第4题
a)试按照以上思路,实现一个排序算法:
b)你的这一算法,时间和空间复杂度各是多少?
c)改进你的算法,使之能够在O(n+M)时间内对来自[0,M)范围内的n个整数进行排序,且使用的辅助空间不超过O(M)。
第5题
第9题
下列排序方法中,属于不稳定的排序方法是()。
A.直接插入排序法
B.冒泡排序法
C.基数排序法
D.堆排序法
第10题
序列中元素A[i]和A[j]若满足i<j且A[i]>A[j],则称之为一个逆序对(inversion)。考查如教材80页代码3.19所示的插入排序算法List::insertionSort(),试证明:
a)若所有逆序对的间距均不超过k,则运行时间为o(kn);
b)特别地,当k为常数时,插入排序可在线性时间内完成;
c)若共有I个逆序对,则关键码比较的次数不超过o(I);
d)若共有I个逆序对,则运行时间为o(n+I)。
第11题