臭皮匠排序是下面描述的排序算法:傀儡排序如何工作?
Stooge-Sort(A,i,j)
if(A[i]>A[]])
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)
算法有一個可怕的運行時間,我知道。
問題:我想知道這個算法是如何工作的?
臭皮匠排序是下面描述的排序算法:傀儡排序如何工作?
Stooge-Sort(A,i,j)
if(A[i]>A[]])
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)
算法有一個可怕的運行時間,我知道。
問題:我想知道這個算法是如何工作的?
您排序子數組的第一個和最後一個元素。 (如果需要交換)
然後你遞歸排序的第一個2/3 第三子陣的,子陣的最後2/3 RD又一次第一子陣列的2/3 RD。
爲了證明您可以使用歸納的正確性。
1. Clearly this algo works for 0, 1 and 2 element array.
2. Assuming it works for all arrays shorter than subarray
[i, j] let's prove it works for array[i,j] also. Let's
divide range[i,j] in 3 parts x, y and z;
a. After Stooge-Sort(A,i,j-k), or [xy], every element in range
y are larger than that of x. (Because range [xy] has
lesser elements than range[i,j])
b. After Stooge-Sort(A,i+k,j), or [yz], all largest elements
have moved to z and are sorted. So z is sorted and contains
largest elements of the array.
c. After Stooge-Sort(A,i,j-k), or [xy], first (2/3)rd part of
array is also sorted making the complete array sorted.
從步驟a,b和c,我們可以得出結論部分的x,y和z被分類和x的所有元素比y大(或相等),和z的所有元素是(大於或等於)比z和完整的數組排序。
它採用分而治之的策略。
Set i = list first element index , j = list last element index
Set list item at position i = min(list value at position i, list value at position j)
Set list item at position j = max(list value at position i, list value at position j)
If (j - i) <= 1 return sorted list
Else Set t = (j - i + 1)/3
Call sort with {i = i, j = j - t} then {i = i + t, j = j } then {i = i, j = j - t}
可以說,我要排序陣列[1,4,5,3,-6,3,7,10,-2,-5]
這種將開始:
Before: [1,4,5,3,-6,3,7,10,-2,-5] (i=0 ;j=9)
Before: [-5,4,5,3,-6,3,7,10,-2,1] (i=0 ;j=6)
Before: [-5,4,5,3,-6,3,7,10,-2,1] (i=0 ;j=4)
Before: [-6,4,5,3,-5,3,7,10,-2,1] (i=0 ;j=3)
Before: [-6,4,5,3,-5,3,7,10,-2,1] (i=0 ;j=2)
Before: [-6,4,5,3,-5,3,7,10,-2,1] (i=0 ;j=1)
After: [-6,4,5,3,-5,3,7,10,-2,1] (i=0 ;j=1)
Before: [-6,4,5,3,-5,3,7,10,-2,1] (i=1 ;j=2)
After: [-6,4,5,3,-5,3,7,10,-2,1] (i=1 ;j=2)
Before: [-6,4,5,3,-5,3,7,10,-2,1] (i=0 ;j=1)
After: [-6,4,5,3,-5,3,7,10,-2,1] (i=0 ;j=1)
After: [-6,4,5,3,-5,3,7,10,-2,1] (i=0 ;j=2)
Before: [-6,4,5,3,-5,3,7,10,-2,1] (i=1 ;j=3)
Before: [-6,3,5,4,-5,3,7,10,-2,1] (i=1 ;j=2)
After: [-6,3,5,4,-5,3,7,10,-2,1] (i=1 ;j=2)
Before: [-6,3,5,4,-5,3,7,10,-2,1] (i=2 ;j=3)
After: [-6,3,4,5,-5,3,7,10,-2,1] (i=2 ;j=3)
Before: [-6,3,4,5,-5,3,7,10,-2,1] (i=1 ;j=2)
After: [-6,3,4,5,-5,3,7,10,-2,1] (i=1 ;j=2)
After: [-6,3,4,5,-5,3,7,10,-2,1] (i=1 ;j=3)
Before: [-6,3,4,5,-5,3,7,10,-2,1] (i=0 ;j=2)
Before: [-6,3,4,5,-5,3,7,10,-2,1] (i=0 ;j=1)
After: [-6,3,4,5,-5,3,7,10,-2,1] (i=0 ;j=1)
Before: [-6,3,4,5,-5,3,7,10,-2,1] (i=1 ;j=2)
After: [-6,3,4,5,-5,3,7,10,-2,1] (i=1 ;j=2)
Before: [-6,3,4,5,-5,3,7,10,-2,1] (i=0 ;j=1)
After: [-6,3,4,5,-5,3,7,10,-2,1] (i=0 ;j=1)
After: [-6,3,4,5,-5,3,7,10,-2,1] (i=0 ;j=2)
After: [-6,3,4,5,-5,3,7,10,-2,1] (i=0 ;j=3)
Before: [-6,3,4,5,-5,3,7,10,-2,1] (i=1 ;j=4)
Before: [-6,-5,4,5,3,3,7,10,-2,1] (i=1 ;j=3)
Before: [-6,-5,4,5,3,3,7,10,-2,1] (i=1 ;j=2)
After: [-6,-5,4,5,3,3,7,10,-2,1] (i=1 ;j=2)
Before: [-6,-5,4,5,3,3,7,10,-2,1] (i=2 ;j=3)
//etc
'如果(A [I]> A []])'必須'如果(A [I]> A [j]])' – Gajahlemu
只需用一個短陣列,一支鉛筆和一張紙「玩電腦」 - 找出代碼的最簡單方法就是在腦海中執行它(或者使用調試器和步驟,但是我有時依靠手工勞動的粉絲:) –