数据结构03排序课件

第三章第三章 排排 序序（Sorting）2第三章第三章 排序排序n3.1 3.1 排序的基本概念排序的基本概念n3.2 3.2 简单排序方法简单排序方法n3.3 3.3 先进法排序方法先进法排序方法n3.4 3.4 基数排序基数排序n3.5 3.5 各种排序方法的综合比较各种排序方法的综合比较3第三章第三章 排序排序n待排序数据元素（记录）的存储结构：待排序数据元素（记录）的存储结构：typedeftypedef intint KeyType KeyType /定义关键字类型为整型定义关键字类型为整型typedeftypedef structstruct KeyType key;KeyType key;/关键字项关键字项 InfoType otherinfo;InfoType otherinfo;/其他数据项其他数据项RcdType;RcdType;/记录类型记录类型n本章的排序图例只标出了记录的关键字。本章的排序图例只标出了记录的关键字。43.1 3.1 排序的基本概念排序的基本概念n3.1.1 3.1.1 排序的定义排序的定义n3.1.2 3.1.2 排序的特性排序的特性稳定性与稳定性与不稳定性不稳定性n3.1.3 3.1.3 排序的分类排序的分类n3.1.4 3.1.4 内排序的特点内排序的特点n3.1.5 3.1.5 选择排序法选择排序法53.1 3.1 排序的基本概念排序的基本概念n3.1.1 3.1.1 排序的定义排序的定义n简单定义：排序是按照关键字的简单定义：排序是按照关键字的非递减非递减或或非递增非递增顺顺序对一组记录重新进行序对一组记录重新进行整队整队（或（或排列排列）的操作。）的操作。n数学定义：假设含有数学定义：假设含有n个记录的序列为：个记录的序列为：r1,r2,rn(3-1)它们的关键字相应为它们的关键字相应为k1,k2,kn,对式对式(3-1)的记录的记录序列进行排序就是要确定序号序列进行排序就是要确定序号1,2,n的一种排列的一种排列p1,p2,pn使其相应的关键字满足如下的非递增使其相应的关键字满足如下的非递增(减减)关系：关系：kp1 kp2 kpn(3-2)也就是使式也就是使式(3-2)的记录序列重新排列成一个按关键的记录序列重新排列成一个按关键字有序的序列字有序的序列rp1 rp2 rpn(3-3)63.1 3.1 排序的基本概念排序的基本概念n3.1.2 3.1.2 排序的特性排序的特性稳定性与不稳定性稳定性与不稳定性n当待排记录中的关键字当待排记录中的关键字ki(1,2,n)都不相同时，则都不相同时，则任何一个记录的无序序列经排序后得到的结果是惟一任何一个记录的无序序列经排序后得到的结果是惟一的。的。n简单地说，简单地说，稳定性排序稳定性排序-数据排序过后能使值相同数据排序过后能使值相同的数据，保持原顺序中之相对位置。反之，则称为的数据，保持原顺序中之相对位置。反之，则称为“不稳定性排序不稳定性排序”。n若排序的序列中存在两个或两个以上关键字相等的若排序的序列中存在两个或两个以上关键字相等的记录时，则排序得到的记录序列的结果不惟一。记录时，则排序得到的记录序列的结果不惟一。n假设假设ki=kj(1i n,1jn,ijj)，且在排序前的序列，且在排序前的序列中中 ri 领先于领先于rj(即即ijj)。若在排序后的序列中。若在排序后的序列中ri 总是领总是领先于先于rj，则称所用的排序方法是，则称所用的排序方法是稳定稳定的；反之，若可能的；反之，若可能使排序后的序列中使排序后的序列中 rj领先于领先于ri，则称所用的排序方法是，则称所用的排序方法是不稳定不稳定的。的。73.1.2 3.1.2 排序的特性稳定性与不稳定性272716169 9（1 1）31317 724249 9（2 2）17170 01 12 23 34 45 56 67 7 排序前：排序前：7 79 9（1 1）9 9（2 2）161617172424272731310 01 12 23 34 45 56 67 7 稳定排序：稳定排序：7 79 9（2 2）9 9（1 1）161617172424272731310 01 12 23 34 45 56 67 7 不稳定排序：不稳定排序：83.1.3 3.1.3 排序的分类排序的分类n根据在排序的过程涉及的存储器不同，排序方根据在排序的过程涉及的存储器不同，排序方法可分为两类：法可分为两类：n1.1.内部排序（内部排序（Internal Sort）：在排序进行的过程）：在排序进行的过程中不使用计算机外部存储器的排序过程。中不使用计算机外部存储器的排序过程。n选择排序选择排序n插入排序插入排序n起泡排序起泡排序n快速排序快速排序n归并排序归并排序n堆排序堆排序n基数排序基数排序n2.外部排序（外部排序（External Sort）：在排序进行的过程）：在排序进行的过程中需要对外存进行访问的排序过程。中需要对外存进行访问的排序过程。93.1.4 3.1.4 内排序的特点内排序的特点n 待排序记录序列的存储结构：待排序记录序列的存储结构：const int const int MAXSIZE=20 MAXSIZE=20 /定义最大顺序表的长度定义最大顺序表的长度typedeftypedef structstruct RcdType rMAXSIZE+1;RcdType rMAXSIZE+1;/r0/r0闲置或作为闲置或作为“哨兵哨兵”intint length;length;/顺序表的真正长度顺序表的真正长度SqList;SqList;/顺序表类型顺序表类型n 内部排序的过程是一个逐步扩大记录的有序序列的过程。通常内部排序的过程是一个逐步扩大记录的有序序列的过程。通常在排序的过程中，参与排序的记录序列可划分两个区域：有序序在排序的过程中，参与排序的记录序列可划分两个区域：有序序列区和无序序列区，其中有序序列区的的记录已按关键字非递减列区和无序序列区，其中有序序列区的的记录已按关键字非递减有序排列。有序排列。n 使有序序列中记录的数目至少增加一个的操作称为使有序序列中记录的数目至少增加一个的操作称为一趟排序一趟排序。103.1.5 选择排序法选择排序法n思想：在排序过程序中，依次从待排序的记录序列中思想：在排序过程序中，依次从待排序的记录序列中选择出关键字值最小的记录、关键字值次小的记录、选择出关键字值最小的记录、关键字值次小的记录、，并分别有序序列中的第并分别有序序列中的第1个位置、第二个位置、个位置、第二个位置、，最后剩下一个关键字值最大的记录位于序列的最后一个最后剩下一个关键字值最大的记录位于序列的最后一个位置，从而使待排序的记录序列成为按关键字值由小到位置，从而使待排序的记录序列成为按关键字值由小到大排列的的有序序列。大排列的的有序序列。有序序列有序序列 R1.i-1R1.i-1无序序列无序序列 Ri.nRi.n有序序列有序序列 R1.i-1R1.i-1RjRjRiRi有序序列有序序列 R1.iR1.i无序序列无序序列 Ri+1.nRi+1.n一趟排序后一趟排序后一趟排序开始一趟排序开始113.1.5 选择排序法选择排序法n一趟排序算法：一趟排序算法：voidvoid SelectPass(SqList&L,SelectPass(SqList&L,intint i)i)RcdType W;RcdType W;intint j,k;j,k;j=i;j=i;/j j指示无序序列中第一个记录的位置指示无序序列中第一个记录的位置 forfor(k=i+1;k=L.length;k+)(k=i+1;k=L.length;k+)if(L.rk.keyL.rj.key)j=k;if(L.rk.keyL.rj.key)j=k;/只记录位置只记录位置 ifif(i!=j)(i!=j)/交换交换RjRj和和Ri;Ri;W=L.ri;L.ri=L.rj;L.rj=W;W=L.ri;L.ri=L.rj;L.rj=W;/L.ri L.rj;L.ri L.rj;/SelectPass/SelectPass123.1.5 选择排序法选择排序法n整个算法：整个算法：voidvoid SelectSort(SqList&L)SelectSort(SqList&L)RcdType W;RcdType W;forfor(i=1;iL.length;i+)(i=1;iL.length;i+)j=i;j=i;/j j指示无序序列中第一个记录的位置指示无序序列中第一个记录的位置 forfor(k=i+1;k=L.length;k+)(k=i+1;k=L.length;k+)/找到最小记录下标找到最小记录下标 if(L.rk.keyL.rj.key)j=k;if(L.rk.keyL.rj.key)j=k;ifif(i!=j)(i!=j)/交换交换RjRj和和Ri;Ri;W=L.ri;L.ri=L.rj;L.rj=W;W=L.ri;L.ri=L.rj;L.rj=W;/for for /SelectSort/SelectSort133.1.5 选择排序法选择排序法初始状态初始状态49491 13838656549492 27676131327275252i=1i=113133838656549492 2767649491 127275252i=2i=213132727656549492 2767649491 138385252i=3i=313132727383849492 2767649491 165655252i=4i=413132727383849492 2767649491 165655252i=5i=513132727383849492 249491 1656552527676i=6i=613132727383849492 249491 1656576765252i=7i=713132727383849492 249491 1656576765252143.1.5 选择排序法选择排序法n时间复杂度：时间复杂度：O(n2)n空间复杂度：空间复杂度：O(1)n优点：优点：n算法简单；辅助空间少。算法简单；辅助空间少。n缺点：缺点：n效率低；不稳定性排序。效率低；不稳定性排序。153.2 简单排序方法简单排序方法n3.2.1 3.2.1 插入排序插入排序n3.2.2 3.2.2 起泡排序起泡排序163.2.1 插入排序插入排序n基本思想：依次将记录序列中的每一个记录插入到有序段中，使有基本思想：依次将记录序列中的每一个记录插入到有序段中，使有序段的长度不断地扩大。其具体的排序过程可以描述如下：首先将待序段的长度不断地扩大。其具体的排序过程可以描述如下：首先将待排序记录序列中的第一个记录作为一个有序段，将记录序列中的第二排序记录序列中的第一个记录作为一个有序段，将记录序列中的第二个记录插入到上述有序段中，形成由两个记录组成的有序段，再将记个记录插入到上述有序段中，形成由两个记录组成的有序段，再将记录序列中的第三个记录插入到这个有序段中，形成由三个记录组成的录序列中的第三个记录插入到这个有序段中，形成由三个记录组成的有序段，有序段，依此类推，每一趟都是将一个记录插入到前面的有序段中。依此类推，每一趟都是将一个记录插入到前面的有序段中。n假设当前欲处理第假设当前欲处理第i个记录，则将个记录，则将Ri这个记录插入到有序这个记录插入到有序R1.i-1 段段中，从而使有序序列长度增中，从而使有序序列长度增1，直到所有记录都插入到有序段中。一共，直到所有记录都插入到有序段中。一共需要经过需要经过n-1趟就可以将初始序列的趟就可以将初始序列的n个记录重新排列成按关键字值大个记录重新排列成按关键字值大小排列的有序序列。小排列的有序序列。RiRi有序序列有序序列 R1.iR1.i无序序列无序序列 Ri+1.nRi+1.n一趟排序后一趟排序后一趟排序开始一趟排序开始有序序列有序序列 R1.i-1R1.i-1无序序列无序序列 Ri.nRi.n173.2.1 插入排序插入排序6 69 93 34 46 69 93 34 46 69 96 69 93 34 43 36 69 93 36 69 94 43 34 46 69 9插入插入9 9插入插入3 3插入插入4 4起始起始183.2.1 插入排序插入排序n一趟排序算法：一趟排序算法：voidvoid InsertPass(SqList&L,InsertPass(SqList&L,intint i)i)/将将L.riL.ri插入有序的插入有序的R1.i-1R1.i-1中中 L.r0=L.ri;L.r0=L.ri;/复制为哨兵复制为哨兵 forfor(j=i-1;L.r0.keyL.rj.key;j-)(j=i-1;L.r0.keyL.rj.key;j-)L.rj+1=L.rj;L.rj+1=L.rj;/记录后移记录后移 L.rj+1=L.r0;L.rj+1=L.r0;/插入到正确位置插入到正确位置/InsertPass/InsertPass193.2.1 插入排序插入排序n整个算法：整个算法：voidvoid InsertSort(SqList&L)InsertSort(SqList&L)/将将L.riL.ri插入有序的插入有序的R1.i-1R1.i-1中中 forfor(i=2;i=L.length;i+)(i=2;i=L.length;i+)ifif(L.ri.keyL.ri-1.key)(L.ri.keyL.ri-1.key)L.r0=L.ri;L.r0=L.ri;/复制为哨兵复制为哨兵 forfor(j=i-1;L.r0.keyL.rj.key;j-)(j=i-1;L.r0.keyL.rj.key;j-)L.rj+1=L.rj;L.rj+1=L.rj;/记录后移记录后移 L.rj+1=L.r0;L.rj+1=L.r0;/插入到正确位置插入到正确位置 /InsertSort/InsertSort203.2.1 插入排序插入排序初始状态初始状态49491 138386565979776761313272749492 2i=2i=2i=3i=3i=4i=4i=5i=5i=6i=6i=7i=7i=8i=8383849491 16565979776761313272749492 2383849491 16565979776761313272749492 23838656549491 16565979776761313272749492 23838979749491 16565767697971313272749492 23838767649491 13838656576769797272749492 21313131349491 12727383865657676979749492 21313272749491 12727383897976565767649492 2131349492 2213.2.1 插入排序插入排序n时间复杂度时间复杂度n最佳状况（最佳状况（正序）正序）：O（n）n最坏状况最坏状况（逆序）：（逆序）：O(n2)n平均状况：平均状况：O(n2)n空间复杂度：空间复杂度：O(1)n优点：优点：n算法简单；稳定排序算法简单；稳定排序。n缺点：缺点：n花费较长的排序时间。花费较长的排序时间。223.2.2 3.2.2 起泡排序起泡排序n思想：通过对无序序列区中的记录进行相邻记录关键思想：通过对无序序列区中的记录进行相邻记录关键字间的字间的“比较比较”和记录位置的和记录位置的“交换交换”实现关键字较小实现关键字较小的记录向的记录向“一头一头”漂移，而关键字较大的记录向漂移，而关键字较大的记录向“另一另一头头”下沉，从而达到记录按关键字非递减顺序有序排列下沉，从而达到记录按关键字非递减顺序有序排列的目标。的目标。i i无序序列无序序列 R1.i-1R1.i-1有序序列有序序列 Ri.nRi.n一趟排序后一趟排序后一趟排序开始一趟排序开始无序序列无序序列 R1.iR1.i有序序列有序序列 Ri+1.nRi+1.n233.2.2 3.2.2 起泡排序起泡排序373796968 854548 854549696373796968 89696373754548 8969654548 83737243.2.2 3.2.2 起泡排序起泡排序n一趟排序算法：一趟排序算法：voidvoid BubblePass(SqList&L,BubblePass(SqList&L,intint i)i)RcdType W;RcdType W;/j j指示无序序列中第一个记录的位置指示无序序列中第一个记录的位置 forfor(j=1;ji;j+)(j=1;ji;j+)ifif(L.rj+1.keyL.rj.key)(L.rj+1.key1;i-)(i=L.length;i1;i-)forfor(j=1;ji;j+)(j=1;ji;j+)ifif(L.rj+1.keyL.rj.key)(L.rj+1.key1)(i1)lastExchange=1;lastExchange=1;forfor(j=1;ji;j+)(j=1;ji;j+)ifif(L.rj+1.keyL.rj.key)(L.rj+1.key=pivotkeyRhigh.key=pivotkey，则减小，则减小highhighn否则将否则将RhighRhigh移至指针移至指针lowlow所指位置所指位置n检测指针所指记录检测指针所指记录n若若Rlow.key=pivotkeyRlow.key=pivotkey，则增加，则增加lowlown否则将否则将RlowRlow移至指针移至指针highhigh所指位置所指位置n重复进行，直至重复进行，直至lowlow和和highhigh指向同一位置。指向同一位置。323.3.1 3.3.1 快速排序快速排序28284 436362 26565141455551717i ij jtemptemp2828i ii i28284 436362 26565141455551717i ij j1717j jj j1414i ii i6565j j282817174 42 2555536361414656528283636333.3.1 3.3.1 快速排序快速排序n一趟排序算法：一趟排序算法：intint Partition(RcdType R,Partition(RcdType R,intint low,low,intint high)high)intint pivotkey;pivotkey;R0=Rlow;R0=Rlow;/将枢轴放在闲置单元将枢轴放在闲置单元 pivotkey=Rlow.key;pivotkey=Rlow.key;/将枢轴的关键字放在将枢轴的关键字放在pivotkeypivotkey while(lowhigh)while(lowhigh)whilewhile(low=pivotkey)(low=pivotkey)high-;high-;/high/high往左找，比小时停止往左找，比小时停止 ifif(lowhigh)Rlow+=Rhigh;(lowhigh)Rlow+=Rhigh;/把比枢轴小的记录移到低端把比枢轴小的记录移到低端 whilewhile(lowhigh&Rlow.key=pivotkey)(lowhigh&Rlow.key=pivotkey)low+;low+;/low/low往右找，比往右找，比pivotkeypivotkey大时停止大时停止 ifif(lowhigh)Rhigh-=Rlow;(lowhigh)Rhigh-=Rlow;/把比枢轴大的记录移到高端把比枢轴大的记录移到高端 /while/while Rlow=R0;Rlow=R0;/把枢轴放在正确的位置把枢轴放在正确的位置 return(low);return(low);/返回枢轴位置返回枢轴位置/Partition/Partition343.3.1 3.3.1 快速排序快速排序n整个算法：整个算法：voidvoid QSort(RcdType R,QSort(RcdType R,intint s,s,intint t)t)/对记录序列对记录序列Rs.tRs.t进行快速排序进行快速排序 ifif(s(s11 pivotLoc=Partition(R,s,t);pivotLoc=Partition(R,s,t);/对对Rs.tRs.t进行一次划分进行一次划分 QSort(R,s,pivotLoc-1);QSort(R,s,pivotLoc-1);/对低端子序列递归排序对低端子序列递归排序 QSort(R,s,pivotLoc-1);QSort(R,s,pivotLoc-1);/对高端子序列递归排序对高端子序列递归排序 /if/if/QSort/QSortvoidvoid QuickSort(SqList&L)QuickSort(SqList&L)/对顺序表对顺序表L L进行快速排序进行快速排序 QSort(L.r,1,L.length);QSort(L.r,1,L.length);/QuickSort/QuickSort一趟快速排序示例一趟快速排序示例49491 138386565979776761313272749492 2i ij jj j272738386565979776761313272749492 2i ij ji i272738386565979776761313656549492 2i ij jj j272738381313979776761313656549492 2i ij ji i272738381313979776769797656549492 2i ij jj j27273838131349491 176769797656549492 2pivotkeypivotkey49491 1363.3.1 3.3.1 快速排序快速排序初始状态初始状态49491 138386565979776761313272749492 2一次划分一次划分2727131376767676979749492 2656549491 138381313383876767676979749492 2656549491 127271313383876767676979749492 2656549491 127271313383876767676979749492 2656549491 127271313383876767676979749492 2656549491 127271313383876767676979749492 2656549491 12727373.3.1 3.3.1 快速排序快速排序n时间复杂度：时间复杂度：n最佳状况最佳状况(当每次分割的两个区块都均匀大小时当每次分割的两个区块都均匀大小时)：O(nO(n*loglog2 2n)n)n最坏状况最坏状况(每次分割的两个区块大小相差很多时每次分割的两个区块大小相差很多时)：O(n2)n平均状况：平均状况：O(nO(n*loglog2 2n)n)n空间复杂度：空间复杂度：使用递归的深度使用递归的深度n最佳状况最佳状况:O(log:O(log2 2n)n)n最坏状况最坏状况:O(n):O(n)n平均状况：平均状况：介于介于O(logO(log2 2n)n)和和O(n)之间之间n优点：优点：n平均时间复杂度低，适用于完全随机的序列。平均时间复杂度低，适用于完全随机的序列。n缺点：缺点：n不稳定性排序不稳定性排序;空间效率低；结点顺序不好则效率低。空间效率低；结点顺序不好则效率低。383.3.2 归并排序归并排序n归并排序法是利用归并排序法是利用“归并归并”操作的一种排序方操作的一种排序方法。法。n基本思想：基本思想：n将待排序的原始记录序列将待排序的原始记录序列Rs.t中取一个中中取一个中间位置间位置(s+t)/2，先分别对子序列，先分别对子序列Rs.(s+t)/2和和R(s+t)/2+1.t进行递归的归并排序，然后进行递归的归并排序，然后进行一次归并处理。进行一次归并处理。393.3.2 归并排序归并排序n 归并排序基本操作归并排序基本操作将两个位置相邻的有序记录子序列将两个位置相邻的有序记录子序列Ri.mRi.m和和Rm+1.nRm+1.n归并为一个有序记录序列归并为一个有序记录序列RnRn，算法如，算法如下：下：voidvoid Merge(RcdType SR,RcdType TR,Merge(RcdType SR,RcdType TR,intint i,i,intint m,m,intint n)n)/对有序的对有序的Ri.mRi.m和和Ri+1.nRi+1.n归并为一个有序的归并为一个有序的RnRn forfor(j=m+1,k=i;i=m&j=n;k+)(j=m+1,k=i;i=m&j=n;k+)ifif(SRi.key=SRj.key)TRk=SRi+;(SRi.key=SRj.key)TRk=SRi+;elseelse TRk=SRj+;TRk=SRj+;/for/for whilewhile(i=m)TRk+=SRi+;(i=m)TRk+=SRi+;/将剩余的将剩余的Ri.mRi.m复制到复制到TRTR whilewhile(j=n)TRk+=SRj+;(jn/2=4（1）考虑）考虑n4n4 n8 不变不变67491382n1n2n3n4n5n6n7n88453.3.3 堆排序堆排序（2）考虑）考虑n3n3 n7 交换交换67491382n1n2n3n4n5n6n7n8267491382n1n2n3n4n5n6n7n862463.3.3 堆排序堆排序（3）考虑）考虑n2n4n2n5n2 不变不变27491386n1n2n3n4n5n6n7n89473.3.3 堆排序堆排序（4）考虑）考虑n1n1 n2 交换交换29471386n1n2n3n4n5n6n7n8769471382n1n2n3n4n5n6n7n887493.3.3 堆排序堆排序考虑考虑n4n4n8 不变不变29481376n1n2n3n4n5n6n7n879 98 86 67 71 14 42 23 3最大堆最大堆503.3.3 堆排序堆排序29481376n1n2n3n4n5n6n7n8n取出树根取出树根与最后一个节点交换与最后一个节点交换39n1n823481976n1n2n3n4n5n6n7n8928471936n1n2n3n4n5n6n7n89n1n7成堆成堆5128471936n1n2n3n4n5n6n7n893.3.3 堆排序堆排序n1n7n1n6成堆成堆8222471936n1n2n3n4n5n6n7n89827431926n1n2n3n4n5n6n7n898523.3.3 堆排序堆排序n1n6n1n5成堆成堆27431926n1n2n3n4n5n6n7n8987424431926n1n2n3n4n5n6n7n898726431924n1n2n3n4n5n6n7n8987533.3.3 堆排序堆排序n1n5n1n4成堆成堆26431924n1n2n3n4n5n6n7n89876121431924n1n2n3n4n5n6n7n8987624431921n1n2n3n4n5n6n7n89876543.3.3 堆排序堆排序n1n4n1n3成堆成堆24431921n1n2n3n4n5n6n7n898764223421941n1n2n3n4n5n6n7n89876422431941n1n2n3n4n5n6n7n898764553.3.3 堆排序堆排序n1n3n1n2成堆成堆23421941n1n2n3n4n5n6n7n8987641321421943n1n2n3n4n5n6n7n898764322411943n1n2n3n4n5n6n7n8987643563.3.3 堆排序堆排序n1n222411943n1n2n3n4n5n6n7n89876431221411943n1n2n3n4n5n6n7n898764321 12 23 34 46 67 78 89 9void HeapSort(int void HeapSort(int*heap,int index)heap,int index)int i,j,temp;int i,j,temp;for(i=index/2;i=1;i-)createHeap(heap,i,index);for(i=index/2;i=1;i-)createHeap(heap,i,index);for(i=index-1;i=1;i-)for(i=index-1;i=1;i-)heap1 heap1heapi+1;/heapi+1;/借助借助temptemp交换交换 createHeap(heap,1,i);createHeap(heap,1,i);void createHeap(int void createHeap(int*heap,int root,int index)heap,int root,int index)int i,j,temp,finish=0;int i,j,temp,finish=0;j=2 j=2*root;temp=heaproot;root;temp=heaproot;while(j=index&finish=0)while(j=index&finish=0)if(jindex)if(jindex)if(heapjheapj+1)j+;if(heapj=heapj)finish=1;if(temp=heapj)finish=1;else heapj/2=heapj;j else heapj/2=heapj;j*=2;=2;heapj/2=temp;heapj/2=temp;堆排序算法堆排序算法调用调用HeapSort(list,index);HeapSort(list,index);583.3.3 堆排序堆排序n时间复杂度：时间复杂度：O(nlog2n)n空间复杂度：空间复杂度：O(1)O(1)n优点：优点：n最坏情况下时间复杂度也仅为最坏情况下时间复杂度也仅为O(nlog2n)。n缺点：缺点：n运行时间主要耗费在建初始堆和调整堆上，运行时间主要耗费在建初始堆和调整堆上，排序数据较少时，不值得提倡。排序数据较少时，不值得提倡。593.4 3.4 基数排序基数排序n基本思想：基本思想：n基数排序：假设记录的逻辑关键字由多个关键字构基数排序：假设记录的逻辑关键字由多个关键字构成，每个关键字可能取成，每个关键字可能取r r个值，则只要从最低位关键字个值，则只要从最低位关键字起，按关键字的不同值将记录起，按关键字的不同值将记录“分配分配”到到r r个队列之后个队列之后再再“收集收集”在一起，如此重复趟，最终完成整个记录在一起，如此重复趟，最终完成整个记录序列的排序。序列的排序。“基数基数”指的是指的是r r的取值范围。的取值范围。n例：关键字为三位整数，其关键字构成是（例：关键字为三位整数，其关键字构成是（k2,k1,k0），），k2,k1,k0 的基数为的基数为10n例：关键字为例：关键字为5个字母，其关键字构成是（个字母，其关键字构成是（k4,k3,k2,k1,k0），），kj,(0=j收集收集-分配分配-收集收集基基数数排排序序示示例例7878090963633030747489899494252505056969181883830 01 12 23 34 45 56 67 78 89 910101111（a a）初始状态）初始状态3030636383837474949425250505787818180909898969690 01 12 23 34 45 56 67 78 89 910101111（c c）第一趟收集后的结果）第一趟收集后的结果0505090918182525303063636969747478788383898994940 01 12 23 34 45 56 67 78 89 910101111（e e）第二趟收集后的结果）第二趟收集后的结果30300909898969690 01 12 23 34 45 56 67 78 89 9（b b）第一趟分配后的结果）第一趟分配后的结果25250505787818187474949463638383181894940 01 12 23 34 45 56 67 78 89 9（d d）第二趟分配后的结果）第二趟分配后的结果7474787883838989636369690505090925253030需要一个临时需要一个临时的二维数组存的二维数组存放分配结果吗？放分配结果吗？610 01 12 23 34 45 56 67 78 89 9101011113.4 3.4 基数排序基数排序7878090963633030747489899494252505056969181883830 01 12 23 34 45 56 67 78 89 910101111记录数组记录数组A A计数数组（个位）计数数组（个位）（a a）初始状态和对）初始状态和对“个位数个位数”计数的结果计数的结果0 03 30 01 12 23 34 45 56 67 78 89 90 02 20 01 10 02 22 22 2计数数组累加计数数组累加1 112120 01 12 23 34 45 56 67 78 89 97 79 97 71 11 13 35 57 7记录数组记录数组B B303063638383747494942525050578781818090989896969（b b）计数器的累加结果和记录）计数器的累加结果和记录“复制复制”后的状态后的状态2 211116 6 5 54 410103 30 01 19 98 8 7 7620 01 12 23 34 45 56 67 78 89 9101011113.4 3.4 基数排序基数排序（b b）计数器的累加结果和记录）计数器的累加结果和记录“复制复制”后的状后的状态态3030636383837474949425250505787818180909898969690 01 12 23 34 45 56 67 78 89 910101111计数数组（十位）计数数组（十位）1 11 10 01 12 23 34 45 56 67 78 89 92 22 22 22 21 11 10 00 0计数数组累加计数数组累加3 312120 01 12 23 34 45 56 67 78 89 99 911117 72 24 45 55 55 5记录数组记录数组A A050509091818252530306363696974747878838389899494（c c）对）对“十位数十位数”计数、累加和记录计数、累加和记录“复制复制”后的状态后的状态记录数组记录数组B B6 610101 12 28 80 03 311117 79 95 54 4633.4 3.4 基数排序基数排序n基数排序需说明的数据结构基数排序需说明的数据结构const int const int MAX_NUM_OF_KEY=6 MAX_NUM_OF_KEY=6 /关键字项数的最大值关键字项数的最大值const int const int RADIX=10 RADIX=10 /关键字的基数关键字的基数const int const int MAXSIZE=10000MAXSIZE=10000 typedeftypedef structstruct KeysType keysMAX_NUM_OF_KEY;KeysType keysMAX_NUM_OF_KEY;/关键字数组关键字数组 InfoType otheritems;InfoType otheritems;/其他数据项其他数据项 /int bitsnum;int bitsnum;/关键字的位数关键字的位数RcdType;RcdType;/基数排序中的记录类型基数排序中的记录类型643.4 3.4 基数排序基数排序n 一趟基数排序算法：一趟基数排序算法：voidvoid RadixPass(RcdType A,RcdType B,RadixPass(RcdType A,RcdType B,intint n,n,intint i)i)/对数组对数组A A中记录关键字的中记录关键字的“第第i i位位”计数，并累计计数，并累计countcount的值的值 /将数组将数组A A中复制到数组中复制到数组B B中中 forfor(j=0;jRADIX;j+)countj=0;(j=0;jRADIX;j+)countj=0;/计数数组计数数组countcount初始化初始化 forfor(k=0;kn;k+)(k=0;kn;k+)/对关键字的对关键字的“第第i i位位”计数计数 countAk.keysi+;countAk.keysi+;forfor(j=1;jRADIX;j+)(j=1;j=0;k-)(k=n-1;k=0;k-)/从右端开始复制记录从右端开始复制记录 j=Ak.keysi;j=Ak.keysi;Bcountj-1=Ak;Bcountj-1=Ak;countj-;countj-;/for/for/RadixPass/RadixPass653.4 3.4 基数排序基数排序n 整个算法：整个算法：voidvoid RadixSort(SqList&L)RadixSort(SqList&L)RcdType CL.length;RcdType CL.length;/申请辅助空间申请辅助空间 i=L.bitsnum-1;i=L.bitsnum-1;whilewhile(i=0)(i=0)RadixPass(L.r,C,L.length,i);RadixPass(L.r,C,L.length,i);/一趟基数排序，结果存人一趟基数排序，结果存人C C i-;i-;if if(i=0)(i=0)RadixPass(C,L.r,L.length,i);RadixPass(C,L.r,L.length,i);/一趟基数排序，结果存人一趟基数排序，结果存人L.rL.r i-;i-;/if/if elseelse for for(j=0;jL.length;j+)(j=0;jL.length;j+)/排序后的结果若在排序后的结果若在C C中，复制到中，复制到L.rL.r L.rj=Cj;L.rj=Cj;/while/while/RadixSort/RadixSortTypedef struct RcdType *r;int bitnum;int length;SqList 663.4 3.4 基数排序基数排序n时间复杂度：时间复杂度：n最佳状况、最坏状况、平均状况：最佳状况、最坏状况、平均状况：O(dO(d*n)n)n空间复杂度：空间复杂度：n最佳状况、最坏状况、平均状况：最佳状况、最坏状况、平均状况：O(n)O(n)n优点：优点：n平均时间复杂度低；稳定性排序。平均时间复杂度低；稳定性排序。n缺点：缺点：n空间效率低。空间效率低。673.5 各种排序方法的综合比较各种排序方法的综合比较n3.5.1 3.5.1 时间性能时间性能n3.5.2 3.5.2 空间性能空间性能n3.5.3 3.5.3 排序方法稳定性能排序方法稳定性能n3.5.4 3.5.4 小结小结683.5.1 3.5.1 时间性能时间性能n按平均的时间性能来分，有三类排序方法：按平均的时间性能来分，有三类排序方法：n时间复杂度时间复杂度O(nlogn)O(nlogn)的方法有：快速排序、堆排序和归并排的方法有：快速排序、堆排序和归并排序，其中快速排序目前被认为是最快的一种排序方法，后两者序，其中快速排序目前被认为是最快的一种排序方法，后两者之比较，在之比较，在n n值较大的情况下，归并排序较堆排序更快。值较大的情况下，归并排序较堆排序更快。n时间复杂度时间复杂度O(nO(n2 2 )的方法有：插入排序、起泡排序和选择排的方法有：插入排序、起泡排序和选择排序，其中以插入排序为最常用，特别是已按关键字基本有序排序，其中以插入排序为最常用，特别是已按关键字基本有序排列的记录序列尤为如此，选择排序过程中记录移动次数最少。列的记录序列尤为如此，选择排序过程中记录移动次数最少。n当待排记录序列按关键字顺序有序时，插入排序和起泡排序能当待排记录序列按关键字顺序有序时，插入排序和起泡排序能达到达到O(n)O(n)的时间复杂度；而对于快速排序而言，这是最不好的情的时间复杂度；而对于快速排序而言，这是最不好的情况，此时的时间性能蜕化为况，此时的时间性能蜕化为O(O(n n2 2)n选择排序、堆排序和归并排序的时间性能不随记录序列中关键选择排序、堆排序和归并排序的时间性能不随记录序列中关键字的分布而改变，人们应事先对要排序的记录关键字的分布情况字的分布而改变，人们应事先对要排序的记录关键字的分布情况有所了解，才可有所了解，才可1 1对症下药，选择有针对性的排序方法。对症下药，选择有针对性的排序方法。n当待排序记录中其他各数据项比关键字占有更大的数据量时，当待排序记录中其他各数据项比关键字占有更大的数据量时，还应考虑到排序过程中移动记录的操作时间，起泡排序效率最低。还应考虑到排序过程中移动记录的操作时间，起泡排序效率最低。693.5.2 3.5.2 空间性能空间性能n空间性能指的是排序过程中所需的辅助空间性能指的是排序过程中所需的辅助空间大小。空间大小。n所有的简单排序方法（包括：插入、起泡和选择所有的简单排序方法（包括：插入、起泡和选择排序）和堆排序的空间复杂度均为排序）和堆排序的空间复杂度均为O O（1 1）.n快速排序为快速排序为O(logn),O(logn),为递归程序执行过程中栈所为递归程序执行过程中栈所需的辅助空间。需的辅助空间。n归并排序和基数排序所需辅助空间最多，其空间归并排序和基数排序所需辅助空间最多，其空间复杂度为复杂度为O(n)O(n)。703.5.3 3.5.3 排序方法稳定性能排序方法稳定性能n稳定的排序方法指的是对于两个关键字相等的稳定的排序方法指的是对于两个关键字相等的记录在经过排之后，不改变它们在排序之前在记录在经过排之后，不改变它们在排序之前在序列中的相对位置。序列中的相对位置。n除快速排序和堆排序是不稳定的排序方法外，除快速排序和堆排序是不稳定的排序方法外，本章讨论的其他排序访方法都是稳定的，例如，本章讨论的其他排序访方法都是稳定的，例如，例如：对关键字序列（例如：对关键字序列（4 41 1，3 3，4 42 2，2 2）进行快速）进行快速排序，其结果为（排序，其结果为（2 2，3 3，4 42 2，4 41 1）。）。n“稳定性稳定性”是由方法本身决定的，一般来说，是由方法本身决定的，一般来说，排序过程中所进行的比较操作和交换数据仅发排序过程中所进行的比较操作和交换数据仅发生在相邻的记录之间，没有大步距的数据调整生在相邻的记录之间，没有大步距的数据调整时，则排序方法是稳定的。时，则排序方法是稳定的。713.5.4 小结小结排序法排序法平均时间平均时间最坏情况最坏情况最好情况最好情况辅助空间辅助空间稳定性稳定性插入插入O(n2)O(n2)O(n)O(1)选择选择O(n2)O(n2)O(n2)O(1)起泡起泡O(n2)O(n2)O(n)O(1)快速快速O(n*log2n)O(n2)O(n*log2n)O(log2n)归并归并O(n*log2n)O(n*log2n)O(n*log2n)O(n)堆堆O(n*log2n)O(n*log2n)O(n*log2n)O(1)基数基数O(d*n)O(d*n)O(d*n)O(n)723.5.4 小结小结n若待排序的记录个数若待排序的记录个数n n值较小（例如值较小（例如n30n0)while(len0)for(j=len+1;j=L.length;j+)for(j=len+1;j=L.length;j+)if(L.Rj.keyL.Rj-len.key)if(L.Rj.keyL.Rj-len.key)L.R0=L.Rj;process=j-len;L.R0=L.Rj;process=j-len;while(L.R0.key0)while(L.R0.key0)L.Rprocess+len=L.Rprocess;L.Rprocess+len=L.Rprocess;process-=len;process-=len;/while /while L.Rprocess+len=L.R0;L.Rprocess+len=L.R0;/if /iflen/=2;len/=2;/while/while/shellsort/shellsort3.6 谢耳排序法算法谢耳排序法算法763.6 谢耳排序法谢耳排序法n时间复杂度：时间复杂度：nO(nr)其中其中1r2n空间复杂度：空间复杂度：O（1）n优点：优点：n以插入的方式进行排序，方法简易，由于以插入的方式进行排序，方法简易，由于插入排序法对已排序好的部分会快速处理，插入排序法对已排序好的部分会快速处理，故最后几次程序速度会较快故最后几次程序速度会较快。773.7 二叉树排序法二叉树排序法n基本思想：基本思想：n将欲排序的元素一一以建立二叉树的方式插入；将欲排序的元素一一以建立二叉树的方式插入；n（1）每一个节点最多只有两个子节点（左节点、右节点）每一个节点最多只有两个子节点（左节点、右节点）n（2）若一节点有子节点，则该节点的数据要比左节点的）若一节点有子节点，则该节点的数据要比左节点的数据大，且比右节点的数据小（左节点数据大，且比右节点的数据小（左节点parent右节点）右节点）n使用二叉树中序遍历的方式将二叉树的节点打输出使用二叉树中序遍历的方式将二叉树的节点打输出来，即可得到元素的排序结果。来，即可得到元素的排序结果。n实例：实例：424242151561612222545438384215421561421561224215612254384215612254793.7 二叉树排序法二叉树排序法n算法：算法：void binarytree(int void binarytree(int*btree,int btree,int*list,int index)list,int index)int i,level;int i,level;btree1=list1;btree1=list1;for(i=2;i=index;i+)for(i=2;i=index;i+)level=1;level=1;while(btreelevel!=0)while(btreelevel!=0)if(listibtreelevel level if(listibtreelevel level*=2;=2;else level=2 else level=2*level+1;level+1;btreelevel=listi;btreelevel=listi;80 3.7 二叉树排序法二叉树排序法n时间复杂度：时间复杂度：n受高度影响，为受高度影响，为 O(n*log2n)n空间复杂度：空间复杂度：O(n)n优点：优点：n以插入的方式进行排序，方法简单以插入的方式进行排序，方法简单。n缺点：缺点：n在插入节点时，第一个元素必为树根，若该值在数列中偏在插入节点时，第一个元素必为树根，若该值在数列中偏大或偏小，则会使树的歪斜程度加大，从而影响排序速度。大或偏小，则会使树的歪斜程度加大，从而影响排序速度。n稳定性：由排序条件决定稳定性：由排序条件决定n左节点左节点 parent parent 右节点，稳定排序右节点，稳定排序n左节点左节点 parent parent 右节点，不稳定排序右节点，不稳定排序