选择排序算法能否像冒泡排序那样提前终止其循环？

Question

如果我不包含提前终止标志，这个程序会运行没问题，但它只需要 10 次排序就可以完全排序列表，而不是完整的 12 次。但是，当包含终止标志时，它过早地终止排序。按照逻辑，我可以看到会发生这种情况，因为在第三遍之后，数组的排序如下：

当前索引 i 为 7，没有更小的值可以与之交换，因此标志没有得到分配给它的值 1，循环终止。所以我想我的问题是，是否有可能提前突破选择排序算法并仍然完全完成排序？

#include<stdio.h>
int main()
{
     int list[13]= {23,8,4,7,22,18,39,42,5,88,16,11,3};
     int temp,min,flag;
     printf( "Before Sorting\n" );
     printf( "23 8 4 7 22 18 39 42 5 88 16 11 3\n" );

for( int i=0; i<12; i++ )
    {
        flag = 0;
        min = i;

        for( int j=i+1; j<13; j++ )
            {
                if( list[j]<list[min] )
                    {
                        flag = 1;
                        min = j  ;
                    }
            }

        if( !flag )
            break;

        temp = list[i];
        list[i]=list[min];
        list[min]=temp;

        printf( "\nAfter Pass %d.\n",i+1 );
        for( int i=0; i<13; i++ )
            printf( "%d ",list[i] );

        printf( "\n" );
    }

return 0;
}

Answer 1

冒泡排序几乎没有任何可取之处，最好的地方就是它的名字。 Donald Knuth 曾说过

the bubble sort seems to have nothing to recommend it, except a catchy name and the fact that it leads to some interesting theoretical problems

事实上，来自维基百科关于 selection sort：

Among simple average-case Θ(n²) algorithms, selection sort almost always outperforms bubble sort and gnome sort.

选择排序没有变化 - 它的运行时间不取决于排序。对于另一个具有可变运行时间的简单 O(n²) 算法，请参见 insertion sort.

Answer 2

确实可以。这是这样一个实现，

int selsort(int v[], int n){

  bool sorted = false; // v not known to be sorted
  int  i = 0;          // i smallest elements in place 

  while(!sorted){
    // find min v[i..n-1]
    // check if v[i..n-1] is sorted

    int  j   = i+1;
    int  min = i;    // position of minimum of v[i..j-1]
    sorted   = true; // v[i..j-1] sorted

    while(j<n){
      if(v[j]<v[min]) min = j;        // update min
      if(v[j]<v[j-1]) sorted = false; // update sorted
      j++;
    }

    if (!sorted){
      // place min v[i..n-1] in v[i]
      int aux = v[i];
      v[i]    = v[min];
      v[min]  = aux;      

      i++;
    }
  }

  return EXIT_SUCCESS;
}

像往常一样，在迭代 i 中，我们从 v[0..i-1] 开始，在正确的位置对数组的 i 最小元素进行排序。所以我们要找到min v[i..n-1]放在位置i。在这个变体中，当我们这样做时，我们还会检查 v[i..n-1] 是否已排序。如果它被排序，那么就没有别的事可做。

您的实施

在您的实现中，您测试有序段的方式是错误的。

if( list[j]<list[min] )
    {
        flag = 1;
        min = j  ;
    }

只要您不必更新内部循环中的最小值，您的标志就会保持在 0。因此，任何在第一个位置具有最小值的段都将被视为已排序。

选择排序算法能否像冒泡排序那样提前终止其循环？

Can a selection sort algorithm terminate from its loop early the way a bubble sort is able to?

c

flags

selection-sort