排序算法——直接选择排序

一、直接选择排序的思想

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

1、 初始状态：无序区为array[1…n]，有序区为空；

2、 第一趟排序：

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

……..

3、第i趟排序

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

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

二、C代码实现

1. #include "stdio.h"
   
2. /*
   
3. * 函数：choose_sort(int *array, int n)
   
4. * 功能：插入排序
   
5. * 参数：n为数组元素的个数
   
6. */
   
7. void choose_sort(int array[],int n)
   
8. {
   
9.     int i,j;
   
10.     int b,temp,num;
    
11.     for(i=0;i<n-1;i++)
    
12.     {
    
13.         temp=i;
    
14.         for(j=i+1;j<n;j++)
    
15.         {
    
16.             if(array[j]<=array[temp])//获取待排序的元素中最小的元素
    
17.             {
    
18.                 temp=j;//记录最小元素的下标
    
19.             }
    
20.         }
    
21.         if(i!=temp)
    
22.         {
    
23.             b=array[temp];
    
24.             array[temp]=array[i];
    
25.             array[i]=b;
    
26.         }
    
27.     }
    
28. }
    
29. int main(int argc,char *argv[])
    
30. {
    
31.     int array[]={3,8,4,7,1};
    
32.     choose_sort(array,5);
    
33.     for(int i=0;i<5;i++)
    
34.     {
    
35.         printf("%d ",array[i]);
    
36.     }
    
37.     printf("\n");
    
38.     return 0;
    
39. }

三、直接选择排序的时间

直接选择排序的平均时间复杂度为O(n*n)，并且是一种不稳定的排序。