8.3 选择类排序
8.3 选择类排序
选择排序的基本方法是：每步从待排序的记录中选出关键字最小的记录，顺序放在已排序的记录序列的最后，直到全部排完为止。本节介绍简单选择排序、堆排序和树形选择排序。
8.3.1 简单选择排序
简单选择排序的过程是：每一趟排序在n-i-1（i=1，2，…，n-1）个记录中选取关键字最小的记录，并和第i个记录进行交换。
简单选择排序（Selection Sort）首先在所有的数据中挑选一个最小的记录放在第一个位置（因为由小到大排序），再从第二个开始挑选一个最小的记录放在第二个位置，……，一直下去。假设有n个记录，则最多需要n-1次对调，以及n(n-1)/2次比较。
例如，有一个含有7个记录的序列，关键字分别为（48,36,65,97,15,27,48），则如图8-6给出了每次进行选择和交换后的记录排列情况。其中方括号内表示待排序序列，方括号前表示已排序序列。
图8-6 简单选择排序过程示例
简单选择排序算法如下：
void SelectSort(LineList R[ ],int n)
{
int i,j,k;
LineList tmp;
for(i=0;i<n-1;i++)
{
k=i;
for(j=i+1;j<n;j++)
if(R[j].key<R[k].key)
k=j; /*用k指出每趟在无序区段的最小元素*/
tmp=R[i]; /*将R[k]与R[i]交换*/
R[i]=R[k];
R[k]=tmp;
}
}
用这种方法排序，其关键字的比较次数与各元素原来的排列顺序无关。第1次选择（i=0）比较n-1次，第2次选择（i=1）比较n-2次，……，第n-1次选择（i=n-2）比较1次，总的比较次数为
次。但元素的移动次数和初始排列顺序有关，如果R[0..n-1]原来就是从小到大排列的，就不需要移动；如果每次选择都要进行交换，移动次数将达到最大值，即3(n-1)次。因此，算法的执行时间为O(n2)。
简单选择排序是不稳定的。
8.3.2 堆排序
堆（Heap）是一个二叉树，其特性是每一个父节点的数据都比它的两个子节点大或相等（称为大根堆，如果是进行从大到小的排序，则堆中每个节点的关键字都不大于其孩子节点的关键字，称为小根堆）。图8-7（a）符合Heap的定义，而图8-7（b）不符合。
假设将8-7（a）以数组来表示，则A[1]=39，A[2]=25，A[3]=28，A[4]=21，A[5]=12。可以看出39的子节点25、28分别存于A[2]、A[3]中，25的子节点21、12，分别存于A[4]、A[5]。从上述可知，对于数组的任一位置i，它的父节点是i/2。或者对于任一节点j，其两个子节点分别是2j、2j+1。假使2j大于总节点数n，则左子节点不存在；若2j+1大于n，则右子节点不存在。图8-7（a），若将25和28互换，它还是一棵Heap，因此同组数据所决定的Heap不是唯一的。
例如，有10个数据27，7，80，5，67，18，62，24，58，25，若用数组表示，则A[1]=27，A[2]=7，A[3]=80，A[4]=5，……，A[10]=25，用二叉树表示如图8-8所示。
（a）符合堆定义 （b）不符合堆定义
图8-7 符合堆定义及不符合堆定义 图8-8 用二叉树表示的数列
如何将图8-8变成Heap的形态呢？
方法是先求出小于n/2的最大整数，然后从该整数至1的节点与其两个子节点中最大的数相比，若大于则对调，小于则不必对调，此种方法最多只有一次会与其子节点对调。读者可从第2个节点依次与其父节点相比时可能发生的对调次数了解哪种方法较快。其转变步骤如下。
从A[4]=5开始，因为A[10]=25<A[5]=67，所以不需要交换。
A[4]=5，其最大子节点A[8]=58，因为58>5，所以将A[4]与A[8]对调，如图8-9所示。
A[3]=80与最大子节点A[7]=62相比，因为80>62，所以不需要调换。
A[2]=7，由于其小于A[5]=67，所以A[2]与A[5]对调，然后A[5]又比A[10]小再调换，如图8-10所示。
图8-9 A[4]与A[8]交换后的二叉树示意图 图8-10 A[5]与A[2]、A[10]交换后的二叉树示意图
A[1]=27，小于A[3]=80，所以A[1]与A[3]对调，然后A[3]又比A[7]小再做调换，所以二叉树变为如图8-11所示。
不难看出已经变成Heap了，第1个数据80最大，此时80与第10个数据7对调，对调之后，最后一个数据就固定不动了，下面调整时数据量已减少1个。完成了将二叉树变为一棵树Heap之后，也可以利用上述方法继续调整。可是这种方法会进行很多不必要的比较，因为除第1个数据外，其余的数据都相同，因此可以先令第一个节点为父节点，然后比较左、右子节点，看哪一个大，若右子节点大，则只要调整右半部即可；反之，调整左半部（因为不需调整的那半部分已符合Heap规则了）。
此时，A[1]=80、A[2]=67、A[3]=62、A[4]=58、A[5]=25、A[6]=18、A[7]=27、A[8]=5、A[9]=24、A[10]=7，当i=1时，根节点A[1]与A[10]对调；i=2，根节点与A[9]对调，依此类推。因此i=1时原先堆变成如图8-12所示。
图8-11 A[3]与A[1]、A[7]交换后的二叉树示意图 图8-12 输出80后的二叉树示意图
|
图8-13 67和62交换后的二叉树示意图 |
[i=2]：承i=1，先将根节点与A[9]对调，并输出67；其情形如图8-14所示。
[i=3]：承i=2，先将根节点与A[8]对调，然后输出62，其情形如图8-15所示。
[i=4]：承i=3，先将根节点与A[7]对调，然后输出58，其情形如图8-16所示。
[i=5]：承i=4，先将根节点与A[6]对调，然后输出27，其情形如图8-17所示。
62与7对调，
然后调整右半部
…
图8-14 62与7交换，并输出67后的二叉树示意图
58与5对调，
然后调整左半部
…
图8-15 58与5交换，并输出62后的二叉树示意图
27与7对调，
然后调整左半部
…
图8-16 27与7交换，并输出58后的二叉树示意图
25与7对调，
然后调整左半部
…
图8-17 25与7交换，并输出27后的二叉树示意图
[i=6]：承i=5，先将根节点与A[5]对调，然后输出25，其情形如图8-18所示。
24与5对调，
然后调整左半部
…
图8-18 24与5交换，并输出25后的二叉树示意图
[i=7]：承i=6，先将根节点与A[4]对调，然后输出24，其情形如图8-19所示。
18与5对调，
然后调整右半部
…
图8-19 18与5交换，并输出24后的二叉树示意图
[i=8]：承i=7，先将根节点与A[3]对调，然后输出18，此时情形如图8-20所示。
7与5对调，
…
图8-20 5与7交换，并输出18后的二叉树示意图
[i=9]：承i=8先将根节点与A[2]对调，然后输出7，此时情形如下：
只剩下节点5，再将其输出。
此时已全部排序完成，顺序输出为80，67，62，58，27，25，24，18，7，5。
假如利用Heap Sort处理由小至大的排序，则需利用一个堆栈，将每次的根节点放入堆栈中，最后再将堆栈的数据一一弹出。反之，若是处理由大至小的排序，则需利用队列加以处理。
堆排序的程序实例如下：
/*堆排序*/
#include <stdio.h>
void adjust(int,int);
int data[11]={0,75,23,98,44,57,12,29,64,38,82};
void main()
{
int i,k,temp;
printf("\n<<Heap sort>>\n");
printf("\nNumber : ");
for(k=1;k<=10;k++)
printf("%d ",data[k]);
puts("");
for(k=0;k<60;k++) printf("-");
for(i=10/2;i>0;i--)
adjust(i,10);
printf("\nHeap :");
for(k=1;k<=10;k++)
printf("%d ",data[k]);
for(i=9;i>0;i--)
{
temp=data[i+1];
data[i+1]=data[1];
data[1]=temp; /*将根节点和最后的节点交换*/
adjust(1,i); /*再重新调整为堆树*/
printf("\nAccess : ");
for(k=1;k<=10;k++)
printf("%d ",data[k]);
}
puts("");
for(k=0;k<60;k++)printf("-");
printf("\nSorting: ");
for(k=1;k<=10; k++)
printf("%d ",data[k]);
}
void adjust(int i,int n) /*将数据调整为堆树*/
{
int j,k,done=0;
k=data[i];
j=2*i;
while((j<=n) && (done==0))
{
if((j<n) && (data[j]<data[j+1])) j++;
if(k>=data[j]) done=1;
else
{
data[j/2]=data[j];
j*=2;
}
}
data[j/2]=k;
}
以上程序输出结果为：
<< Heap sort >>
Number : 75 23 98 44 57 12 29 64 38 82
------------------------------------------------------------
Heap : 98 82 75 64 57 12 29 44 38 23
Access : 82 64 75 44 57 12 29 23 38 98
Access : 75 64 38 44 57 12 29 23 82 98
Access : 64 57 38 44 23 12 29 75 82 98
Access : 57 44 38 29 23 12 64 75 82 98
Access : 44 29 38 12 23 57 64 75 82 98
Access : 38 29 23 12 44 57 64 75 82 98
Access : 29 12 23 38 44 57 64 75 82 98
Access : 23 12 29 38 44 57 64 75 82 98
Access : 12 23 29 38 44 57 64 75 82 98
------------------------------------------------------------
Sorting: 12 23 29 38 44 57 64 75 82 98
在堆排序过程中，关键字的比较次数等于初始建堆所需比较次数与每次调整新堆所需比较次数之和。堆排序在最坏情况下所需的比较次数不超过O(nlog2n)，显然，元素的移动次数也不超过O(nlog2n)。堆排序是不稳定的。
8.3.3 树形选择排序
1．树形选择排序的基本思路
树形选择排序（TreeSelectionSort）又称锦标赛排序（TournamentSort），是一种按照锦标赛的思想进行选择排序的方法。其基本方法为：首先将n个待排序记录序列的关键字两两比较，得到n/2个较小关键字，保留下来；再把n/2个关键字两两比较，得到n/4个较小关键字，再保留下来；反复进行上述操作，直至得到最小关键字（树根）。将此最小关键字输出，且将其原来位置改为极大数，与此位置相关部分重新（向树根方向）进行比较，选出次小关键字，保留结果。如此下去，直至全部排序完成。
例如，图8-21为一个树形选择排序的示意图，首先比较7次得到最小值5，然后将5的位置用∞代替，再对右子树进行两次比较可选出17，然后再比较一次可选出13，如此比较下去，直到全部排序结束。
图8-21 树形选择排序的示意图
2．树形选择排序的效率分析
树形选择排序相比直接选择排序在速度上有较大的提高，但其需要额外的存储空间来保存排序结果。同时，将最小关键字改为极大数后，再与兄弟节点比较属于多余操作。
树形选择排序在第一次选最小值时需比较n-1次，以后每选一个次小值都要比较log2n次，因此，总的比较次数为(n-1)+(n-1) log2n=nlog2n。记录的移动次数不超过比较次数。
因此，总的时间复杂度为O(nlog2n)。