选择排序算法分析及程序示例

实例说明
　　用直接选择排序方法对数组进行排序。

实例解析

　　选择排序（ Selection Sort ）的基本思想是：每趟从待排序的记录中选出关键字最小的记录，顺序放在已排好序的子文件的最后，直到全部记录排序完毕。

　　常用的选择排序方法有直接选择排序和堆排序。

直接选择排序（ Straight Selection Sort ）

　　直接选择排序的基本思想是 n 个记录的文件的直接选择排序可经过 n-1 趟直接选择排序得到有序结果。

　　① 初始状态：无序区为 R[1..n] ，有序区为空。

　　② 第 1 趟排序
　　在无序区 R[1..n] 中选出关键字最小的记录 R[k], 将它与无序区的第 1 个记录 R[1] 交换，使 R[1..1] 和 R[2..n] 分别变为记录个数增加 1 个的新有序区和记录个数减少 1 个的新无序区。

　　③ 第 I 趟排序
　　第 I 趟排序开始时，当前有序区和无序区分别为 R[1..i-1] 和 R[i..n](1 ≤ I ≤ n-1) 。该趟排序从当前无序区中选出关键字最小的记录 R[k], 将它与无序区的第 1 个记录 R[i] 交换，使 R[1..i] 和 R[i+1..n] 分别变为记录个数增加 1 个的新有序区和记录个数减少 1 个的新无序区。

　　这样， n 个记录的文件的直接选择排序即可经过 n-1 趟直接选择排序得到有序结果。

直接选择排序的具体算法如下：

void SelectSort(SeqList R){
  int I,j,k;
  for(i=1;i<n;i++){    // 做第 I 趟排序 (1 ≤ I ≤ n-1)
    k=I;
    for(j=i+1;j<=n;j++)    // 在当前无序区 R[i..n] 中选 key 最小的记录 R[k]
      if(R[j].key<R[k].key)
        k=j;    // k 记下目前找到的最小关键字所在的位置
    if(k!=i){    // 交换 R[i] 和 R[k]
      R[0]=R[i];R[i]=R[k];R[k]=R[0];    // R[0] 做暂存单元
    }//endif
  }//endfor
}//SelectSort

程序代码—直接选择排序

#include <stdio.h>
#define MAX 255
int R[MAX];
void Select_Sort(int n){
   int i,j,k;
   for(i=1;i<n;i++){     /* 做第 I 趟排序 (1 ≤ I ≤ n-1) */
     k=i;
     for(j=i+1;j<=n;j++) /*在当前无序区R[i..n] 中选 key 最小的记录 R[k] */
       if(R[j]<R[k])
           k=j;          /* k 记下目前找到的最小关键字所在的位置 */
     if(k!=i){           /* 交换 R[i] 和 R[k] */
       R[0]=R[i];R[i]=R[k];R[k]=R[0];   /* R[0] 做暂存单元 */
     }/* endif */
   }/* endfor */
}/* end of Select_Sort */

void main(){
   int i,n;
   clrscr();
   puts("Please input total element number of the sequence:");
   scanf("%d",&n);
   if(n<=0 || n>MAX){
     printf("n must more than 0 and less than %d.\n",MAX);
     exit(0);
   }
   puts("Please input the elements one by one:");
   for(i=1;i<=n;i++)
      scanf("%d",&R[i]);
   puts("The sequence you input is:");
   for(i=1;i<=n;i++)
      printf("%4d",R[i]);
   Select_Sort(n);
   puts("\nThe sequence after select_sort is:");
   for(i=1;i<=n;i++)
      printf("%4d",R[i]);
   puts("\n Press any key to quit…");
   getch();
}

归纳注释

　　关键字比较次数：无论文件初始状态如何，在第 I 趟排序中选出最小关键字的记录，需做 n-I 次比较，因此，总的比较次数为 n(n-1)/2=O(n^2 )。

　　记录的移动次数：当初始文件为正序时，移动次数为 0。文件初态为反序时，每趟排序均要执行交换操作，总的移动次数取最大值 3(n-1)。直接选择排序的平均时间复杂度为 O(n^2 )。

　　直接选择排序是一个就地排序。

　　稳定性分析：直接选择排序是不稳定的，反例比如 [2,2,1]。