求教个算法Stooge排序算法
程序是用伪码写的，A代表数组，i,j都代表下标。
想请问到底是怎么做到排序的
exchange 代表交换

[code=C/C++][/code]
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)

请教各位？

[解决办法]

C/C++ code

void stooge(int A[], int i, int j){    if(A[i] > A[j])//首尾交换    {        // exchange        int temp = A[i];        A[i] = A[j];        A[j] = temp;    }    if(i+1 >= j)        return;    int k = (j-i+1)/3;    stooge(A, i, j-k);// 递归调用前 2/3     stooge(A, i+k, j);// 递归调用后 2/3    stooge(A, i, j-k);// 递归调用前 2/3}
[解决办法]
好像算法导论里有这个算法。
属于交换排序，是对快排的划分方法的一个改进，不是划分为2个部分，而是划分为3个部分，从而提高排序性能。

STOOGE-SORT(A, i, j)
对数组A中第i个元素到第j个元素进行升序排序。
排序的思想：
1.使A[i]、A[J]有序。
2.对A中前2/3进行排序，使A中前2/3的元素保持升序。
3.对A中后2/3进行排序，使A中后2/3的元素保持升序。
至此可以知道，对后2/3排序后，会打乱中间1/3部分的元素顺序，从而使得前2/3无序。
4.再对前2/3进行排序，这时，整个数组中的元素即为有序。

递归出口，是只有两个元素时，这是很明显的。
[解决办法]
重新贴一下，注意每个begin都伴随一个end

C/C++ code
 
  
 loop:   1 
 i=0,j=4: begin: stooge(A, 0, 4) 
 i=0,j=4,k=1: stooge(A, i, j-k); stooge(A, 0, 3) 
  
 loop:   2 
 i=0,j=3: begin: stooge(A, 0, 3) 
 i=0,j=3,k=1: stooge(A, i, j-k); stooge(A, 0, 2) 
  
 loop:   3 
 i=0,j=2: begin: stooge(A, 0, 2) 
 i=0,j=2,k=1: stooge(A, i, j-k); stooge(A, 0, 1) 
  
 loop:   4 
 i=0,j=1: begin: stooge(A, 0, 1) 
 end: stooge(A, 0, 1) 
 i=0,j=2,k=1: stooge(A, i+k, j); stooge(A, 0, 1) 
  
 loop:   5 
 i=1,j=2: begin: stooge(A, 1, 2) 
 end: stooge(A, 1, 2) 
 i=0,j=2,k=1: stooge(A, i+k, j); stooge(A, 0, 1) 
  
 loop:   6 
 i=0,j=1: begin: stooge(A, 0, 1) 
 end: stooge(A, 0, 1) 
 i=0,j=2,k=1: end: stooge(A, 0, 1) 
 i=0,j=3,k=1: stooge(A, i+k, j); stooge(A, 0, 2) 
  
 loop:   7 
 i=1,j=3: begin: stooge(A, 1, 3) 
 i=1,j=3,k=1: stooge(A, i, j-k); stooge(A, 1, 2) 
  
 loop:   8 
 i=1,j=2: begin: stooge(A, 1, 2) 
 end: stooge(A, 1, 2) 
 i=1,j=3,k=1: stooge(A, i+k, j); stooge(A, 1, 2) 
  
 loop:   9 
 i=2,j=3: begin: stooge(A, 2, 3) 
 end: stooge(A, 2, 3) 
 i=1,j=3,k=1: stooge(A, i+k, j); stooge(A, 1, 2) 
  
 loop:  10 
 i=1,j=2: begin: stooge(A, 1, 2) 
 end: stooge(A, 1, 2) 
 i=1,j=3,k=1: end: stooge(A, 1, 2) 
 i=0,j=3,k=1: stooge(A, i+k, j); stooge(A, 0, 2) 
  
 loop:  11 
 i=0,j=2: begin: stooge(A, 0, 2) 
 i=0,j=2,k=1: stooge(A, i, j-k); stooge(A, 0, 1) 
  
 loop:  12 
 i=0,j=1: begin: stooge(A, 0, 1) 
 end: stooge(A, 0, 1) 
 i=0,j=2,k=1: stooge(A, i+k, j); stooge(A, 0, 1) 
  
 loop:  13 
 i=1,j=2: begin: stooge(A, 1, 2) 
 end: stooge(A, 1, 2) 
 i=0,j=2,k=1: stooge(A, i+k, j); stooge(A, 0, 1) 
  
 loop:  14 
 i=0,j=1: begin: stooge(A, 0, 1) 
 end: stooge(A, 0, 1) 
 i=0,j=2,k=1: end: stooge(A, 0, 1) 
 i=0,j=3,k=1: end: stooge(A, 0, 2) 
 i=0,j=4,k=1: stooge(A, i+k, j); stooge(A, 0, 3) 
  
 loop:  15 
 i=1,j=4: begin: stooge(A, 1, 4) 
 i=1,j=4,k=1: stooge(A, i, j-k); stooge(A, 1, 3) 
  
 loop:  16 
 i=1,j=3: begin: stooge(A, 1, 3) 
 i=1,j=3,k=1: stooge(A, i, j-k); stooge(A, 1, 2) 
  
 loop:  17 
 i=1,j=2: begin: stooge(A, 1, 2) 
 end: stooge(A, 1, 2) 
 i=1,j=3,k=1: stooge(A, i+k, j); stooge(A, 1, 2) 
  
 loop:  18 
 i=2,j=3: begin: stooge(A, 2, 3)  
 
 end: stooge(A, 2, 3) 
 i=1,j=3,k=1: stooge(A, i+k, j); stooge(A, 1, 2) 
  
 loop:  19 
 i=1,j=2: begin: stooge(A, 1, 2) 
 end: stooge(A, 1, 2) 
 i=1,j=3,k=1: end: stooge(A, 1, 2) 
 i=1,j=4,k=1: stooge(A, i+k, j); stooge(A, 1, 3) 
  
 loop:  20 
 i=2,j=4: begin: stooge(A, 2, 4) 
 i=2,j=4,k=1: stooge(A, i, j-k); stooge(A, 2, 3) 
  
 loop:  21 
 i=2,j=3: begin: stooge(A, 2, 3) 
 end: stooge(A, 2, 3) 
 i=2,j=4,k=1: stooge(A, i+k, j); stooge(A, 2, 3) 
  
 loop:  22 
 i=3,j=4: begin: stooge(A, 3, 4) 
 end: stooge(A, 3, 4) 
 i=2,j=4,k=1: stooge(A, i+k, j); stooge(A, 2, 3) 
  
 loop:  23 
 i=2,j=3: begin: stooge(A, 2, 3) 
 end: stooge(A, 2, 3) 
 i=2,j=4,k=1: end: stooge(A, 2, 3) 
 i=1,j=4,k=1: stooge(A, i+k, j); stooge(A, 1, 3) 
  
 loop:  24 
 i=1,j=3: begin: stooge(A, 1, 3) 
 i=1,j=3,k=1: stooge(A, i, j-k); stooge(A, 1, 2) 
  
 loop:  25 
 i=1,j=2: begin: stooge(A, 1, 2) 
 end: stooge(A, 1, 2) 
 i=1,j=3,k=1: stooge(A, i+k, j); stooge(A, 1, 2) 
  
 loop:  26 
 i=2,j=3: begin: stooge(A, 2, 3) 
 end: stooge(A, 2, 3) 
 i=1,j=3,k=1: stooge(A, i+k, j); stooge(A, 1, 2) 
  
 loop:  27 
 i=1,j=2: begin: stooge(A, 1, 2) 
 end: stooge(A, 1, 2) 
 i=1,j=3,k=1: end: stooge(A, 1, 2) 
 i=1,j=4,k=1: end: stooge(A, 1, 3) 
 i=0,j=4,k=1: stooge(A, i+k, j); stooge(A, 0, 3) 
  
 loop:  28 
 i=0,j=3: begin: stooge(A, 0, 3) 
 i=0,j=3,k=1: stooge(A, i, j-k); stooge(A, 0, 2) 
  
 loop:  29 
 i=0,j=2: begin: stooge(A, 0, 2) 
 i=0,j=2,k=1: stooge(A, i, j-k); stooge(A, 0, 1) 
  
 loop:  30 
 i=0,j=1: begin: stooge(A, 0, 1) 
 end: stooge(A, 0, 1) 
 i=0,j=2,k=1: stooge(A, i+k, j); stooge(A, 0, 1) 
  
 loop:  31 
 i=1,j=2: begin: stooge(A, 1, 2) 
 end: stooge(A, 1, 2) 
 i=0,j=2,k=1: stooge(A, i+k, j); stooge(A, 0, 1) 
  
 loop:  32 
 i=0,j=1: begin: stooge(A, 0, 1) 
 end: stooge(A, 0, 1) 
 i=0,j=2,k=1: end: stooge(A, 0, 1) 
 i=0,j=3,k=1: stooge(A, i+k, j); stooge(A, 0, 2) 
  
 loop:  33 
 i=1,j=3: begin: stooge(A, 1, 3) 
 i=1,j=3,k=1: stooge(A, i, j-k); stooge(A, 1, 2) 
  
 loop:  34 
 i=1,j=2: begin: stooge(A, 1, 2) 
 end: stooge(A, 1, 2) 
 i=1,j=3,k=1: stooge(A, i+k, j); stooge(A, 1, 2) 
  
 loop:  35 
 i=2,j=3: begin: stooge(A, 2, 3) 
 end: stooge(A, 2, 3) 
 i=1,j=3,k=1: stooge(A, i+k, j); stooge(A, 1, 2) 
  
 loop:  36 
 i=1,j=2: begin: stooge(A, 1, 2) 
 end: stooge(A, 1, 2) 
 i=1,j=3,k=1: end: stooge(A, 1, 2) 
 i=0,j=3,k=1: stooge(A, i+k, j); stooge(A, 0, 2) 
  
 loop:  37 
 i=0,j=2: begin: stooge(A, 0, 2) 
 i=0,j=2,k=1: stooge(A, i, j-k); stooge(A, 0, 1) 
  
 loop:  38 
 i=0,j=1: begin: stooge(A, 0, 1) 
 end: stooge(A, 0, 1) 
 i=0,j=2,k=1: stooge(A, i+k, j); stooge(A, 0, 1) 
  
 loop:  39 
 i=1,j=2: begin: stooge(A, 1, 2) 
 end: stooge(A, 1, 2) 
 i=0,j=2,k=1: stooge(A, i+k, j); stooge(A, 0, 1) 
  
 loop:  40 
 i=0,j=1: begin: stooge(A, 0, 1) 
 end: stooge(A, 0, 1) 
 i=0,j=2,k=1: end: stooge(A, 0, 1) 
 i=0,j=3,k=1: end: stooge(A, 0, 2) 
 i=0,j=4,k=1: end: stooge(A, 0, 3)