比冒泡算法更简单的排序算法：一个看似充满bug的程序，其实是对的，程序bug能是正数吗？真的很棒。比如程序员们非常熟悉的排序算法，两个“bug”都能打对，真是不可思议。请看这位程序员写的数组升序排序代码：fori=1tondoforj=1tondoifA[i]A[j]thenswapA[i]andA[j]后者的区别在于j=i+1和A[i]>A[j]，这两个程序有很大的不同。但是，我要告诉你一个不可思议的事实，第一串代码是正确的，可以严格证明。那么它是如何实现正确排序的呢？其实仔细想想也很容易理解为什么是可以的。由于该算法比冒泡排序多了一半的交换操作，所以它可以将降序编程为升序。不过，作者还是给出了严格的证明。我们将P?定义为经过i(1≤i≤n)次外循环后得到的数组。如果算法正确，则前i项已经按升序排列，即A[1]≤A[2]≤。..≤A[i]。证明算法正确实际上就是证明P?对任何n都成立。根据数学归纳法，我们只需证明P?为真，假设P?为真，再证明Pi+1也为真，命题即可得证。P?显然是正确的，这一步和普通泡泡算法的降序没有区别。在第一个外层循环之后，A[1]是整个数组的最大元素。那么我们假设P?成立，进而证明Pi+1成立。我们先定义一个序数k：首先假设A[k]（k在1~i之间）满足最小数A[k]>A[i+1]，则A[k?1]≤A[i+1]（k≠1）。如果A[i+1]≥A[i]，那么这样的k不存在，我们让k=i+1。考虑以下三种情况：1.1≤j≤k?1因为A[i+1]>A[j]，没有元素交换发生。2、k≤j≤i（如果k=i+1，则不存在这一步）由于A[j]>A[i+1]，所以每次比较后都会有元素交换。我们用A[]和A′[]来表示交换前后的元素，所以A′[i+1]=A[k],A′[k]=A[i+1]通过一系列exchanges，最大元素最终被放到了A[i+1]的位置，原来的A[i+1]变成了最大元素，插入了A[k]，大小介于原来的A[k]和A[k-1]之间的元素。3.i+1≤j≤n由于最大元素已经交换到前i+1个元素，所以这个过程没有元素交换。最后，P?是执行升序排序算法后的结果。由于内部和外部循环集之间没有范围差异，因此这可以说是“最简单”的排序算法。从代码上看，它看起来像一个冒泡算法，但从证明过程可以看出它实际上是一个插入算法。△插入算法AlgorithmicComplexity显然，该算法会一直进行n2比较，然后计算该算法的交换次数。可以证明交换接下来至多是I+2(n-1)次，至少是n-1次。其中I是初始数的倒数，最大值为n(n-1)/2，所以整个算法的复杂度为O(n2)。从证明过程可以看出，除了i=1的循环外，其余循环中j=i-1之后的部分是完全无效的，所以这部分可以省略，得到一个简化的算法。fori=2tondoforj=1toi?1doifA[i]A[j]时交换。在作者提出的算法中，j=1到n，当A[i]
