这个算法最早2014年就在stackoverflow上出现了。不过这次作者重新提出来了。作者的证明过程：
定义Pi是经过i次（1 ≤ i ≤ n）外循环后得到的数组。
如果算法正确，那么前i项已经是升序排列，即A[1] ≤ A[2] ≤ . . . ≤ A[i]。
证明该算法正确，实际上就是证明P?对于任何n都成立。'
根据数学归纳法，我们只要证明P?成立，假设Pi成立，接着再证明Pi+1也成立，命题即可得证。
P1显然是正确的，而且这一步和普通的冒泡算法降序没有区别，经过第1次外循环，A[1]就是整个数组的最大元素。
接着我们假设Pi成立，然后证明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]
经过一系列交换，最大元素最终被放到了A[i+1] 位置上，原来的A[i+1]变成了最大元素，A[k]被插入了大小介于原来A[k]和A[k-1]之间的元素。
3、i+1 ≤ j ≤ n
由于最大元素已经交换到前i+1个元素中，此过程也没有任何元素交换。
最后，Pn就是升序排序算法执行完以后的结果。
由于内外两组循环没有任何范围差别，因此这可以说是“最简单”的排序算法了。
从代码上来看，它很像冒泡算法，但从证明过程中可以看出，这实际上是一种插入算法。
【 在 ArchLinux 的大作中提到: 】
: 我发现i = 1这个循环把最大数放到a[1]的位置之后，后面这个二重循环实际上就是把a[i]插入到a[1..i-1]的类似插入排序的过程，只是因为代码里用的是swap操作，数据移动的次数可能比教科书上的插入排序算法的插入过程要多。
:
: 所以总的算法的实际上就相当于：先把数组的最大数移到最前面，然后做一次插入排序。
: ...................
--来自微水木3.5.11
--
修改:foliver FROM 140.206.194.*
FROM 140.206.194.*