enter image description here

讲解

与插入排序法一样,冒泡排序法的各个计算步骤中,数组也分成“已排序部分”和“未排序部分”。

enter image description here

在上述冒泡排序的算法中,数据从数组开头逐一完成排序。也就是说,步骤1 到步骤4 的处理结束后,数据中最小的元素将移动至数组开头的A[0] 位置。同理,步骤5 到步骤7 结束后,数据中第二小的元素会移动至A1,然后步骤8 到步骤9 确定A2,步骤10 确定A3,以此类推,逐一确定已排序部分末尾要追加的元素。

从例子中很容易能看出,程序每完成一次外层循环,已排序部分就增加一个元素。这样一来,程序外层循环最多需执行N 次,同时内层循环的处理范围也会逐渐减小。因此,我们可以发挥外层循环变量i 的作用,对冒泡排序的算法作如Program 3.1 所示的修改。

Program 3.1 冒泡排序法的实现

1 bubbleSort()

2 flag = 1

3 i = 0 // 未排序部分的起始下标

4 while flag

5 flag = 0

6 for j 从N-1 到 i+1

7 if A[j] < A[j-1]

8 A[j] 与A[j-1] 交换

9 flag = 1

10 i++

实现该冒泡排序法时需要的主要变量如图3.5 所示。

enter image description here

考察

冒泡排序法仅对数组中的相邻元素进行比较和交换,因此键相同的元素不会改变顺序。所以冒泡排序法也属于一种稳定排序的算法。但要注意的是,一旦将比较运算A[j] < A[j-1] 改为A[j] ≤ A[j-1],算法就会失去稳定性。

然后我们考虑一下冒泡排序法的复杂度。假设数据总量为N,冒泡排序法需对未排序部分的相邻元素进行(N-1)+(N-2)+…+1=(N²-N)/2 次比较。也就是说,冒泡排序法在最坏的情况下需要进行(N²-N)/2 次比较运算,算法复杂度数量级为O(N²)。

顺便一提,冒泡排序法中的交换次数又称为反序数或逆序数,可用于体现数列的错乱程度。

参考答案

enter image description here

评论

推荐 0
冒泡排序

我要评论

需要登录后才能发言
登录未成功,请修改提交。