信息学奥赛-入门级 题库
某同学用冒泡排序对数组{6,1,5,2,4}进行升序排序,请问需要进行多少次元素交换?()
冒泡排序过程如下(数组初始:{6,1,5,2,4}):
第一趟:交换4次,数组变为{1,5,2,4,6}。
第二趟:交换2次,数组变为{1,2,4,5,6}。
第三趟及以后:无交换。
总交换次数为6。
冒泡排序算法的伪代码如卜:
输入:数组L, n ≥ 1。输出:按非递减顺序排序的L
算法 BubbleSort:
1. FLAG ← n //标记被交换的最后元素位置
2. while FLAG > 1 do
3. k ← FLAG -1
4. FLAG ← 1
5. for j=1 to k do
6. if L(j) > L(j+1) then do
7. L(j) ↔ L(j+1)
8. FLAG ← j
对n个数用以上冒泡排抒算法进行排序 最少需要比较多少次?()。
考察冒泡排序的时间复杂度 。题目要求的是最少时间,我们可以发现,当数组本身是有序的时候,flag的值会一直是1,不会改变,所以j是从1到n-1,一共比较了n-1次,所以选D。
使用冒泡排序对序列进行升序排序,列每执行一次交换操作将会减少1个逆序对, 因此序5, 4, 3, 2, 1
需要执行( )次交换操作,才能完成冒泡排序。
15
冒泡排序算法的伪代码如卜:
输入:数组L, n ≥ 1。输出:按非递减顺序排序的L
算法 BubbleSort:
1. FLAG ← n //标记被交换的最后元素位置
2. while FLAG > 1 do
3. k ← FLAG -1
4. FLAG ← 1
5. for j=1 to k do
6. if L(j) > L(j+1) then do
7. L(j) ↔ L(j+1)
8. FLAG ← j
对n个数用以上冒泡排抒算法进行排序 最少需要比较多少次?()。
考察冒泡排序的时间复杂度 。题目要求的是最少时间,我们可以发现,当数组本身是有序的时候,flag的值会一直是1,不会改变,所以j是从1到n-1,一共比较了n-1次,所以选D。