优化选择排序算法（OSSA） - 如何解决它？

Question

我发现this paper，它描述了一种选择排序的优化版本，它被认为总体上胜过了传统的选择排序。在第4页的描述为这个特定变体的伪代码如下：

k = 0 
for i = n–1 to k 
    IndexOfLarge = IndexOfSmall = k 

    for j = k+1 to i 
    if (X[j] > X[IndexOfLarge]) 
     IndexOfLarge = j 
    if (X[j] < X[IndexOfSmall]) 
     IndexOfSmall = j 

    Large = X[IndexOfLarge] 
    Small = X[IndexOfSmall] 
    X[IndexOfLarge] = X[i] 
    X[IndexOfSmall] = X[k] 

    if (IndexOfLarge == k) 
    Temp = X[i] 
    X[i] = Large 
    X[IndexOfSmall] = Temp 
    Else 
    X[i] = Large 

    if (IndexOfSmall == i) 
    Temp = X[k] 
    X[k] = Small 
    X[IndexOfLarge] = Temp 
    Else 
    X[k] = Small 

    k = k+1 

这是很容易翻译成C：

#include "selectionsort.h" 

void selectionsort(int *array, size_t num) { 

    int *x = array; 

    for(int i = num-1, k = 0; i > k; --i, ++k) { 
     int i_small = k; 
     int i_large = k; 

     for(int j = k+1; j <= i; ++j) { 

      if(x[j] > x[i_large]) { 
       i_large = j; 
      } 

      if(x[j] < x[i_small]) { 
       i_small = j; 
      } 
     } 

     int large = x[i_large]; 
     int small = x[i_small]; 
     x[i_large] = x[i]; 
     x[i_small] = x[k]; 

     int tmp; 
     if(i_large == k) { 
      tmp = x[i]; 
      x[i] = large; 
      x[i_small] = tmp; 
     } else { 
      x[i] = large; 
     } 

     if(i_small == i) { 
      tmp = x[k]; 
      x[k] = small; 
      x[i_large] = tmp; 
     } else { 
      x[k] = small; 
     } 
} 

现在事实证明，这种特定的实现不始终对所有输入进行分类。例如，下面是一个100个随机整数的数组，范围从0到100.如果针对每次迭代进行布局，则在最后两行中，在数组中间右侧，您将看到简单地被覆盖的编号52。

0 86 85 24 38 64 29 8 50 38 64 1 71 71 93 1 35 18 52 31 10 88 21 64 61 85 39 71 26 98 94 1 83 78 25 20 7 55 96 57 59 59 59 29 96 17 30 93 35 49 90 11 36 10 76 97 95 14 33 88 78 93 89 60 36 80 46 44 8 41 0 59 66 25 89 61 42 85 20 44 33 76 55 36 87 97 32 47 10 32 0 88 24 55 13 61 35 60 71 98 
0 0 85 24 38 64 29 8 50 38 64 1 71 71 93 1 35 18 52 31 10 88 21 64 61 85 39 71 26 71 94 1 83 78 25 20 7 55 96 57 59 59 59 29 96 17 30 93 35 49 90 11 36 10 76 97 95 14 33 88 78 93 89 60 36 80 46 44 8 41 86 59 66 25 89 61 42 85 20 44 33 76 55 36 87 97 32 47 10 32 0 88 24 55 13 61 35 60 98 98 
0 0 0 24 38 64 29 8 50 38 64 1 71 71 93 1 35 18 52 31 10 88 21 64 61 85 39 71 26 71 94 1 83 78 25 20 7 55 96 57 59 59 59 29 96 17 30 93 35 49 90 11 36 10 76 60 95 14 33 88 78 93 89 60 36 80 46 44 8 41 86 59 66 25 89 61 42 85 20 44 33 76 55 36 87 97 32 47 10 32 85 88 24 55 13 61 35 97 98 98 
0 0 0 1 38 64 29 8 50 38 64 24 71 71 93 1 35 18 52 31 10 88 21 64 61 85 39 71 26 71 94 1 83 78 25 20 7 55 96 57 59 59 59 29 96 17 30 93 35 49 90 11 36 10 76 60 95 14 33 88 78 93 89 60 36 80 46 44 8 41 86 59 66 25 89 61 42 85 20 44 33 76 55 36 87 35 32 47 10 32 85 88 24 55 13 61 97 97 98 98 
0 0 0 1 1 64 29 8 50 38 64 24 71 71 93 38 35 18 52 31 10 88 21 64 61 85 39 71 26 71 94 1 83 78 25 20 7 55 61 57 59 59 59 29 96 17 30 93 35 49 90 11 36 10 76 60 95 14 33 88 78 93 89 60 36 80 46 44 8 41 86 59 66 25 89 61 42 85 20 44 33 76 55 36 87 35 32 47 10 32 85 88 24 55 13 96 97 97 98 98 
0 0 0 1 1 1 29 8 50 38 64 24 71 71 93 38 35 18 52 31 10 88 21 64 61 85 39 71 26 71 94 64 83 78 25 20 7 55 61 57 59 59 59 29 13 17 30 93 35 49 90 11 36 10 76 60 95 14 33 88 78 93 89 60 36 80 46 44 8 41 86 59 66 25 89 61 42 85 20 44 33 76 55 36 87 35 32 47 10 32 85 88 24 55 96 96 97 97 98 98 
0 0 0 1 1 1 7 8 50 38 64 24 71 71 93 38 35 18 52 31 10 88 21 64 61 85 39 71 26 71 94 64 83 78 25 20 29 55 61 57 59 59 59 29 13 17 30 93 35 49 90 11 36 10 76 60 55 14 33 88 78 93 89 60 36 80 46 44 8 41 86 59 66 25 89 61 42 85 20 44 33 76 55 36 87 35 32 47 10 32 85 88 24 95 96 96 97 97 98 98 
0 0 0 1 1 1 7 8 50 38 64 24 71 71 93 38 35 18 52 31 10 88 21 64 61 85 39 71 26 71 24 64 83 78 25 20 29 55 61 57 59 59 59 29 13 17 30 93 35 49 90 11 36 10 76 60 55 14 33 88 78 93 89 60 36 80 46 44 8 41 86 59 66 25 89 61 42 85 20 44 33 76 55 36 87 35 32 47 10 32 85 88 94 95 96 96 97 97 98 98 
0 0 0 1 1 1 7 8 8 38 64 24 71 71 88 38 35 18 52 31 10 88 21 64 61 85 39 71 26 71 24 64 83 78 25 20 29 55 61 57 59 59 59 29 13 17 30 93 35 49 90 11 36 10 76 60 55 14 33 88 78 93 89 60 36 80 46 44 50 41 86 59 66 25 89 61 42 85 20 44 33 76 55 36 87 35 32 47 10 32 85 93 94 95 96 96 97 97 98 98 
0 0 0 1 1 1 7 8 8 10 64 24 71 71 88 38 35 18 52 31 38 88 21 64 61 85 39 71 26 71 24 64 83 78 25 20 29 55 61 57 59 59 59 29 13 17 30 85 35 49 90 11 36 10 76 60 55 14 33 88 78 93 89 60 36 80 46 44 50 41 86 59 66 25 89 61 42 85 20 44 33 76 55 36 87 35 32 47 10 32 93 93 94 95 96 96 97 97 98 98 
0 0 0 1 1 1 7 8 8 10 10 24 71 71 88 38 35 18 52 31 38 88 21 64 61 85 39 71 26 71 24 64 83 78 25 20 29 55 61 57 59 59 59 29 13 17 30 85 35 49 90 11 36 64 76 60 55 14 33 88 78 32 89 60 36 80 46 44 50 41 86 59 66 25 89 61 42 85 20 44 33 76 55 36 87 35 32 47 10 93 93 93 94 95 96 96 97 97 98 98 
0 0 0 1 1 1 7 8 8 10 10 10 71 71 88 38 35 18 52 31 38 88 21 64 61 85 39 71 26 71 24 64 83 78 25 20 29 55 61 57 59 59 59 29 13 17 30 85 35 49 24 11 36 64 76 60 55 14 33 88 78 32 89 60 36 80 46 44 50 41 86 59 66 25 89 61 42 85 20 44 33 76 55 36 87 35 32 47 90 93 93 93 94 95 96 96 97 97 98 98 
0 0 0 1 1 1 7 8 8 10 10 10 11 71 88 38 35 18 52 31 38 88 21 64 61 85 39 71 26 71 24 64 83 78 25 20 29 55 61 57 59 59 59 29 13 17 30 85 35 49 24 71 36 64 76 60 55 14 33 88 78 32 47 60 36 80 46 44 50 41 86 59 66 25 89 61 42 85 20 44 33 76 55 36 87 35 32 89 90 93 93 93 94 95 96 96 97 97 98 98 
0 0 0 1 1 1 7 8 8 10 10 10 11 13 88 38 35 18 52 31 38 88 21 64 61 85 39 71 26 71 24 64 83 78 25 20 29 55 61 57 59 59 59 29 71 17 30 85 35 49 24 71 36 64 76 60 55 14 33 88 78 32 47 60 36 80 46 44 50 41 86 59 66 25 32 61 42 85 20 44 33 76 55 36 87 35 89 89 90 93 93 93 94 95 96 96 97 97 98 98 
0 0 0 1 1 1 7 8 8 10 10 10 11 13 14 38 35 18 52 31 38 88 21 64 61 85 39 71 26 71 24 64 83 78 25 20 29 55 61 57 59 59 59 29 71 17 30 85 35 49 24 71 36 64 76 60 55 35 33 88 78 32 47 60 36 80 46 44 50 41 86 59 66 25 32 61 42 85 20 44 33 76 55 36 87 88 89 89 90 93 93 93 94 95 96 96 97 97 98 98 
0 0 0 1 1 1 7 8 8 10 10 10 11 13 14 17 35 18 52 31 38 87 21 64 61 85 39 71 26 71 24 64 83 78 25 20 29 55 61 57 59 59 59 29 71 38 30 85 35 49 24 71 36 64 76 60 55 35 33 88 78 32 47 60 36 80 46 44 50 41 86 59 66 25 32 61 42 85 20 44 33 76 55 36 88 88 89 89 90 93 93 93 94 95 96 96 97 97 98 98 
0 0 0 1 1 1 7 8 8 10 10 10 11 13 14 17 18 35 52 31 38 87 21 64 61 85 39 71 26 71 24 64 83 78 25 20 29 55 61 57 59 59 59 29 71 38 30 85 35 49 24 71 36 64 76 60 55 35 33 36 78 32 47 60 36 80 46 44 50 41 86 59 66 25 32 61 42 85 20 44 33 76 55 88 88 88 89 89 90 93 93 93 94 95 96 96 97 97 98 98 
0 0 0 1 1 1 7 8 8 10 10 10 11 13 14 17 18 20 52 31 38 55 21 64 61 85 39 71 26 71 24 64 83 78 25 35 29 55 61 57 59 59 59 29 71 38 30 85 35 49 24 71 36 64 76 60 55 35 33 36 78 32 47 60 36 80 46 44 50 41 86 59 66 25 32 61 42 85 20 44 33 76 87 88 88 88 89 89 90 93 93 93 94 95 96 96 97 97 98 98 
0 0 0 1 1 1 7 8 8 10 10 10 11 13 14 17 18 20 20 31 38 55 21 64 61 85 39 71 26 71 24 64 83 78 25 35 29 55 61 57 59 59 59 29 71 38 30 85 35 49 24 71 36 64 76 60 55 35 33 36 78 32 47 60 36 80 46 44 50 41 76 59 66 25 32 61 42 85 52 44 33 86 87 88 88 88 89 89 90 93 93 93 94 95 96 96 97 97 98 98 
0 0 0 1 1 1 7 8 8 10 10 10 11 13 14 17 18 20 20 21 38 55 31 64 61 33 39 71 26 71 24 64 83 78 25 35 29 55 61 57 59 59 59 29 71 38 30 85 35 49 24 71 36 64 76 60 55 35 33 36 78 32 47 60 36 80 46 44 50 41 76 59 66 25 32 61 42 85 52 44 85 86 87 88 88 88 89 89 90 93 93 93 94 95 96 96 97 97 98 98 
0 0 0 1 1 1 7 8 8 10 10 10 11 13 14 17 18 20 20 21 24 55 31 64 61 33 39 71 26 71 38 64 83 78 25 35 29 55 61 57 59 59 59 29 71 38 30 44 35 49 24 71 36 64 76 60 55 35 33 36 78 32 47 60 36 80 46 44 50 41 76 59 66 25 32 61 42 85 52 85 85 86 87 88 88 88 89 89 90 93 93 93 94 95 96 96 97 97 98 98 
0 0 0 1 1 1 7 8 8 10 10 10 11 13 14 17 18 20 20 21 24 24 31 64 61 33 39 71 26 71 38 64 83 78 25 35 29 55 61 57 59 59 59 29 71 38 30 44 35 49 55 71 36 64 76 60 55 35 33 36 78 32 47 60 36 80 46 44 50 41 76 59 66 25 32 61 42 52 85 85 85 86 87 88 88 88 89 89 90 93 93 93 94 95 96 96 97 97 98 98 
0 0 0 1 1 1 7 8 8 10 10 10 11 13 14 17 18 20 20 21 24 24 25 64 61 33 39 71 26 71 38 64 52 78 31 35 29 55 61 57 59 59 59 29 71 38 30 44 35 49 55 71 36 64 76 60 55 35 33 36 78 32 47 60 36 80 46 44 50 41 76 59 66 25 32 61 42 83 85 85 85 86 87 88 88 88 89 89 90 93 93 93 94 95 96 96 97 97 98 98 
0 0 0 1 1 1 7 8 8 10 10 10 11 13 14 17 18 20 20 21 24 24 25 25 61 33 39 71 26 71 38 64 52 78 31 35 29 55 61 57 59 59 59 29 71 38 30 44 35 49 55 71 36 64 76 60 55 35 33 36 78 32 47 60 36 42 46 44 50 41 76 59 66 64 32 61 80 83 85 85 85 86 87 88 88 88 89 89 90 93 93 93 94 95 96 96 97 97 98 98 
0 0 0 1 1 1 7 8 8 10 10 10 11 13 14 17 18 20 20 21 24 24 25 25 26 33 39 71 61 71 38 64 52 61 31 35 29 55 61 57 59 59 59 29 71 38 30 44 35 49 55 71 36 64 76 60 55 35 33 36 78 32 47 60 36 42 46 44 50 41 76 59 66 64 32 78 80 83 85 85 85 86 87 88 88 88 89 89 90 93 93 93 94 95 96 96 97 97 98 98 
0 0 0 1 1 1 7 8 8 10 10 10 11 13 14 17 18 20 20 21 24 24 25 25 26 29 39 71 61 71 38 64 52 61 31 35 33 55 61 57 59 59 59 29 71 38 30 44 35 49 55 71 36 64 76 60 55 35 33 36 32 32 47 60 36 42 46 44 50 41 76 59 66 64 78 78 80 83 85 85 85 86 87 88 88 88 89 89 90 93 93 93 94 95 96 96 97 97 98 98 
0 0 0 1 1 1 7 8 8 10 10 10 11 13 14 17 18 20 20 21 24 24 25 25 26 29 29 71 61 71 38 64 52 61 31 35 33 55 61 57 59 59 59 39 71 38 30 44 35 49 55 71 36 64 64 60 55 35 33 36 32 32 47 60 36 42 46 44 50 41 76 59 66 76 78 78 80 83 85 85 85 86 87 88 88 88 89 89 90 93 93 93 94 95 96 96 97 97 98 98 
0 0 0 1 1 1 7 8 8 10 10 10 11 13 14 17 18 20 20 21 24 24 25 25 26 29 29 30 61 71 38 64 52 61 31 35 33 55 61 57 59 59 59 39 71 38 71 44 35 49 55 71 36 64 64 60 55 35 33 36 32 32 47 60 36 42 46 44 50 41 66 59 76 76 78 78 80 83 85 85 85 86 87 88 88 88 89 89 90 93 93 93 94 95 96 96 97 97 98 98 
0 0 0 1 1 1 7 8 8 10 10 10 11 13 14 17 18 20 20 21 24 24 25 25 26 29 29 30 31 59 38 64 52 61 61 35 33 55 61 57 59 59 59 39 71 38 71 44 35 49 55 71 36 64 64 60 55 35 33 36 32 32 47 60 36 42 46 44 50 41 66 71 76 76 78 78 80 83 85 85 85 86 87 88 88 88 89 89 90 93 93 93 94 95 96 96 97 97 98 98 
0 0 0 1 1 1 7 8 8 10 10 10 11 13 14 17 18 20 20 21 24 24 25 25 26 29 29 30 31 32 38 64 52 61 61 35 33 55 61 57 59 59 59 39 66 38 71 44 35 49 55 71 36 64 64 60 55 35 33 36 59 32 47 60 36 42 46 44 50 41 71 71 76 76 78 78 80 83 85 85 85 86 87 88 88 88 89 89 90 93 93 93 94 95 96 96 97 97 98 98 
0 0 0 1 1 1 7 8 8 10 10 10 11 13 14 17 18 20 20 21 24 24 25 25 26 29 29 30 31 32 32 64 52 61 61 35 33 55 61 57 59 59 59 39 66 38 41 44 35 49 55 71 36 64 64 60 55 35 33 36 59 38 47 60 36 42 46 44 50 71 71 71 76 76 78 78 80 83 85 85 85 86 87 88 88 88 89 89 90 93 93 93 94 95 96 96 97 97 98 98 
0 0 0 1 1 1 7 8 8 10 10 10 11 13 14 17 18 20 20 21 24 24 25 25 26 29 29 30 31 32 32 33 52 61 61 35 64 55 61 57 59 59 59 39 66 38 41 44 35 49 55 50 36 64 64 60 55 35 33 36 59 38 47 60 36 42 46 44 71 71 71 71 76 76 78 78 80 83 85 85 85 86 87 88 88 88 89 89 90 93 93 93 94 95 96 96 97 97 98 98 
0 0 0 1 1 1 7 8 8 10 10 10 11 13 14 17 18 20 20 21 24 24 25 25 26 29 29 30 31 32 32 33 33 61 61 35 64 55 61 57 59 59 59 39 44 38 41 44 35 49 55 50 36 64 64 60 55 35 52 36 59 38 47 60 36 42 46 66 71 71 71 71 76 76 78 78 80 83 85 85 85 86 87 88 88 88 89 89 90 93 93 93 94 95 96 96 97 97 98 98 
0 0 0 1 1 1 7 8 8 10 10 10 11 13 14 17 18 20 20 21 24 24 25 25 26 29 29 30 31 32 32 33 33 35 61 61 46 55 61 57 59 59 59 39 44 38 41 44 35 49 55 50 36 64 64 60 55 35 52 36 59 38 47 60 36 42 64 66 71 71 71 71 76 76 78 78 80 83 85 85 85 86 87 88 88 88 89 89 90 93 93 93 94 95 96 96 97 97 98 98 
0 0 0 1 1 1 7 8 8 10 10 10 11 13 14 17 18 20 20 21 24 24 25 25 26 29 29 30 31 32 32 33 33 35 35 61 46 55 61 57 59 59 59 39 44 38 41 44 61 49 55 50 36 42 64 60 55 35 52 36 59 38 47 60 36 64 64 66 71 71 71 71 76 76 78 78 80 83 85 85 85 86 87 88 88 88 89 89 90 93 93 93 94 95 96 96 97 97 98 98 
0 0 0 1 1 1 7 8 8 10 10 10 11 13 14 17 18 20 20 21 24 24 25 25 26 29 29 30 31 32 32 33 33 35 35 35 46 55 61 57 59 59 59 39 44 38 41 44 61 49 55 50 36 42 36 60 55 61 52 36 59 38 47 60 64 64 64 66 71 71 71 71 76 76 78 78 80 83 85 85 85 86 87 88 88 88 89 89 90 93 93 93 94 95 96 96 97 97 98 98 
0 0 0 1 1 1 7 8 8 10 10 10 11 13 14 17 18 20 20 21 24 24 25 25 26 29 29 30 31 32 32 33 33 35 35 35 36 55 60 57 59 59 59 39 44 38 41 44 61 49 55 50 46 42 36 60 55 61 52 36 59 38 47 61 64 64 64 66 71 71 71 71 76 76 78 78 80 83 85 85 85 86 87 88 88 88 89 89 90 93 93 93 94 95 96 96 97 97 98 98 
0 0 0 1 1 1 7 8 8 10 10 10 11 13 14 17 18 20 20 21 24 24 25 25 26 29 29 30 31 32 32 33 33 35 35 35 36 36 60 57 59 59 59 39 44 38 41 44 47 49 55 50 46 42 55 60 55 61 52 36 59 38 61 61 64 64 64 66 71 71 71 71 76 76 78 78 80 83 85 85 85 86 87 88 88 88 89 89 90 93 93 93 94 95 96 96 97 97 98 98 
0 0 0 1 1 1 7 8 8 10 10 10 11 13 14 17 18 20 20 21 24 24 25 25 26 29 29 30 31 32 32 33 33 35 35 35 36 36 36 57 59 59 59 39 44 38 41 44 47 49 55 50 46 42 55 60 55 38 52 60 59 61 61 61 64 64 64 66 71 71 71 71 76 76 78 78 80 83 85 85 85 86 87 88 88 88 89 89 90 93 93 93 94 95 96 96 97 97 98 98 
0 0 0 1 1 1 7 8 8 10 10 10 11 13 14 17 18 20 20 21 24 24 25 25 26 29 29 30 31 32 32 33 33 35 35 35 36 36 36 38 59 59 59 39 44 57 41 44 47 49 55 50 46 42 55 59 55 38 52 60 60 61 61 61 64 64 64 66 71 71 71 71 76 76 78 78 80 83 85 85 85 86 87 88 88 88 89 89 90 93 93 93 94 95 96 96 97 97 98 98 
0 0 0 1 1 1 7 8 8 10 10 10 11 13 14 17 18 20 20 21 24 24 25 25 26 29 29 30 31 32 32 33 33 35 35 35 36 36 36 38 38 59 59 39 44 57 41 44 47 49 55 50 46 42 55 59 55 59 52 60 60 61 61 61 64 64 64 66 71 71 71 71 76 76 78 78 80 83 85 85 85 86 87 88 88 88 89 89 90 93 93 93 94 95 96 96 97 97 98 98 
0 0 0 1 1 1 7 8 8 10 10 10 11 13 14 17 18 20 20 21 24 24 25 25 26 29 29 30 31 32 32 33 33 35 35 35 36 36 36 38 38 39 59 52 44 57 41 44 47 49 55 50 46 42 55 59 55 59 59 60 60 61 61 61 64 64 64 66 71 71 71 71 76 76 78 78 80 83 85 85 85 86 87 88 88 88 89 89 90 93 93 93 94 95 96 96 97 97 98 98 
0 0 0 1 1 1 7 8 8 10 10 10 11 13 14 17 18 20 20 21 24 24 25 25 26 29 29 30 31 32 32 33 33 35 35 35 36 36 36 38 38 39 41 52 44 57 59 44 47 49 55 50 46 42 55 59 55 59 59 60 60 61 61 61 64 64 64 66 71 71 71 71 76 76 78 78 80 83 85 85 85 86 87 88 88 88 89 89 90 93 93 93 94 95 96 96 97 97 98 98 
0 0 0 1 1 1 7 8 8 10 10 10 11 13 14 17 18 20 20 21 24 24 25 25 26 29 29 30 31 32 32 33 33 35 35 35 36 36 36 38 38 39 41 42 44 57 55 44 47 49 55 50 46 52 55 59 59 59 59 60 60 61 61 61 64 64 64 66 71 71 71 71 76 76 78 78 80 83 85 85 85 86 87 88 88 88 89 89 90 93 93 93 94 95 96 96 97 97 98 98 
0 0 0 1 1 1 7 8 8 10 10 10 11 13 14 17 18 20 20 21 24 24 25 25 26 29 29 30 31 32 32 33 33 35 35 35 36 36 36 38 38 39 41 42 44 57 55 44 47 49 55 50 46 52 55 59 59 59 59 60 60 61 61 61 64 64 64 66 71 71 71 71 76 76 78 78 80 83 85 85 85 86 87 88 88 88 89 89 90 93 93 93 94 95 96 96 97 97 98 98 
0 0 0 1 1 1 7 8 8 10 10 10 11 13 14 17 18 20 20 21 24 24 25 25 26 29 29 30 31 32 32 33 33 35 35 35 36 36 36 38 38 39 41 42 44 44 55 55 47 49 55 50 46 52 57 59 59 59 59 60 60 61 61 61 64 64 64 66 71 71 71 71 76 76 78 78 80 83 85 85 85 86 87 88 88 88 89 89 90 93 93 93 94 95 96 96 97 97 98 98 
0 0 0 1 1 1 7 8 8 10 10 10 11 13 14 17 18 20 20 21 24 24 25 25 26 29 29 30 31 32 32 33 33 35 35 35 36 36 36 38 38 39 41 42 44 44 46 55 47 49 55 50 52 55 57 59 59 59 59 60 60 61 61 61 64 64 64 66 71 71 71 71 76 76 78 78 80 83 85 85 85 86 87 88 88 88 89 89 90 93 93 93 94 95 96 96 97 97 98 98 
0 0 0 1 1 1 7 8 8 10 10 10 11 13 14 17 18 20 20 21 24 24 25 25 26 29 29 30 31 32 32 33 33 35 35 35 36 36 36 38 38 39 41 42 44 44 46 47 52 49 55 50 55 55 57 59 59 59 59 60 60 61 61 61 64 64 64 66 71 71 71 71 76 76 78 78 80 83 85 85 85 86 87 88 88 88 89 89 90 93 93 93 94 95 96 96 97 97 98 98 
0 0 0 1 1 1 7 8 8 10 10 10 11 13 14 17 18 20 20 21 24 24 25 25 26 29 29 30 31 32 32 33 33 35 35 35 36 36 36 38 38 39 41 42 44 44 46 47 49 52 50 55 55 55 57 59 59 59 59 60 60 61 61 61 64 64 64 66 71 71 71 71 76 76 78 78 80 83 85 85 85 86 87 88 88 88 89 89 90 93 93 93 94 95 96 96 97 97 98 98 
0 0 0 1 1 1 7 8 8 10 10 10 11 13 14 17 18 20 20 21 24 24 25 25 26 29 29 30 31 32 32 33 33 35 35 35 36 36 36 38 38 39 41 42 44 44 46 47 49 50 50 55 55 55 57 59 59 59 59 60 60 61 61 61 64 64 64 66 71 71 71 71 76 76 78 78 80 83 85 85 85 86 87 88 88 88 89 89 90 93 93 93 94 95 96 96 97 97 98 98 

对于每一个输入，总有一个重写值，但如果我很幸运，该值是由重复覆盖，那么它的排序。但这并非总是如此。

我该如何解决这个问题？

Answer 1

由于@Bob__指出，该程序将错误的事情时，子阵列中的一个的最大元素出现在第一位置（除非最小的元素也出现在最后位置）。看起来，这个错误是忠实地从引用作者的伪代码中复制出来的，而这个伪代码似乎与那篇不太令人印象深刻的论文相同。由于他们对具体复杂性的分析是基于它们的伪代码，所以它的细节也被认为是有问题的，尽管算法比简单选择排序更快的事实是毫无疑问的。

在任何情况下，我宁愿不同的编写代码的交换部分：

// swap the maximum and minimum elements into place, handling 
// a bit of trickiness when one (or both) of the extreme values 
// is at the far opposite end of the interval from where it belongs. 

int large = x[i_large]; 
int small = x[i_small]; 

if (i_small == i) { 
    if (i_large != k) { 
     // Three-way swap: move the middle element to index i_large 
     x[i_large] = x[k]; 
    } // else a straight swap of positions k and i 
} else if (i_large == k) { 
    // Three-way swap: move the middle element to index i_small 
    x[i_small] = x[i]; 
} else { 
    // Two independent swaps 
    x[i_small] = x[k]; 
    x[i_large] = x[i]; 
} 

// In all cases: 
x[k] = small; 
x[i] = large; 

这

1. 可生产正确的结果在所有情况下
2. 执行相同数量的比较作为最坏情况下的原始代码的类似部分，但可能执行较少
3. 执行与模拟部分相同数量的分配最坏情况下的原始代码，但可能执行更少

Answer 2

在你的代码，这些线路：

int large = x[i_large]; 
int small = x[i_small]; 
x[i_large] = x[i]; // if k == i_large ==> x[k] = x[i]; or x[i_large] = x[i_small]; 
x[i_small] = x[k]; // and i == i_small  

产生问题时k == i_large和i == i_small。为了避免这个问题用途：

int tmp = x[k]; 
x[i_large] = x[i]; 
x[i_small] = tmp;