傀儡排序如何工作？

Question

臭皮匠排序是下面描述的排序算法：

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) 

算法有一个可怕的运行时间，我知道。
问题：我想知道这个算法是如何工作的？

Answer 1

您排序子数组的第一个和最后一个元素。 （如果需要交换）

然后你递归排序的第一个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和完整的数组排序。

Answer 2

它采用分而治之的策略。

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