9.4 选择类排序法

选择排序的基本思想是：每一趟在n-i+1（i=1，2，…n-1）个记录中选取关键字最小的记录作为有序序列中第i个记录。我们主要介绍简单选择排序、树型选择排序和堆排序。

   简单选择排序

简单选择排序的基本思想：第i趟简单选择排序是指通过n-i次关键字的比较，从n-i+1个记录中选出关键字最小的记录，并和第i个记录进行交换。共需进行i-1趟比较，直到所有记录排序完成为止。例如：进行第i趟选择时，从当前候选记录中选出关键字最小的k号记录，并和第i个记录进行交换。图9.5给出了一个简单选择排序示例，说明了前三趟选择后的结果。图中大括号内为当前候选记录，大括号外为当前已经排好序的记录。

 

 

　 　　　　　｛  48　     62         35         77         55         14         35         98　｝

  

 

 

 

                                     i                                                                    k

 

　 　　　　　    14　 ｛  62         35         77         55          48         35          98　｝

 

 

 

                                                  i            k

 

　 　　　　　   14　        35    ｛  62         77         55          48         35          98　｝

                                                       k

　 　　　　　   14　        35         35     ｛ 77         55          48         62          98　｝

 

 

 

 

 

                                                                             i                            k

 

 

图9.5  选择排序示例

 

 

简单选择排序的算法具体描述如下：

 

void  SelectSort(RecordType r[], intlength)

/*对记录数组r做简单选择排序，length为数组的长度*/

{

    n=length;

for ( i=1 ; i<=n－１; ++i) 

{

k=i；

for ( j=i+1 ; j<=n ; ++j) 

 if(r[j].key < r[k].key )  k=j；

if ( k!=i)

  { x= r[i]； r[i]= r[k]； r[k]=x; }

}

 

} /* SelectSort  */

 

算法9.8 简单选择排序

 

简单选择排序算法分析：在简单选择排序过程中，所需移动记录的次数比较少。最好情况下，即待排序记录初始状态就已经是正序排列了，则不需要移动记录。最坏情况下，即待排序记录初始状态是按逆序排列的，则需要移动记录的次数最多为3（n-1）。简单选择排序过程中需要进行的比较次数与初始状态下待排序的记录序列的排列情况无关。当i=1时，需进行n-1次比较；当i=2时，需进行n-2次比较；依次类推，共需要进行的比较次数是 =(n-1)+(n-2)+…+2+1=n(n-1)/2，即进行比较操作的时间复杂度为O(n²)。