数据结构与算法设计PPT (46).pdf

《数据结构与算法设计PPT (46).pdf》由会员分享，可在线阅读，更多相关《数据结构与算法设计PPT (46).pdf（28页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第9章 排序9.5 基于选择的排序选择排序2021/2/242选择排序的基本思想是：每一趟(例如第i趟，i=0,1,n-2)在后面n-i个待排序对象中选出关键码最小的对象,作为有序对象序列的第i个对象。待到第n-2 趟作完，待排序对象只剩下1个元素，排序结束。直接选择排序直接选择排序是一种简单的排序方法，基本步骤是：(1)在一组对象vivn-1中选择具有最小关键码的对象；(2)若它不是这组对象中的第一个对象，则将它与这组对象中的第一个对象对调；(3)在这组对象中剔除这个具有最小关键码的对象，在剩下的对象vi+1vn-1中重复执行第(1)、(2)步，直到剩余对象只有一个为止。直接选择排序算法的实

2、现2021/2/244template void SelectSort(datalist&list)for(int i=0;i list.CurrentSize-1;i+)SelectExchange(list,i);template void SelectExchange(datalist&list,const int i)int k=i;for(intj=i+1;j list.CurrentSize;j+)if(list.Vectorj.getKey()list.Vectork.getKey()k=j;/记住当前具最小关键码的对象/选择结束后进行交换选择结束后进行交换if(k!=i)/对换

3、到第i个位置Swap(list.Vectori,list.Vectork);2021/2/24621254925*16080 1 2 3 4 52125*i=0492516251608490825*4921i=1i=2081625*2521初始最小者 08交换21,08最小者 16交换25,16最小者 21交换49,214925*0 1 2 3 4 525*i=42516084925*4921结果i=308162521最小者 25*无交换最小者 25无交换25211608各趟排序后的结果0 1 2 3 4 5160825*492125i=1时选择排序的过程i kj 49250825*1621i

4、 kj 49 2525*2549250825*16210 1 2 3 4 5i kj 21 16k 指示当前序列中最小者2021/2/2490825*211625i kj 16 2549算法性能分析 直接选择排序的关键码比较次数与对象的初始排列无关。第i趟选择具有最小关键码对象所需的比较次数总是n-i-1 次，此处假定整个待排序对象序列有n 个对象。因此，总的关键码比较次数为-=-=-=20211ninninKCN)()(对象的移动次数与对象序列的初始排列有关。当这组对象的初始状态是按其关键码从小到大有序的时候，对象的移动次数为 0，达到最少。最坏情况是每一趟都要进行交换，总的对象移动次数为为

5、3(n-1)。直接选择排序是一种不稳定的排序方法。算法性能分析锦标赛排序(Tournament Tree Sort)锦标赛排序与体育比赛时的淘汰赛类似。首先取得n 个对象的关键码，进行两两比较，得到 n/2 个比较的优胜者(关键字小者)作为第一步比较的结果保留下来。然后对这 n/2 个对象再进行关键字的两两比较，如此重复，直到选出一个关键码最小的对象为止。08Winner 2108086325*2121254925*160863tree7 tree8 tree9 tree10 tree11 tree12 tree13 tree14锦标赛排序树例子下面是对象排列的初始状态，相当于一棵满二叉树的叶

6、结点，存放的是所有参加排序的对象的关键码。胜者树的概念 每次两两比较的结果是把关键码小者作为优胜者上升到双亲结点，称这种比赛树为胜者树。位于最底层的叶结点叫做胜者树的外结点，非叶结点称为胜者树的内结点。每个结点除了存放对象的关键字data外，还存放了此对象是否要参选的标志Active和此对象在满二叉树中的序号index。胜者树最顶层是树的根，表示最后选择出来的具有最小关键码的对象。08Winner(胜者)2108086325*2121254925*160863tree7 tree8 tree9 tree10 tree11 tree12 tree13 tree14形成初始胜者树（最小关键码上升到

7、根）a0关键码比较次数:6 16Winner(胜者)2116166325*2121254925*1663tree7 tree8 tree9 tree10 tree11 tree12 tree13 tree14输出冠军并调整胜者树后树的状态a1关键码比较次数:2 21Winner(胜者)21636325*2121254925*63tree7 tree8 tree9 tree10 tree11 tree12 tree13 tree14输出亚军并调整胜者树后树的状态a2关键码比较次数:2 25Winner(胜者)25636325*25254925*63tree7 tree8 tree9 tree10

8、 tree11 tree12 tree13 tree14输出第三名并调整胜者树后树的状态输出第三名并调整胜者树后树的状态a3关键码比较次数关键码比较次数:2:2 25*Winner(胜者)25*636325*4925*63tree7 tree8 tree9 tree10 tree11 tree12 tree13 tree14输出第四名并调整胜者树后树的状态a4关键码比较次数:2 63Winner(胜者)636363tree7 tree8 tree9 tree10 tree11 tree12 tree13 tree14全部比赛结果输出时树的状态a6关键码比较次数:2 胜者树数据结点类的定义tem

9、plate class DataNodepublic:Type data;/数据值int index;/结点在满二叉树中顺序号int active;/参选标志：=1,参选,=0,不参选template void TournamentSort(Typea,int n)DataNode*tree;DataNode item;锦标赛排序算法的实现intbottomRowSize=PowerOfTwo(n);/乘幂值intTreeSize=2*bottomRowSize-1;/总结点个数intloadindex=bottomRowSize-1;/内结点个数tree=newDataNodeTreeSiz

10、e;intj=0;/从a 向胜者树外结点复制数据for(int i=loadindex;i TreeSize;i+)treei.index=i;if(j n)treei.active=1;treei.data=aj+;elsetreei.active=0;锦标赛排序算法的实现i=loadindex;/进行初始比较选择最小的项进行初始比较选择最小的项while(i)j=i;while(j 2*i)if(!treej+1.active|/胜者送入双亲treej.data=treej+1.data)tree(j-1)/2=treej;else tree(j-1)/2=treej+1;j+=2;i=(

11、i-1)/2;/i 退到双亲,直到 i=0为止 锦标赛排序算法的实现for(i=0;i n-1;i+)/处理其它n-1个数据ai=tree0.data;/送出最小数据treetree0.index.active=0;/失去参选资格UpdateTree(tree,tree0.index);/调整an-1=tree0.data;锦标赛排序算法的实现2021/2/2425template void UpdateTree(DataNode*tree,int i)if(i%2=0)tree(i-1)/2=treei-1;/i偶数,对手左结点elsetree(i-1)/2=treei+1;/i奇数,对手右

12、结点i=(i-1)/2;/向上调整锦标赛排序中树的调整算法的实现while(i)/直到i=0if(i%2=0)j=i-1;elsej=i+1;if(!treei.active|!treej.active)if(treei.active)tree(i-1)/2=treei;/i可参选,i上else tree(i-1)/2=treej;/否则,j上else/两方都可参选if(treei.data treej.data)tree(i-1)/2=treei;/关键码小者上else tree(i-1)/2=treej;i=(i-1)/2;/i上升到双亲锦标赛排序中树的调整算法的实现锦标赛排序算法性能分析

13、 锦标赛排序构成的树是满的完全二叉树，其深度为 log2(n+1)，其中n 为待排序元素个数。除第一次选择具有最小关键码的对象需要进行n-1 次关键码比较外，重构胜者树选择具有次小、再次小关键码对象所需的关键码比较次数均为O(log2n)。总关键码比较次数为O(nlog2n)。对象的移动次数不超过关键码的比较次数，所以锦标赛排序总的时间复杂度为O(nlog2n)。这种排序方法虽然减少了许多排序时间，但是使用了较多的附加存储。如果有n 个对象，必须使用至少 2n-1 个结点来存放胜者树。最多需要找到满足 2k-1 n 2k 的k，使用 2*2k-1 个结点。每个结点包括关键码、对象序号和比较标志三种信息。锦标赛排序是一个稳定的排序方法。锦标赛排序算法性能分析