数据结构第八章排序(2016)

1、第八章 排序12基本排序插入排序34交换排序选择排序5归并排序6分配排序8.1 基本排序排序：排序：给定一组给定一组记录记录的集合的集合r1, r2, , rn，其相应，其相应的关键字分别为的关键字分别为k1, k2, , kn，排序是将这些记录，排序是将这些记录排列成顺序为排列成顺序为rs1, rs2, , rsn的一个序列，使得相的一个序列，使得相应的关键字满足应的关键字满足ks1ks2ksn（称为升序）或（称为升序）或ks1ks2ksn（称为降序）。（称为降序）。正序：正序：待排序序列中的记录已按关键字排好序。待排序序列中的记录已按关键字排好序。逆序（反序）：逆序（反序）：待排序序列中记

2、录的排列顺序与排好待排序序列中记录的排列顺序与排好序的顺序正好相反。序的顺序正好相反。注注: 没有特别说明没有特别说明,均按递增顺序排序均按递增顺序排序.排序算法的排序算法的稳定性：稳定性：假定在待排序的记录集中，存在假定在待排序的记录集中，存在多个多个具有具有相同键值相同键值的记录，若的记录，若经过排序经过排序，这些记录的，这些记录的相对次序相对次序仍然仍然保持不变保持不变，即在原序列中，即在原序列中，ki=kj且且ki在在kj之前，而在排序后的序列中，之前，而在排序后的序列中，ki仍在仍在kj之前，则称这种之前，则称这种排序算法是排序算法是稳定的稳定的；否则否则称为称为不稳定不稳定的。的。

3、 排序的分类排序的分类1.1. 内部排序：内部排序：在排序的整个过程中，待在排序的整个过程中，待排序的所有排序的所有记录记录全部全部被放置在被放置在内存内存中。中。2. 2. 外部排序外部排序：由于待排序的记录个数太多，不能同由于待排序的记录个数太多，不能同时放置在内存，而需要将时放置在内存，而需要将一部分记录一部分记录放置放置在内存在内存，另另一部分记录一部分记录放置放置在外存上在外存上，整个排序过程需要在内外，整个排序过程需要在内外存之间多次交换数据才能得到排序的结果。存之间多次交换数据才能得到排序的结果。重点重点8.1 基本排序1. 内排序在排序过程中的内排序在排序过程中的基本操作基本操

4、作：比较比较：关键字之间的比较；：关键字之间的比较；移动移动：记录从一个位置移动到另一个位置。：记录从一个位置移动到另一个位置。 2. 辅助存储空间辅助存储空间。3.算法本身的复杂程度算法本身的复杂程度。 排序算法的排序算法的性能性能文件存储结构文件存储结构 typedef struct int key; datatype other; rectype; rectype Rn;8.2 插入排序插入排序有多种具体实现算法：插入排序有多种具体实现算法： 1) 1) 直接插入排序直接插入排序 2) 2) 希尔排序希尔排序简言之，边插入边排序，保证子序列中随时都是排好序的。简言之，边插入边排序，保证子

5、序列中随时都是排好序的。8.2.1 直接插入排序新元素插入到哪里？新元素插入到哪里？思想思想: :假设待排记录存于假设待排记录存于RnRn( (R1-Rn-1R1-Rn-1共共n-1n-1个元素个元素),),若若排序的某一时刻排序的某一时刻R R被分为两个子区被分为两个子区: : R1 R1Ri-1Ri-1和和RiRiRn-1Rn-1关键关键: :如何将如何将RiRi插入到当前有序区的适当位置插入到当前有序区的适当位置? ? 假设只有一个记录的有序表是有序的假设只有一个记录的有序表是有序的, ,在在已形成的已形成的有序表中进行比较有序表中进行比较，并在适当位置插入，把原来位，并在适当位置插入，

6、把原来位置上的元素向后置上的元素向后顺移顺移。分析分析: :与当前有序区中最后一个记录与当前有序区中最后一个记录RjRj进行比较进行比较: : 若若Ri.keyRj.key,Ri.key=Rj.key,Ri.key=Rj.key,则则j+1j+1为为RiRi插入位置插入位置. .8.2.1 直接插入排序例：例：关键字序列关键字序列T=（13，6，3，31，9，27，5，11），）， 请写出直接插入排序的中间过程序列。请写出直接插入排序的中间过程序列。 【13】, 6, 3, 31, 9, 27, 5, 11第一趟第一趟【6, 13】, 3, 31, 9, 27, 5, 11第二趟第二趟【3,

