冒泡排序

构思

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

约定

接口

对于冒泡排序的实现，我们实现如下接口：

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个元素归位。

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

代码实现

#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       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进行一次判断，即可确定算法是否应该提前终止。

代码实现

//冒泡排序部分
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)这段有序区间。

代码实现

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)