【选择排序】
的思想是依次从待排序数列中选择最大（小）的、第二大（小）的等等，然后依次重新排列为有序数列。

以某个关键字（key）选一个最大（小）的元素出来，可以看成是一场比赛，就像拳击比赛，如果你能从第一局打到最后一局，那你就是最强者，我们选出这个最强者的过程就是选择的过程，选出来之后，将它标记，然后再从剩下的选手中以同样的方法（分治）选出第二强的，依次下去，直到只剩一个选手（边界）为止。这就是选择排序的全部思想方法。

①直接打擂的方式：（直接选择排序法）
直接选择排序法的算法是这样的，首先选出前n个元素中的最小（大）者，如果这个最小（大）者不是第1个元素，则与第1个元素交换，然后以同样的方法对付后n-1个元素（分治），直到处理的元素只剩一个，即得到有序序列。它和冒泡排序法很类似，不同的是冒泡排序法进行了更多次的交换，而有些交换是不必要的，这使得冒泡排序法是不稳定的，而直接选择排序法是稳定的排序法。

②锦标赛的方法：（树型选择法）
玩过拳皇游戏的人就知道这种比赛方法，实际中的比赛可以不必要打这么多次，我们可以把n个选手分成n/2组，假定n=8，先分成4组，每组两人，两个人打一局，这样可以产生4个胜者，再将这4个人分2组，每组同样两人，各自再打一局，这样可以产生2个胜者，同样再做一次就能产生冠军。这样做的好处是强者可以只打几场就能坐上冠军的宝座，不像前一种方法，冠军要跟其它的人都打一场才能确定（当然，这是最糟的情况）。但是树型选择法最大的缺点是需要的存储空间要大，要建一个败者树，对n很大的情况不太理想。

③堆排序：
将前一种方法进一步改进，使得在O(1)的空间复杂度上就能完成的选择排序法，就是大名鼎鼎的“堆排序法”。堆是一个线性表，下标从1开始取，且满足：nk>=max{n2k,n2k+1}或者nk<=min{n2k,n2k+1}，前者称为大顶堆，后者称为小顶堆。这样看似乎不太明白，我们把堆转换成完全二叉树，它的特点就相当显然了。

【完全二叉树】
是这样一棵二叉树，我们以堆中的元素，从头取，先取1个，做为根，再取2个，做为它的左右子结点，再取4个做为下一层的子结点，依次下去就构成完全二叉树。它的前n-1层（n是它的总层数，称为深度）是一棵满二叉树（即所有非子叶的结点的的度都为2，饱满的意思），第n层的结点靠左对齐。

这样就可以简单的得到结点之间的关系，设结点的序号为k，那它的左孩子序号为2k，右孩子序号为2k+1，这样一来，堆就对应这样一棵完全二叉树：它的根结点大于（小于）左右子树中所有元素，并且左右子树也有这样的性质。

那么堆排序的关键问题就是“如何建堆？”因为从堆的特点看出，它的根结点就是“冠军”，可以直接选择，但是选取之后如何再构建堆？一开始又如何建堆呢？

【算法】
是这样实现的：因为n/2之后的结点已经是堆，只要从这点开始向前调节，将它与它的左右孩子中最大（小）的比较，如果比它还大（小）则不用往后移，这点即是它的位置，否则将它和那个孩子子交换，依次下去，直到这个结点确定了位置，然后再向前调整，直到根部。

void HeapAdjust(SqList &H,int s,int m)
{
//已知H.elemword[s..m]中除H.elemword[s]之外均满足堆的定义,本函数调整H.elemword[s]
//使H.elemword[s..m]成为一个大顶堆
  int j,rc;
  rc=H.elemword[s];
  for(j=2*s;j<=m;j*=2) //沿关键字叫大的结点向下筛选
  {
     if(j<m&&H.elemword[j]<H.elemword[j+1]) ++j; //j为关键字较大的记录的下标
     if(rc>=H.elemword[j]) break; //rc应插入在位置s上
     H.elemword[s]=H.elemword[j];
     s=j;
  }
  H.elemword[s]=rc; //插入
}
void HeapSort(SqList &L)
{
//对顺序表L做堆排序。
  int i,j,t;
  for(i=L.length/2;i>0;--i) //把L.elemword[1..L.length]建成大顶堆
    HeapAdjust(L,i,L.length);
  for(i=L.length;i>1;--i)
  {
    Swap(L.elemword[1],L.elemword[i]); //将堆顶记录和当前未经排序子序列L.elemword[1..i] 中的最后一个记录相互交换
    HeapAdjust(L,1,i-1); //将L.r[1..i-1]重新调整为大顶堆
  }
}

评论