正文

排序由浅入深(一)::选择排序2005-05-22 18:56:00

【评论】 【打印】 【字体: 】 本文链接:http://blog.pfan.cn/rickone/1229.html

分享到:

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

以某个关键字(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]重新调整为大顶堆
  }
}

阅读(15227) | 评论(2)


版权声明:编程爱好者网站为此博客服务提供商,如本文牵涉到版权问题,编程爱好者网站不承担相关责任,如有版权问题请直接与本文作者联系解决。谢谢!

评论

loading...
您需要登录后才能评论,请 登录 或者 注册