7、6, 13】, 31, 9, 27, 5, 11第三趟第三趟【3, 6, 13 , 31】, 9, 27, 5, 11第四趟第四趟【3, 6, 9, 13 , 31】, 27, 5, 11第五趟第五趟【3, 6, 9, 13 , 27, 31】, 5, 11第六趟第六趟【3, 5, 6, 9, 13 , 27, 31】, 11第七趟第七趟【3, 5, 6, 9, 11, 13 , 27, 31】 void insertort ( rectype Rn) int i,j; for(i=2;in;i+) R0=Ri; /*监视哨监视哨*/ j=i-1; while(R0.keyRj.key) Rj

8、+1=Rj-; Rj+1=R0; 小结：直接插入排序是一种小结：直接插入排序是一种稳稳定定的排序算法。的排序算法。8.2.1 直接插入排序直接插入排序直接插入排序算法性能分析算法性能分析最好最好情况下（情况下（正序正序）：）： 时间复杂度为时间复杂度为O(n)。比较次数：比较次数：Cmin=n-1移动次数：移动次数：Mmin=2(n-1) 最坏最坏情况下（情况下（逆序或反序逆序或反序）：）： 2) 1)(2(2maxnniCni比较次数：比较次数：移动次数：移动次数：ninniM2max2) 1)(4() 21(时间复杂度为时间复杂度为O(n2)。 平均时间复杂度为平均时间复杂度为O(n2)空

9、间复杂度空间复杂度:O(1)8.2.2 希尔排序（又称缩小增量排序）（又称缩小增量排序）基本思想基本思想：先取先取一个一个正整数正整数d d1 1nn, ,把把全部记录分成全部记录分成d d1 1个个组组，所有，所有距离为距离为d d1 1倍数的记录倍数的记录放在一组放在一组，在各组内在各组内进行进行直接插入排序直接插入排序；然后；然后取取d d2 2dd1 1，重复上述，重复上述分组和排序分组和排序工工作，作，直至取直至取d d1 1=1=1，即所有记录放在一组中排序为止。即所有记录放在一组中排序为止。技巧技巧：希尔排序中增量：希尔排序中增量di有多种有多种取法取法，我们可选取如，我们可选取

10、如d1=n/2,di+1=di/2。优点优点：让：让关键字小关键字小的元素的元素很快前移很快前移，且序列若，且序列若基本有基本有序时序时，再用直接插入排序处理，再用直接插入排序处理，时间效率会高很多时间效率会高很多。8.2.2 希尔排序1 2 3 4 5 6 7 8 9初始序列初始序列d = 4d = 2d = 18.2.2 希尔排序算法分析：算法分析：每组都需要一个监视哨每组都需要一个监视哨,则共取最大值则共取最大值d1个个,存储于存储于R0-Rd1-1中中,只需让其值小于所有关键字即可。只需让其值小于所有关键字即可。算法描述：算法描述：rectype Rn+d1; /*Rd1-Rn+d1-

11、1存放存放n个待排记录个待排记录*/int dt; /*增量序列增量序列 d0=d1*/void SHELLSORT(rectype R,int d) int i,j,k,h; rectype temp; for(i=0;id0;i+) Ri.key=0; /*设监视哨设监视哨,小于所有小于所有key*/ 8.2.2 希尔排序 k=0; do h=dk; for(i=h+d1;in+d1;i+) temp=Ri; j=i-h; while(temp.keyRj.key) Rj+h=Rj; j=j-h; Rj+h=temp; k+; /*取下一增量取下一增量*/ while(h!=1)8.2.2

12、 希尔排序希尔排序算法的希尔排序算法的时间性能：时间性能：希尔排序希尔排序算法的时间性能是所取算法的时间性能是所取增量增量的函数，而的函数，而到目前为止尚未有人求得一种最好的增量序列。到目前为止尚未有人求得一种最好的增量序列。 研究表明，希尔排序的时间性能研究表明，希尔排序的时间性能在在O(n2)和和O(nlog2n)之间之间。当。当n在某个特定范围内，希尔排序所需的比较次在某个特定范围内，希尔排序所需的比较次数和记录的移动次数数和记录的移动次数约为约为O(n1.3 ) 。 分析：分析：开始时开始时dk 的值较大，子序列中的记录较少，排序速度较的值较大，子序列中的记录较少，排序速度较快；随着排

13、序进展，快；随着排序进展，dk 值逐渐变小，子序列中记录个数值逐渐变小，子序列中记录个数逐渐变多，由于前面工作的基础，大多数记录已基本有逐渐变多，由于前面工作的基础，大多数记录已基本有序，所以排序速度仍然很快。序，所以排序速度仍然很快。小结：希尔排序是一种小结：希尔排序是一种不稳定不稳定的排序算法。的排序算法。8.3 交换排序交换交换 两两比较两两比较待排序记录的关键字，如果待排序记录的关键字，如果发生逆序发生逆序（即排列顺序与排序后的次序正好相反），则（即排列顺序与排序后的次序正好相反），则交换之交换之，直到所有记录都排好序为止。直到所有记录都排好序为止。交换排序的主要算法有：交换排序的主要

14、算法有： 1) 起泡排序起泡排序 2) 快速排序快速排序8.3.1 起泡排序基本思路：基本思路：将待排记录将待排记录纵向排列纵向排列, ,自下而上两两比自下而上两两比较较相邻记录关键字相邻记录关键字k kj j与与k kj-1j-1的值的值, ,若若反序反序则二则二者者交换交换位置位置, ,继续比较继续比较k kj-1j-1与与k kj-2j-2, ,直到全部记直到全部记录比较一遍，则一趟结束。录比较一遍，则一趟结束。优点：优点：每趟结束时，不仅能使当前最小关键字上升每趟结束时，不仅能使当前最小关键字上升到其应该所在位置，还能同时部分理顺其他到其应该所在位置，还能同时部分理顺其他元素。元素。例

