首页 > 代码库 > 选择排序

选择排序

算法描述:

   在一个长度为N的无序数组中,第一趟遍历N个数据,找出其中最小的数值与第一个元素交换。第二趟遍历剩下的N-1个数据,找出最小的数值与第二个元素交换......第N-1趟遍历剩下的2个数据,找出其中最小的数据与第N-1个数据交换。排序结束。

第二趟遍历: 12  20  80  91  56

第三趟遍历: 12  20  56  91  80

第四趟遍历: 12  20  56  80  91

 

算法分析:

  平均时间复杂度:O(n2)

  空间复杂度:O(1)  (用于交换和记录索引)

  稳定性:不稳定 (比如序列【5, 5, 3】第一趟就将第一个[5]与[3]交换,导致第一个5挪动到第二个5后面)

 

算法实现:

 1 void DataSwap( int *a1, int *a2 )
 2 {
 3     int temp;
 4     temp = *a1;
 5     *a1 = *a2;
 6     *a2 = temp;
 7 }
 8 
 9 void SelectionSort( int *pDataArray, int iDataNum )
10 {
11     int min;
12     int index;
13     
14     for( int i = 0; i < iDataNum; ++i )
15     {
16         min = pDataArray[i];
17         index = i;
18         for( int j = i + 1; j < iDataNum; ++j )
19         {
20             if( min > pDataArray[j] )
21             {
22                 index = j;
23                 min = pDataArray[j];
24             }
25         }
26         if( i != index )
27             DataSwap( &pDataArray[index],                 
28 
29                                           &pDataArray[i]);
30     }
31 }
View Code