七-3 Stooge排序

7-3 Stooge排序

Howard、Fine等教授提出了下面的“漂亮的”排序算法：    牛B 啊。。

不愧是教授啊。。这么简单的算法代码。。

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); }
主要写一下证明。。。

初始化：i+1>=j时，[i, j]区间中只有一个或者两个元素，唯一的操作就是 if A[i]>A[j] then exchange A[i]<->A[j]，显然循环不变式是成立的。

保持：

假设这是某段l到r，三次调用做stooge_sort是图中有颜色的部分。第一次调用函数返回时，黄色2>=黄色1。第二次调用函数返回时，蓝色的3>=蓝色的2,且，蓝色3>=黄色2>=黄色1。但是，蓝色2与黄色1的关系并不清楚。第三次调用函数返回时，绿色2>=绿色1。所以这个时候l到r的元素有序。

终止：STOOGE-SORT(A, i, Length[A])调用结束后，根据循环不变式，数组A中的元素是有序的。