《算法导论》7-3看到了这个好东东，beautiful-sort，代码确实漂亮。不愧是教授啊，Howard，Fine，膜拜ing.
int stooge_sort(int a[],int s,int t)
{
int k;
if (a[s]>a[t])
swap(a[s],a[t],k);
if (s+1>=t)
return 0;
k=(t-s+1)/3;
stooge_sort(a,s,t-k);
stooge_sort(a,s+k,t);
stooge_sort(a,s,t-k);
}
a) 证明：如果n=Length[A]，那么STOOGE-SORT(A, 1, Length[A])能正确地对输入数组A[1..n]进行排序。
循环不变式：过程STOOGE-SORT(A, i, j)被调用后，数组A中[i, j]区间内的元素是有序的。
初始化：i+1>=j时，[i, j]区间中只有一个或者两个元素，唯一的操作就是 if A[i]>A[j] then exchange A[i]<->A[j]，显然循环不变式是成立的。
保 持：每一次STOOGE-SORT(A, i, j)被调用时，假设循环不变式成立。则调用STOOG-SORT(A, i, j-k)使得区间[i, j-k]有序，调用STOOG-SORT(A, i+k, j)使得区间[i+k, j]有序。因为k=(j-i+1)/3，所以区间[i, j-k]和区间[i+k, j]的重叠部分区间[i+k, j-k]的元素个数为[i, j]中元素个数的1/3，也为k个。因调用STOOG-SORT(A, i, j-k)后区间[i, j-k]有序，所以区间[i+k, j-k]中的元素应该是区间[i, j-k]中最大的k个元素，于是调用STOOG-SORT(A, i+k, j)后可以保证区间[j-k+1, j]中包含区间[i, j]中最大的k个元素并且是有序的。因此可保证在第二次调用STOOG-SORT(A, i, j-k)后区间[i, j]有序。
终止：STOOGE-SORT(A, i, Length[A])调用结束后，根据循环不变式，数组A中的元素是有序的。
b) 给出一个表达STOOGE-SORT最坏情况的运行时间的递归式，以及关于最坏情况运行时间的一个紧确的渐进（Θ记号）界。
T(n)=3T(2n/3)+Θ(1)
根据主定理：
a=3 b=3/2 f(n)=Θ(1)
故有 f(n)=O(n^log(3/2, 3-ε)) (ε>0)
所以 T(n)=Θ(n^log(3/2, 3))>Θ(n^2)
复制了大牛的文章过来，没事自己看看。
不过怎么觉得Thomas.H.Cormen等人有点讽刺讽刺这几个教授呢？？