余睿的博客

浮生若梦,别多会少,不如莫遇

0%

冒泡排序

构思

  • 问题:给定任意一个数组,内含n个可比较的元素,将它们按升序排列。
  • 观察:在该数组中,对于任意两个相邻的元素,其关系总为顺序/逆序。
  • 扫描交换:依次比较每一对相邻的元素,如有必要,将其交换

约定

接口

对于冒泡排序的实现,我们实现如下接口:

1
void bubbleSort(int *a,int lo,int hi);

其中,a为待排序数组,lo为排序的区间起点,hi为排序区间的终点。需要注意的是,待排序区间为一个左闭右开区间,数学表示为[lo,hi)

综上,对于上面的接口,其语义为:将数组a[lo,hi)区间进行降序排序。

图示

在问中的示意图中,蓝色单向箭头表示当前待比较的两个元素,橙色双向箭头表示交换两个位置的数据。

实现一

原理

一遍冒泡排序示意图

假设对上图的序列进行排序,我们始终将注意力放在当前位置以及其后的紧邻位置上的两个元素(如上 a 所示)。一旦这两个元素逆序,我们交换其位置(如上图 b、d、e 所示),然后移动到下一个位置(如上图 b 所示),最终抵达hi-2的位置结束一次迭代。

每一轮迭代结束,当前乱序的序列中的最大者必然会归位(如上图 f 所示),所以在下一轮迭代中,我们只需要比较到hi-2-i的位置即可结束。即:在前i轮的迭代中,必然会使得最大的i个元素归位。

下图展示了上述序列排序的完整过程:

冒泡排序示意图

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<iostream>
using namespace std;
//冒泡排序部分
void bubbleSort(int *a, int lo, int hi) {
for(int i=lo;i<hi;i++){
for (int j = lo; j < hi - 1 - i; j++) {
if (a[j] > a[j + 1]) {
swap(a[j], a[j + 1]);
}
}
}
}
//输出数组内容
void print(int* a,int lo,int hi) {
for (int i = lo; i < hi; i++) {
cout << a[i] << "\t";
}
cout << endl;
}

int main() {
int a[10] = { 1,4,2,7,8,3,6,5,9,0 };
print(a, 0, 10);
bubbleSort(a, 0, 10);
print(a, 0, 10);
return 0;
}

运行上面的程序,输入如下:

1
2
1       4       2       7       8       3       6       5       9       0
0 1 2 3 4 5 6 7 8 9

正确性

假设对于规模为n的输入数据,在经过k趟扫描后,最大的k个元素必然就位,从而问题的规模缩减为n-k,最多经过n趟扫描,算法必然终止。

改进(提前终止)

原理

考察一个如下图所示的序列:

单趟扫描示意图

在上图所示的序列中,除了6以外的数组都是有序的,我们在第一趟扫描过程中即可将6就位(如上图 f 所示)。

不幸的是,依照我们此前的做法,我们任需要进行六次扫描才能终止算法(尽管在第一趟扫描结束后该序列就已经有序),多出来的五次扫描是完全没有必要的。如下图所示:

冒泡排序示意图

依照上面的描述,我们可以引入一个有序标志sorted,并将其值设为true。一旦发生交换,将sorted的值置为false,表示当前的序列并不是有序的,这样在每趟扫描结束时对sorted进行一次判断,即可确定算法是否应该提前终止。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
//冒泡排序部分
void bubbleSort(int* a, int lo, int hi) {
bool sorted = false;//初始化标志
for (int i = lo; (i < hi) && (!sorted); i++) {
sorted = true;//设初值
for (int j = lo; j < hi - 1 - i; j++) {
if (a[j] > a[j + 1]) {
swap(a[j], a[j + 1]);
sorted = false;//发生交换,未有序
}//else...有序,提前终止
}
}
}

改进(跳跃)

原理

再考察下面这样一个序列:

冒泡排序一遍扫描示意图

6就位后,尽管[0,6)未必有序,但是对于后缀[3,6)却是有序的,此时我们完全可以让hi=3,从而缩减问题的规模。如下图所示:

跳跃示意图

我们使用last来表示最后发生交换的位置,在下一轮的循环中,即可让hi=last,这样就可以直接跳跃[last,hi)这段有序区间。

代码实现

1
2
3
4
5
6
7
8
9
10
void bubbleSort(int* a, int lo, int hi) {
for (int last = --hi; lo < hi; hi = last) {
for (int i = last = lo; i < hi; i++) {
if (a[i] > a[i + 1]) {
swap(a[i], a[i + 1]);
last = i;
}
}
}
}

综合评价

  • 效率:最好时间复杂度O(n),最差O(n^2)

欢迎关注我的其它发布渠道