局部有序和整体有序

对于一个由整数组成的序列A[0,n)，任何相邻的两个数，都满足A[i - 1] <= A[i]（前一项小于后一项）我们称为顺序的，那么也就是说，一个有序序列的任何相邻数对，都是顺序的。反之，对于一个局部存在逆序对的序列来说，一定不是有序的。

那么我们是不是可以通过不断改善一个无序序列相邻逆序对的顺序，可以使这个序列有序呢？

扫描交换

在用j和j+1标记的一对数中，通过扫描是否属于逆序关系，如果后一项小于前一项，就交换它们。

(相关资料图)

虽然经过这样一趟扫描，序列未必达到整体有序，但有最大的一个元素必然就位。

通过这样反复的扫描，多次交换后，所有元素都回到了自己的位置。

这个思路的实现只用了几行代码，真正让人困惑的，可能就是这里的j范围的界定，为什么j < n-i-1。

通过不断蚕食待排序的部分，使整个序列有序。

排序过程中，虽有元素朝着各自最终位置亦步亦趋的移动，这个过程可以形象的视为冒泡。

对于这样一个长度为n的序列，每经过1轮扫描后，最大的1个元素必然就位，由此我们可以得出，

扫描交换的时间线性正比于无序部分的规模，整体呈现出算术级数的形式，所以它的时间复杂度与末项成平方关系。

冒泡排序改进

这样的算法是否真的可以满足我们在各种情况下的需求呢？

可以设想一个这样的序列，部分元素已经就位，但是待排序的部分未必是无序的。

对于这样一个序列，如果采用我们一开始的算法，就会在序列整体有序后，多余的继续扫描序列。

换句话说，我们对于相邻两个元素的检查，可能在不久的过去已经做过了，它们是有序的，但我们还是机械的一趟一趟扫描这些序列，就只是为了我们认为的所有元素归位。

改进的策略是，我们在扫描时，不妨记录一下，是否真的存在逆序对，如果不存在，那么这个序列局部处处有序，整体必然是有序的，我们可以提前终止程序了。

现在的问题是，如何判断存在或不存在逆序对，或者说，什么是存在逆序对的条件？这个问题的答案是不言而喻的，就是在这一趟扫描中，曾经是否交换过一对元素。

冒泡排序再改进

这样的算法是否就可以应对所有的场景呢？

由于篇幅原因，这里直接给出改进的代码和思路。通过增加last来标记扫描的边界，对于超出边界的元素，是否值得扫描呢，留给各位自己思考。

标签：