走狗排序是如何工作的？

Question

Stooge 排序是一种排序算法，描述如下：

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)

该算法的运行时间很糟糕，我知道这一点。
问题：我想知道这个算法是如何工作的？

Answer 1

您对子数组的第一个和最后一个元素进行排序。（需要的话可以换）

然后你递归地对子数组的前 2/3 ^rd、子数组的最后 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，并且完全数组已排序。