15、：例：关键字序列关键字序列 T=(49, 38, 65, 97, 76, 13, 27, 49*），请写出冒），请写出冒泡排序的具体实现过程。泡排序的具体实现过程。4938659776132749*初态初态 第第1趟趟 第第2趟趟 第第3趟趟 第第4趟趟 第第5趟趟1349386597762749*1327493865977649*1327384949*6597761327384949*6576971327384949*657697起泡排序需多少趟起泡排序需多少趟,每趟需比较次数每趟需比较次数?第第1趟趟:n-1次次第第2趟趟:n-2次次(至多至多)第第n-1趟趟:1次次一旦下趟没有交换发一旦

16、下趟没有交换发生，还可以提前结束生，还可以提前结束排序排序。如何确定何时结束排序？如何确定何时结束排序？ 设标志位设标志位noswap来表示每一趟是否有交换：来表示每一趟是否有交换： 即：每趟开始之前，设即：每趟开始之前，设noswap=1，若交换则改，若交换则改noswap=0；只需每趟结束后观察只需每趟结束后观察noswap的值即可。的值即可。8.3.1 起泡排序void BUBBLESORT( rectype R) /*R0-Rn-1共共n个记录个记录*/ int i,j,noswap; rectype temp; for(i=0;i=i;j-) if(Rj+1.keyRj.key) t

17、emp=Rj+1; Rj+1=Rj; Rj=temp; noswap=0; if(noswap=1) break; n-2n-18.3.1 起泡排序冒泡排序的算法分析冒泡排序的算法分析时间效率时间效率：O O（n n2 2) ) 空间效率空间效率：O O（1 1） 只在交换时用到一个缓冲单元只在交换时用到一个缓冲单元稳稳 定定 性性： 稳定稳定详细分析：详细分析：最好情况：最好情况：初始排列已经有序，只执行一趟起泡，初始排列已经有序，只执行一趟起泡，做做 n- -1 次关键码比较，不移动对象。次关键码比较，不移动对象。O(n)最坏情形：最坏情形：初始排列逆序，初始排列逆序，算法要执行算法要执行

