论坛徽章:: 0

电梯直达

1楼 [收藏(0)] [报告]

发表于 2009-12-09 11:16 |只看该作者 |倒序浏览

程序是用伪码写的，A代表数组，i,j都代表下标。
想请问到底是怎么做到排序的
exchange 代表交换

STOOGE-SORT(A, i, j)
if  A[i] > A[j]
     then exchange A[i]<--->A[j]
if i+1 >= j
   then return  k = (j - i  + 1)/3
STOOGE-SORT(A, i, j-k)
STOOGE-SORT(A, i+k, j)
STOOGE-SORT(A, i, j-k)

文库|博客

hellioncu

巨富豪门

论坛徽章:: 324

2楼 [报告]

发表于 2009-12-09 13:05 |只看该作者

网络上搜索下都有解释
Howard、Fine等教授提出了下面的“漂亮的”排序算法。

STOOGE-SORT(A, i, j)
1 if A>A[j]
2    then exchange A<->A[j]
3 if i+1>=j
4    then return
5 k<-(j-i+1)/3
6 STOOGE-SORT(A, i, j-k)
7 STOOGE-SORT(A, i+k, j)
8 STOOGE-SORT(A, i, j-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>A[j] then exchange A<->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)