Posted on 2007-07-25 14:13
ZelluX 閱讀(686)
評論(0) 編輯 收藏 所屬分類:
Algorithm
CLRS page 161
偽代碼描述：
Stooge-sort(A, i, j)
if A[i] > A[j]
then exchange A[i], A[]
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)
即先排序前2/3部分，然后是后2/3部分，最后再進行前面1/3的排序。
a. 證明算法正確性
由于是遞歸算法，而初始狀態顯然成立，因此只要證明當部分排序正確時，整體也能夠被正確排序：
第一次排序后，第二部分每個數都不小于第一部分的所有數；
第二次排序后，第二部分某些數被交換到第三部分中，此時第三部分數都不小于第二部分和第一部分的數，但是第二部分的數并不一定都小于第一部分的（因為可能包含第三部分的數，而這些數與第一部分數的大小關系無法確認）；
第三次排序后，第二部分的數都不小于第一部分的數。
這樣，第一部分的任意數<=第二部分的任意數<=第三部分的任意數
而且各部分的數都已排序，因此整體已被排序。
b. 復雜度分析
遞歸式
T(n) = 3T(2n/3) + 1
由Master Theorem
T(n) = O(n^log(3/2, 3))