扩展阅读:冒泡排序
局部有序和整体有序
对于一个由整数组成的序列A[0,n)
,任何相邻的两个数,都满足A[i - 1] <= A[i]
(前一项小于后一项)我们称为顺序的,那么也就是说,一个有序序列的任何相邻数对,都是顺序的。反之,对于一个局部存在逆序对的序列来说,一定不是有序的。
那么我们是不是可以通过不断改善一个无序序列相邻逆序对的顺序,可以使这个序列有序呢?
扫描交换
在用j
和j+1
标记的一对数中,通过扫描是否属于逆序关系,如果后一项小于前一项,就交换它们。
虽然经过这样一趟扫描,序列未必达到整体有序,但有最大的一个元素必然就位。
通过这样反复的扫描,多次交换后,所有元素都回到了自己的位置。
// 冒泡排序
void bubbleSortA(int a[], int n) {
for(int i = 0; i < n; i++)
for (int j = 0; j < n-i-1; j++) {
if (a[j+1] < a[j])
swap(a[j+1], a[i]);
}
}
这个思路的实现只用了几行代码,真正让人困惑的,可能就是这里的j
范围的界定,为什么j < n-i-1
。
通过不断蚕食待排序的部分,使整个序列有序。
排序过程中,虽有元素朝着各自最终位置亦步亦趋的移动,这个过程可以形象的视为冒泡。
对于这样一个长度为n的序列,每经过1轮扫描后,最大的1个元素必然就位,由此我们可以得出,
扫描交换的时间线性正比于无序部分的规模,整体呈现出算术级数的形式,所以它的时间复杂度与末项成平方关系。
冒泡排序改进
这样的算法是否真的可以满足我们在各种情况下的需求呢?
可以设想一个这样的序列,部分元素已经就位,但是待排序的部分未必是无序的。

对于这样一个序列,如果采用我们一开始的算法,就会在序列整体有序后,多余的继续扫描序列。
换句话说,我们对于相邻两个元素的检查,可能在不久的过去已经做过了,它们是有序的,但我们还是机械的一趟一趟扫描这些序列,就只是为了我们认为的所有元素归位。
改进的策略是,我们在扫描时,不妨记录一下,是否真的存在逆序对,如果不存在,那么这个序列局部处处有序,整体必然是有序的,我们可以提前终止程序了。
现在的问题是,如何判断存在或不存在逆序对,或者说,什么是存在逆序对的条件?这个问题的答案是不言而喻的,就是在这一趟扫描中,曾经是否交换过一对元素。
// 冒泡排序改进
void bubbleSortB(int a[], int n) {
bool sorted = false; // 定义全局顺序标志,首先认为尚未排序
while (!sorted) { // 尚未确定是否排序前,先逐躺扫描
sorted = true; // 无罪推论,假定全局顺序
for (int i = 1; i < n; i++)
if (a[i] < a[i - 1]) { // 发现逆序对,
sorted = false; // 发现罪证,清除全局顺序标志
swap(a[i], a[i - 1]); // 交换,使得局部顺序
}
n--; // 部分元素归位,缩小待排序序列的规模
}
}
冒泡排序再改进
这样的算法是否就可以应对所有的场景呢?
由于篇幅原因,这里直接给出改进的代码和思路。通过增加last
来标记扫描的边界,对于超出边界的元素,是否值得扫描呢,留给各位自己思考。
// 冒泡排序再改进
void bubbleSortC(int a[],int n){
bool sorted = false; // 定义全局顺序标志,首先认为尚未排序
while (!sorted) { // 尚未确定是否排序前,先逐躺扫描
sorted = true; // 无罪推论,假定全局顺序
int last = n;
for (int i = 1; i < n; i++)
if (a[i] < a[i - 1]) { // 发现逆序对,
sorted = false; // 发现罪证,清除全局顺序标志
swap(a[i], a[i - 1]); // 交换,使得局部顺序
last = i+1;
}
n = (last < n-1) ? last : n-1; // 部分元素归位,缩小待排序序列的规模
}
}