18、n-1 1趟起泡，第趟起泡，第i趟趟(1 i n) 做了做了n- i 次关键码比较，执行了次关键码比较，执行了n-i 次对象交换。次对象交换。此时的比较总次数和记录移动次数为：此时的比较总次数和记录移动次数为：11111233121nininninMnninC)()()()(maxmaxO（n2）O（n2）8.3.1 起泡排序分析：分析：设变量设变量exchange记载记录交换的位置，则一趟排记载记录交换的位置，则一趟排序后，序后，exchange记载的一定是这一趟排序中记录的最后记载的一定是这一趟排序中记录的最后一次交换位置，且从此位置以后的所有记录均已有序一次交换位置，且从此位置以后的所有

19、记录均已有序。 每趟扫描时，记录最后一次交换位置每趟扫描时，记录最后一次交换位置k，则下一趟只需，则下一趟只需扫描到扫描到 k处即可，而不必到处即可，而不必到i。分析：分析：由于一般起泡排序在记录正序时只作一趟，而反由于一般起泡排序在记录正序时只作一趟，而反序时作序时作n-1趟。则可考虑每次将从上到下扫描和从下到上趟。则可考虑每次将从上到下扫描和从下到上扫描交替进行，即：从下往上升小的，从上往下降大的。扫描交替进行，即：从下往上升小的，从上往下降大的。（2） 双向起泡双向起泡8.3.2 快速排序 假设待排记录假设待排记录Rl-Rh,Rl-Rh,任取一个记录任取一个记录 ( (通常取无序区通常取

20、无序区第一个记录第一个记录) ) 作为比较的作为比较的基准基准temptemp，以其关键字的值为分界点将全部记录划分为两部以其关键字的值为分界点将全部记录划分为两部分分: :所有所有比它小比它小的元素均位于分界点的元素均位于分界点左侧左侧(Rl-(Rl-Ri-1)Ri-1)，所有，所有比它大比它大的元素的元素均位于分界点均位于分界点右侧右侧(Ri+1-Rh)(Ri+1-Rh), ,则基准则基准temptemp就位于其最终正确位就位于其最终正确位置置Ri;Ri;然后再分别对这两部分无序区重复上述过然后再分别对这两部分无序区重复上述过程，直到程，直到每一部分均只剩一个记录为止每一部分均只剩一个记录

21、为止。 ( (又称划分交换排序又称划分交换排序) )基本思想：基本思想：8.3.2 快速排序解决方法：解决方法：设待划分的序列是设待划分的序列是Rl-RhRl-Rh，设指针，设指针i i，j j分别指向该区域左、右两端的下标分别指向该区域左、右两端的下标l l和和h h，令，令RlRl为为基准基准temp.temp.（1 1）j j向左向左扫描扫描:j-:j-，找到第一个比基准小的记录，找到第一个比基准小的记录RjRj，与，与RiRi交换；交换；（2 2）i i向右向右扫描扫描:i+:i+，找到第一个比基准大的记录，找到第一个比基准大的记录RiRi，与，与RjRj交换；交换；（3 3）重复上述

22、过程，直到）重复上述过程，直到i=ji=j, ,此时此时i i便为基准最终所便为基准最终所在位置。在位置。关键问题：如何实现一次划分？关键问题：如何实现一次划分？快速排序算法分析快速排序算法分析(了解了解)例：例：关键字序列关键字序列 T=(49, 38, 65, 97, 76, 13, 27, 49）8.3.2 快速排序int Partition( rectype R, int l, int h) /*RlRh*/ int i,j; rectype temp; i=l; j=h; temp=Ri; /*初始化初始化*/ do while ( ) j-; /*j向左扫描向左扫描*/ if (i

23、j) Ri+=Rj; while ( ) i+;/*i向右扫描向右扫描*/ if (ij) Rj- -=Ri; while(i!=j) Ri=temp; /*i为基准的最终位置为基准的最终位置*/ retutn i;i= temp.keyij & Ri.key= temp.key8.3.2 快速排序调用方法：调用方法：Quicksort(R,0,n-1);Quicksort(R,0,n-1);关键问题：如何处理划分后得到的两个待排序子序列？关键问题：如何处理划分后得到的两个待排序子序列？ void QuickSort (rectype R, int s1, int t1 ) int i; if

24、 (s1 t1) i= Partition (R,s1, t1); QuickSort (R, s1, i-1); QuickSort ( R, i+1, t1); 解决方法：解决方法：对划分得到的两个子序列递归地执行快速对划分得到的两个子序列递归地执行快速排序。排序。8.3.2 快速排序例：例：49,38,65,97,76,13,27,49的快速排序递归树如下：的快速排序递归树如下：快速排序的快速排序的递归执行过程递归执行过程可以用递归树描述。可以用递归树描述。快速排序的性能分析快速排序的性能分析4927769749653838138.3.2 快速排序快速排序算法快速排序算法效率分析效率分析

25、：空间复杂度空间复杂度: :递归调用时每次的指针递归调用时每次的指针, ,参数需用栈存放参数需用栈存放, ,则与递则与递归树的深度一致归树的深度一致. . 最好情况最好情况: :每次划分将文件均分为两部分每次划分将文件均分为两部分最坏情况最坏情况: :递归深度为递归深度为n,n,一边倒一边倒, ,则则 O(n)O(n)时间复杂度时间复杂度: : 最好情况最好情况: :每次都均等分每次都均等分最坏情况最坏情况: :一边倒一边倒, ,每次划分无序区记录只少一个每次划分无序区记录只少一个, ,需进行需进行n-1n-1趟排序趟排序, ,每趟每趟n-in-i次比较次比较, ,则则C Cmaxmax= O

26、(n= O(n2 2) ) 小结小结: :平均时间复杂度平均时间复杂度: :快速排序是一种快速排序是一种不稳定不稳定的排序算法的排序算法. .8.4 选择排序选择排序有多种具体实现算法：选择排序有多种具体实现算法： 1) 1) 直接选择排序直接选择排序 2) 2) 堆排序堆排序基本思想基本思想：每一趟从待排记录中选取关键字最小的记每一趟从待排记录中选取关键字最小的记录录, ,顺序放在已排好序的记录序列后面顺序放在已排好序的记录序列后面, ,直至全部记录直至全部记录排完为止。排完为止。8.4.1 直接选择排序思路简单：思路简单：每经过每经过一趟一趟比较就比较就找出一个最小值找出一个最小值，与待与

