stooge sort是一种排序算法，描述如下：
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)
算法的运行时间很糟糕，我知道这一点。
问：我想知道这个算法是如何工作的？
最佳答案
对子数组的第一个和最后一个元素进行排序。（如有需要，交换）
然后递归地对子阵的前2/3、最后2/3和子阵的前2/3进行排序。
为了证明正确性，你可以使用归纳法。
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，整个数组被排序。
关于arrays - 垃圾箱排序如何工作？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/7682287/