Posted on 2007-07-25 14:13
ZelluX 閱讀(685)
評(píng)論(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部分，最后再進(jìn)行前面1/3的排序。
a. 證明算法正確性
由于是遞歸算法，而初始狀態(tài)顯然成立，因此只要證明當(dāng)部分排序正確時(shí)，整體也能夠被正確排序：
第一次排序后，第二部分每個(gè)數(shù)都不小于第一部分的所有數(shù)；
第二次排序后，第二部分某些數(shù)被交換到第三部分中，此時(shí)第三部分?jǐn)?shù)都不小于第二部分和第一部分的數(shù)，但是第二部分的數(shù)并不一定都小于第一部分的（因?yàn)榭赡馨谌糠值臄?shù)，而這些數(shù)與第一部分?jǐn)?shù)的大小關(guān)系無法確認(rèn)）；
第三次排序后，第二部分的數(shù)都不小于第一部分的數(shù)。
這樣，第一部分的任意數(shù)<=第二部分的任意數(shù)<=第三部分的任意數(shù)
而且各部分的數(shù)都已排序，因此整體已被排序。
b. 復(fù)雜度分析
遞歸式
T(n) = 3T(2n/3) + 1
由Master Theorem
T(n) = O(n^log(3/2, 3))