27、待排序列最前面的位置互换排序列最前面的位置互换即可。即可。首先，在首先，在n个记录中选择最小者放到个记录中选择最小者放到R0位置；然后，从位置；然后，从剩余的剩余的n-1个记录中选择最小者放到个记录中选择最小者放到R1位置；位置；如此进行下如此进行下去，直到全部有序为止。去，直到全部有序为止。优点：优点：实现简单实现简单缺点：缺点：每趟只能确定一个元素，表长为每趟只能确定一个元素，表长为n n时需要时需要n-1n-1趟趟8.4.1 直接选择排序例：例：关键字序列关键字序列T= T= （2121，2525，4949，2525* *，1616，0808），），请给出请给出直接选择排序直接选择排序的

28、具体实现过程。的具体实现过程。原始序列：原始序列： 21，25，49，25*，16，08第第1趟趟第第2趟趟第第3趟趟第第4趟趟第第5趟趟08，25，49，25*，16，2108，16, 49，25*，25，2108，16, 21，25*，25，4908，16, 21，25*，25，4908，16, 21，25*，25，49算法的算法的稳定性稳定性：因为排序时，因为排序时，2525* *到了到了2525的前面。的前面。最小值最小值 0808 与与R0R0交换位置交换位置8.4.1 直接选择排序void selectSort ( rectype R ) /*R0Rn-1*/ int i,j,mi

29、n; rectype temp; for (int i=0; in-1; i+) /*n-1 趟趟*/ min=i; for ( j=i+1; jn; j+) /*找最小找最小*/ if (Rj.keyn/2in/2的结点是叶子结点的结点是叶子结点. .即具即具有有n n个结点的完全二叉树个结点的完全二叉树, ,有有 个叶子结点个叶子结点. .2)2)从从最后一个非叶子结点最后一个非叶子结点开始开始, ,即即i=n/2i=n/2( (注注: :整除整除),),以其为以其为根根, ,将该将该子树调整为堆子树调整为堆; ;再调下一个非叶子结再调下一个非叶子结点点, ,逐个调整至以逐个调整至以第一个

30、非叶子结点第一个非叶子结点为根的树调整为根的树调整为堆为堆, ,则就完成了初始化堆的过程则就完成了初始化堆的过程. .2/n8.4.2 堆排序思想：思想：由于其左右子树均为堆由于其左右子树均为堆,则以则以Ri为根的树中的为根的树中的最大值只能在最大值只能在Ri与其左右孩子结点中选择与其左右孩子结点中选择.(1) 若若Ri.key最大最大,则无须调整则无须调整,即为大根堆即为大根堆;(2) 若左右孩子结点之一最大若左右孩子结点之一最大(假设假设R2i.key最大最大),则则Ri与与R2i交换；但交换后可能导致以交换；但交换后可能导致以R2i为为根的子树被破坏不再是堆，由于以根的子树被破坏不再是堆

31、，由于以R2i为根的为根的左右子树仍为堆，则重复此过程，继续向下筛左右子树仍为堆，则重复此过程，继续向下筛选。选。8.4.2 堆排序创建堆和调整堆的方法实例创建堆和调整堆的方法实例: (: (大根堆大根堆) )1.1.创建完全二叉树创建完全二叉树152011231310 1 2 3 4 5 61510201323111110,无需调整无需调整8.4.2 堆排序152011231310 1 2 3 4 5 61510201323112023,筛下筛下202.2.调整调整8.4.2 堆排序152311201310 1 2 3 4 5 61510231320111523,1523,筛下筛下15151

32、520,筛下筛4.2 堆排序231020131511初始建堆结果初始建堆结果:23 20 11 15 13 10:23 20 11 15 13 10232011151310 1 2 3 4 5 6例：例：关键字序列关键字序列 T=(42, 13, 91, 23, 24, 76, 05, 88）void SIFT (rectype R, int i, int m ) /*Ri-Rm*/ int j; rectype temp; temp=Ri; j=2*i; /*左孩子下标左孩子下标*/ while (j=m ) if (jm & Rj.keyRj+1.key) j+;

33、 if (temp.key=1; i-) SIFT(R,i,n) ; 关键问题：如何由一个无序序列建成一个堆？关键问题：如何由一个无序序列建成一个堆？注：注：最后一个结点（叶子）的序号是最后一个结点（叶子）的序号是n，则最后一个分支结点则最后一个分支结点(非叶子结点非叶子结点)即为结点即为结点n的双亲，的双亲，其序号是其序号是n/2。8.4.2 堆排序堆排序算法堆排序算法void HeapSort ( rectype R ) /*R1-Rn*/ int i; rectype temp; for (i=n/2; i=1; i-) /*初始化堆初始化堆*/ SIFT(R,i,n); for (i=

34、n; i1; i- ) /*n-1趟趟*/ temp=R1; /*交换交换*/ R1=Ri; Ri=temp; SIFT(R,1,i-1); /*重建堆重建堆*/ 8.4.2 堆排序SIFT( )8.5 归并排序关键字序列关键字序列T= （21，25，49，25*，93，62，72，08，37，16，54），请给出归并排序的具体），请给出归并排序的具体实现过程。实现过程。关键问题：关键问题：如何将如何将两个有序序列两个有序序列合成合成一个有序序列一个有序序列？设设Rlow-RmidRlow-Rmid和和Rmid+1-RhighRmid+1-Rhigh为相邻，归并为相邻，归并成一个有序序列成一个

35、有序序列R1low - R1high R1low - R1high 。low m m+1 highR lowhigh R1 ijk若若Ri.key=Rj.key,Ri.keyRj.key, Ri.keyRj.key, 则则R1k=Rj;k+;j+; R1k=Rj;k+;j+; 8.5 归并排序void Merge (rectype R , rectype R1 , int low, int mid, int high ) int i,j,k; i=low; j=mid+1; k=low; while (i=mid & j=high) if (Ri.key=Rj.key) R1k+=Ri+; else R1k+=Rj+; while (i=mid) R1k+=Ri+; while (j=high) R1k+=Rj+; 算法描述：仅实现一次归并算法描述：仅实现一次归并, ,且只归并两组且只归并两组. . 8.5 归并排序void Mergepass (rectype R , r