排序梁.ppt

《排序梁.ppt》由会员分享，可在线阅读，更多相关《排序梁.ppt（91页珍藏版）》请在三一文库上搜索。

1、第9章 排序,主讲：梁宝兰,2,第9章 排序,教学要求： 1、理解和掌握：排序的基本思想和基本概念，插入排序、选择排序、交换排序的思想、算法及分析。 2、理解：归并排序和基数排序，排序算法的性能分析与比较。,3,内容提要,排序的基本概念 插入排序 交换排序 选择排序 归并排序 基数排序 性能比较,4,9.1 基本概念,一、排序的定义： 排序：是将一个数据元素的任意序列，重新排列成一个按关键字（排序码）有序的序列。 关键字：是要排序的数据元素集合中的一个域，排序是以关键字为基准进行的。 主关键字:能够惟一区分各个不同数据元素的关键字;不满足主关键字定义的关键字称为次关键字。,5,二、稳定排序和非

2、稳定排序 对于具有同一排序码的多个记录来说，若采用的排序方法保证使排序后记录的相对次序不变，则称此排序方法是稳定的，否则称为不稳定的。,9.1 基本概念,例如： 排序前： 5 ， 4 ， 1 ， 2 ，4 , 3 稳定排序后： 1， 2 ， 3， 4 ，4 , 5 不稳定排序后： 1， 2 ， 3， 4 ，4 , 5,6,三、内部排序和外部排序 按照排序过程中使用内外存的不同将排序方法分为内排序和外排序。 若排序过程全部在内存中进行，则称为内排序；若排序过程需要不断地进行内存和外存之间的数据交换，则称为外排序。,9.1 基本概念,本教材中讨论的均为内排序,7,四、内部排序算法的分类 1.按排序

3、原则分类 插入排序：(直接插入排序、二分插入排序、希尔排序) 选择排序：(简单选择排序、树型排序、堆排序) 交换排序：(冒泡排序、快速排序) 归并排序：(二路归并排序、多路归并排序) 基数排序：(多关键字排序、基数排序),9.1 基本概念,8,2. 按排序复杂度分类： 简单排序方法； 先进的排序方法； 基数排序。,9.1 基本概念,9,五、排序算法的比较 时间复杂性 排序 = 比较+移动 空间复杂性 衡量算法中使用的辅助内存空间的多少。 稳定性： 是否为稳定算法,9.1 基本概念,10,六、待排序记录的结构定义： struct Node KeyType key; ;,9.1 基本概念,本教程中

4、所有 KeyTpye均为int,11,9.2 插入排序,一、直接插入排序 1. 基本思想： 假设待排序的记录存放在数组R0n-1中。 初始时，R0自成1个有序区，无序区为R1n-1 从i=1起直至i=n-1为止，依次将Ri插入当前的有序区R0i-1中，生成含n个记录的有序区。,12,待排序序列：17，3，25，14，20，9,2. 直接插入排序过程举例：,演示,13,3. 直接插入的算法实现 /对r数组中前n个数据进行排序 void stinsort(Node r, int n) int i, j; node x; for ( i=1; in; i+) /进行n-1趟插入 /把第i个元素插入到

5、已有序的0i-1元素中。 ,通过比较找准第i个元素插入的位置,哨兵？,j = i-1; x = ri; while (rj.key x.key),14,4. 直接插入排序的效率分析 空间性能：需要一个元素的辅助空间 时间性能： 最好情形（已有序）下，排序过程中比较的次数是n-1，赋值执行的次数是2（n-1) ； 最坏情形（倒序）下，比较次数为n(n-1)/2，赋值语句执行的次数为(n-1)(n+4)/2。因此，直接插入排序的时间复杂度为O（n2）。 （另注：直接插入排序在n较小时，其效率比较高；若数据基本有序，则其效率也比较高） 稳定性：稳定,一、直接插入排序,15,二、折半插入排序 基本思想

6、还是通过n-1趟插入，把无序元素插入到有序元素中 对于第i个元素的插入，可以先采用折半查找法来确定其插入位置，然后进行插入,9.2 插入排序,待排序序列： 17, 3, 25, 14, 20, 9,演示,16,void binsort(Node r, int n) int i, j,low,high,mid; Node x; for ( i=1; i=low;j-) /移动数据，腾出插入位置 rj+1 = rj; rlow = x; /插入数据 ,17,三、希尔排序 1. 基本思想： 先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中

7、。先在各组内进行直接插人排序；然后，取第二个增量d2d1重复上述的分组和排序，直至所取的增量dt=1(dtdt-ld2d1)，即所有记录放在同一组中进行直接插入排序为止。 该方法实质上是一种分组插入方法。,9.2 插入排序,18,三、希尔排序,2. 排序过程举例： 待排序序列： 49, 38, 65, 97, 76, 13, 27, 49, 55, 4,d=5,49,13,27,38,65,49,97,55,76,4,19,三、希尔排序,2. 排序过程举例： 待排序序列： 49, 38, 65, 97, 76, 13, 27, 49, 55, 4,d=5,49,13,27,38,65,49,9

8、7,55,76,4,d=2,55,4,27,49,65,13,97,49,76,38,20,三、希尔排序,2. 排序过程举例： 待排序序列： 49, 38, 65, 97, 76, 13, 27, 49, 55, 4,d=5,49,13,27,38,65,49,97,55,76,4,d=2,55,4,27,49,65,13,97,49,76,38,55,4,13,65,27,97,38,76,49,49,d=1,21,3. 希尔算法的实现 void shellsort(Node r, int n) int i, j, d; Node x; d = n/2; while(d=1) / 以增量等于

9、1结束插入排序 for ( i=d; i x.key) /增量缩减 ,Shell排序,局部有序，比较和移动次数减少,三、希尔排序,22,4. 希尔排序分析 时间性能：虽然我们给出的算法是三层循环，最外层循环为log2n数量级，中间的for循环是n数量级的，内循环远远低于n数量级，因为当分组较多时，组内元素较少，因此循环次数少；当分组较少时，组内元素增多，但已接近有序，循环次数并不增加。因此，希尔排序的时间复杂性在O（nlog2n）和O（n2 ）之间，大致为O（n1. 3）。 稳定性：不稳定,三、希尔排序,23,练习:,请写出一下待排序序列，在执行直接插入排序，折半插入排序，希尔排序过程中，每趟

10、插入后的序列。 8，3，9，2，1，9，7，4，6，5,24,9.3 选择排序,一、简单选择排序 基本思想： 第一次从r0rn-1中选取最小值，与r0交换，第二次从r1rn-1中选取最小值，与r1交换，第i次从ri-1rn-1中选取最小值，与ri-1交换，, 第n-1次从rn-2rn-1中选取最小值，与rn-2交换。总共通过n-1次，得到一个按排序码从小到大排列的有序序列。,25,2. 简单选择排序举例 待排序序列：(8，3，2，1，7，4，6，5),一、简单选择排序,8,3,2,1,7,4,6,5,初始状态,数组角标：,8,3,2,1,7,4,6,5,第一趟,1,3,2,8,7,4,6,5,

11、第二趟,26,2. 简单选择排序举例 待排序序列：(8，3，2，1，7，4，6，5),一、简单选择排序,8,3,2,1,7,4,6,5,初始状态,数组角标：,8,3,2,1,7,4,6,5,第一趟,1,2,3,8,7,4,6,5,第二趟,1,2,3,8,7,4,6,5,第三趟,1,2,3,8,7,4,6,5,第四趟,27,2. 简单选择排序举例 待排序序列：(8，3，2，1，7，4，6，5),一、简单选择排序,8,3,2,1,7,4,6,5,初始状态,数组角标：,8,3,2,1,7,4,6,5,第一趟,1,2,3,8,7,4,6,5,第二趟,1,2,3,8,7,4,6,5,第三趟,1,2,3,

12、4,7,8,6,5,第四趟,1,2,3,4,7,8,6,5,第五趟,28,2. 简单选择排序举例 待排序序列：(8，3，2，1，7，4，6，5),一、简单选择排序,8,3,2,1,7,4,6,5,初始状态,数组角标：,8,3,2,1,7,4,6,5,第一趟,1,2,3,8,7,4,6,5,第二趟,1,2,3,8,7,4,6,5,第三趟,1,2,3,4,7,8,6,5,第四趟,1,2,3,4,5,8,6,7,第五趟,1,2,3,4,5,8,6,7,第六趟,29,2. 简单选择排序举例 待排序序列：(8，3，2，1，7，4，6，5),一、简单选择排序,8,3,2,1,7,4,6,5,初始状态,数组

13、角标：,8,3,2,1,7,4,6,5,第一趟,1,2,3,8,7,4,6,5,第二趟,1,2,3,8,7,4,6,5,第三趟,1,2,3,4,7,8,6,5,第四趟,1,2,3,4,5,8,6,7,第五趟,1,2,3,4,5,8,6,7,第六趟,1,2,3,4,5,6,8,7,第七趟,30,3. 简单选择排序算法的实现 void SelectSort(Node r,int n) int min; Node temp; for(int i=0;in-1;i+) /n-1趟选择 min = i; for(int j=i+1;j=n-1;j+) if(rj.key rmin.key) min =

14、j; if (i!=min) /第i趟选择出的最小值，放在第i位 temp = ri; ri = rmin; rmin = temp; ,简单选择排序,一、简单选择排序,31,4. 简单选择排序分析 在简单选择排序中，共需要进行n-1次选择和交换，每次选择需要进行n-i次比较（1in-1），而每次交换最多需3次移动， 因此总的比较次数C=(n2-n)/2 总的移动次数 M = 3(n-1) 简单选择排序的时间复杂度为O(n2)数量级 通常比直接插入排序的执行速度要快一些。 稳定性：不稳定,一、简单选择排序,32,二、堆排序 堆的定义 若有n个元素的排序码k0，k1，k2，kn-1，当满足如下条

15、件： kik2i+1 kik2i+1 （1） kik2i+2 或 (2) kik2i+2 其中i=0,1,2,(n-1)/2 则称此n个元素的关键字k0， k1，k2，kn-1为一个堆。,9.3 选择排序,33,若将此关键字按顺序组成一棵完全二叉树， （1）称为小根堆：二叉树的所有根结点值小于或等于左右孩子的值 （2）称为大根堆：二叉树的所有根结点值大于或等于左右孩子的值。,(a),(a)完全二叉树 (b)大根堆,34,若n个元素的关键字k0 ，k1，k2，k3，kn-1满足堆，且让结点按0、1、2、3、n-1顺序编号，根据完全二叉树的性质（若i为根结点，则左孩子为2i+1，右孩子为2i+2）

16、可知，堆排序实际与一棵完全二叉树有关。若将关键字初始序列组成一棵完全二叉树，则堆排序可以包含建立初始堆（使关键字变成能符合堆的定义的完全二叉树）和利用堆进行排序两个阶段。 堆排序的基本思想：分两步 给定关键字49，38，65，97，76，13，27，70讲述,35,把根结点加入到小根堆中的算法,只有一个结点的树是堆； 若除根结点以外的左子树和右子树均为堆，则把跟根结点加入到堆中的过程如下： （1）若根结点不大于左孩子和右孩子，则直接加入就成堆。 （2）否则，取左孩子和右孩子中较小值与根结点交换；且若左（右）孩子与根结点交换后，左（右）子树的堆结构可能被破坏，所以，要把以左（右）孩子作为根结点，

17、加入到左（右）子树除根结点外的堆中。,36,(1) 建立初始堆：,37,初始化创建最大堆算法,void InitCreatHeap(DataType a, int n) int i; for(i = (n-1)/2; i = 0; i-) CreatHeap(a, n, i); ,38,建堆算法的实现： void CreatHeap (DataType a, int n, int h) int i, j, flag; DataType temp; i = h; / i为要建堆的二叉树根结点下标 j = 2*i+1; / j为i的左孩子结点的下标 temp = ai; while(j aj.ke

18、y) break; /标记结束筛选条件 else /否则把aj上移 ai = aj; i = j; j = 2*i+1; ai = temp; /把最初的ai赋予最后的aj ,39,堆排序算法思想,把n个待排序序列建立成一个大（小）根堆 取堆中的根结点即为当前最大（小）值，把待排序序列中的最后一个元素与堆中的根结点交换；则待排序序列个数减1，有序序列个数加1； 重复上述过程，直到待排序序列长度变为1.,40,(2)交换与重构堆,41,堆排序过程,初始状态,42,堆排序过程,初次建堆,43,堆排序过程,根结点与堆底交换,有序,无序,44,堆排序过程,重新建堆,有序,无序,45,堆排序过程,有序,

19、无序,根结点与堆底交换,46,堆排序过程,有序,无序,重新建堆,47,堆排序过程,有序,无序,根结点与堆底交换,48,堆排序过程,有序,无序,重新建堆,49,堆排序过程,有序,无序,根结点与堆底交换,50,堆排序过程,有序,无序,重新建堆,51,堆排序过程,有序,无序,根结点与堆底交换,52,堆排序过程,有序,无序,重新建堆,53,堆排序过程,有序,无序,根结点与堆底交换,54,堆排序过程,有序,无序,重新建堆,55,堆排序过程,有序,根结点与堆底交换,56,堆排序算法如下： void HeapSort(DataType a, int n) int i; DataType temp; Init

20、CreatHeap(a, n); /初始化创建最大堆 for(i = n-1; i 0; i-) /当前最大堆个数每次递减1 /把堆顶a0元素和当前最大堆的最后一个元素交换 temp = a0; a0 = ai; ai = temp; CreatHeap(a, i, 0);/调整根结点满足最大堆 ,57,堆排序的效率分析 在整个堆排序中，共需要进行n+(n-1)/2 -1次筛选运算，每次筛选运算进行双亲和孩子或兄弟结点的排序码的比较和移动次数都不会超过完全二叉树的深度， 所以，每次筛选运算的时间复杂度为O(log2n)，故整个堆排序过程的时间复杂度为O(nlog2n)。 堆排序占用的辅助空间为

21、1（供交换元素用），故它的空间复杂度为O（1）。 堆排序是一种不稳定的排序方法，例如，给定排序码：2，1，2，它的排序结果为：1，2，2。,58,练习:,请写出一下待排序序列，在执行简单选择排序和堆排序过程中，每趟排序后的序列。 8，3，9，2，1，9，7，4，6，5,59,9.4 交换排序,一、冒泡排序 基本思想： 通过对待排序序列从后向前（从下标较大的元素开始），依次比较相邻元素的排序码，若发现逆序则交换，使排序码较小的元素逐渐从后部移向前部（从下标较大的单元移向下标较小的单元），就象水底下的气泡一样逐渐向上冒。 每趟冒泡可得到一个有序元素，所以最多经过n-1趟冒泡即可对n个元素排好序,轻

22、者自轻 浊者自浊,在一趟冒泡中若没有发生数据交换，则表明序列已经有序，可以提前结束循环,60,例如:待排序序列为：17，3，25，14，20，9。,第三趟排序后，序列已有序，所以第四趟排序没有数据交换，所以第五趟就不用再做了。,61,冒泡算法的实现 void BubbleSort(Node r,int n) int i, j, flag; /当flag为0则停止排序 Node temp; for ( i=1; i=i; j-) if (rj.keyrj-1.key) /发生逆序 temp=rj; rj=rj-1; rj-1=temp; flag=1; /交换，并标记发生了交换 if(flag=

23、0) break; ,冒泡排序,62,冒泡排序的效率分析 从冒泡排序的算法可以看出，若待排序的元素为正序，则只需进行一趟排序，比较次数为（n-1）次，移动元素次数为0；若待排序的元素为逆序，则需进行n-1趟排序，比较次数为(n2-n)/2，移动次数为3(n2-n )/2，因此冒泡排序算法的时间复杂度为O（n2）。由于其中的元素移动较多，所以属于内排序中速度较慢的一种。 因为冒泡排序算法只进行元素间的顺序移动，所以是一个稳定的算法。,63,基本思想： 任取待排序序列中的某个元素作为基准（一般取第一个元素），通过一趟排序，将待排元素分为左右两个子序列，左子序列元素的排序码均小于或等于基准元素的排序

24、码，右子序列的排序码则大于基准元素的排序码，然后分别对两个子序列继续进行排序，直至整个序列有序。,二、快速排序,64,快速排序是对冒泡排序的一种改进方法，算法中元素的比较和交换是从两端向中间进行的，排序码较大的元素一次就能够交换到后面单元，排序码较小的记录一次就能够交换到前面单元，记录每次移动的距离较远，因而总的比较和移动次数较少。 快速排序（Quick Sorting）是迄今为止所有内排序算法中速度最快的一种。,65,示例：给定关键字(46，55，13，42，94，05，17，70)，具体划分如图所示。,66,46 55 13 42 94 05 17 70 ,46 55 13 42 94 0

25、5 17 70 ,17 55 13 42 94 05 46 70 ,17 46 13 42 94 05 55 70 ,17 05 13 42 94 46 55 70 ,17 05 13 42 94 46 55 70 ,17 05 13 42 94 46 55 70 ,17 05 13 42 46 94 55 70 ,67,快速排序算法的实现 分区处理(确定枢轴位置)： int pivot(Node r,int low,int high) int i=low,j=high; Node x = ri; /以分区的首个元素做枢轴元素 while(i=x.key) j-; if(ij) ri = rj

26、; i+; while(ij) ,68,快速排序的递归算法： void QuickSort(node r,int low,int high) int i; if(lowhigh) i = pivot(r,low,high); QuickSort(r,low,i-1); QuickSort(r,i+1,high); ,快速排序,69,3.快速排序的效率分析 若快速排序出现最好的情形（左、右子区间的长度大致相等），类似完全二叉树的结构，所以分解次数与完全二叉树的深度相等，而每趟比较的次数接近于n-1，因此，快速排序的最好时间复杂度应为O（nlog2n）。而且在理论上已经证明，快速排序的平均时间复杂

27、度也为O（nlog2n）。,70,若快速排序出现最坏的情形（每次能划分成两个子区间，但其中一个是空），则这时得到的二叉树是一棵单分枝树，深度为n，因此，快速排序的最坏时间复杂度为O(n2)。 快速排序所占用的辅助空间为栈的深度，故最好的空间复杂度为O（log2n），最坏的空间复杂度为O(n)。 快速排序是一种不稳定的排序方法。,71,练习:,请写出一下待排序序列，在执行冒泡排序和快速排序过程中每趟排序的排序序列。 6 , 5, 3, 7, 8, 9, 2, 1,72,9.5 归并排序,二路归并排序的基本思想 将相邻的两个有序子区间（有序表）合并成一个有序子区间，一次合并完成后，有序子区间的数目

28、减少一半，而区间的长度增加一倍，当区间长度从1增加到n（元素个数）时，整个区间变为一个，则该区间中的有序序列即为我们所需的排序结果。 例如，给定关键字 46，55，13，42，94，05，17，70， 二路归并排序过程如下图所示。,73,74,二路归并排序算法实现 将两个有序序列合并成一个有序序列 void MergePass(node r,int low,int mid,int high,node r2) int i=low,j=mid+1,k=low-1; while(i=mid) ,75,归并排序主体算法： void MergeSort(node r,node r1,int s,int

29、t) node r2MaxSize; if(s=t) r1s = rs; /只有一个待排序元素 else MergeSort(r,r2,s,(s+t)/2); MergeSort(r,r2,(s+t)/2+1,t); MergePass(r2,s,(s+t)/2,t,r1); ,归并排序,76,（1）时间性能 a. 第i趟所需时间： 记录移动次数为n次 两有序区间合并时，记录的比较次数=记录移动次数 每趟归并的时间复杂度均为O(n) b. 共需要进行log2n 趟归并 所以总时间复杂度为O(nlog2n),二路归并排序的效率分析,77,（2）空间性能 两有序序列进行归并时需要等长的辅助空间 因

30、此空间复杂度为O(n) （3）稳定性 ： 稳定,二路归并排序的效率分析,78,9.6 基数排序-多关键字排序,一、示例：扑克牌排序 2 3 k A 2 3 KA 2 3 K A 2 3 k A 扑克牌排序：先看面值，后看花色（多关键字） 针对多关键字排序，一般采用基数排序。,79,基数排序的基本思想是： 根据排序关键字的优先级，按从低到高的次序对待排序序列进行按序分类并按序回收。 例如：若对小于1000的整数待排序序列进行基数排序。 先按个位进行有序分类 再按十位进行有序分类 最好按百位进行有序分类,9.6 基数排序-多关键字排序,80,二、基数排序的基本思想以多位数排序为例 278 109

31、063 930 589 184 505 269 008 083,第一遍：按个位数放入10个箱子（队列）,按0-9的顺序从10个箱子中取出数字,930 063 083 184 505 278 008 109 589 269,278,109,063,930,589,184,505,269,008,083,81,第二遍：再将所得数列按十位数依次入箱,930 063 083 184 505 278 008 109 589 269,再按0-9的顺序从10个箱子中取出数字,505 008 109 930 063 269 278 083 184 589,930,063,083,184,505,278,008

32、,109,589,269,82,例. 多位数排序 278 109 063 930 589 184 505 269 008 083,第三遍：再将所得数列按百位数依次入箱,930 063 083 184 505 278 008 109 589 269,505 008 109 930 063 269 278 083 184 589,再按0-9的顺序从10个箱子中取出数字,008 063 083 109 184 269 278 505 589 930,008,505,109,930,063,269,278,083,184,589,0 1 2 3 4 5 6 7 8 9,83,9.7 各种内排序方法的比

33、较和选择,一、各种内排序方法比较考虑的因素 最好时间复杂度 最坏时间复杂度 平均时间复杂度 空间复杂度 稳定性,84,各种排序算法性能比较,O(n2),O(n2),O(n2),O(n1.3),O(nlog2n),O(nlog2n),O(nlog2n),O(mn),O(n2),O(n2),O(n2),O(n2),O(n2),O(nlog2n),O(nlog2n),O(mn),O(n),O(n),O(n1.3),O(nlog2n),O(nlog2n),O(nlog2n),O(n2),O(mn),85,各种排序算法性能比较,O(log2n),O(n),O(mn),是,否,是,是,是,否,否,O(1)

34、,O(1),O(1),O(1),O(1),86,二、各种内排序方法的选择 1从时间复杂度选择 n较大时：可以选快速排序、堆排序、归并排序 n较小时：可以选简单排序方法。 2从空间复杂度选择 优先次序： O(1)-O(log2n)- O(n),9.7 各种内排序方法的比较和选择,87,(1) 当待排序元素的个数n较大，排序码分布是随机，而对稳定性不做要求时，则采用快速排序为宜。 （2)当待排序元素的个数n大，内存空间允许，且要求排序稳定时，则采用二路归并排序为宜。 （3）当待排序元素的个数n大，排序码分布可能会出现正序或逆序的情形，且对稳定性不做要求时，则采用堆排序或二路归并排序为宜。,9.7

35、各种内排序方法的比较和选择,3一般选择规则,88,（4)当待排序元素的个数n小，元素基本有序或分布较随机，且要求稳定时，则采用直接插入排序、冒泡法排序为宜。 (5)当待排序元素的个数n小，对稳定性不做要求时，则采用简单选择排序、直接插入排序、冒泡法排序。,9.7 各种内排序方法的比较和选择,3一般选择规则,89,实验预告,随机产生n （n由用户输入）个整数（大小范围：09999），将其存于数组A0n-1中。 调用直接插入排序、希尔排序、冒泡排序、快速排序等算法进行排序，并统计出各种排序算法的在的平均比较次数和平均移动次数以及所需的运行时间 。 测试时为n赋值100、200、300、1 000和2 000及更多。,90,本章小结,本章主要介绍了排序的基本思想和基本概念；按照排序的分类介绍插入排序(直接插入排序和希尔排序) 、选择排序(直接选择排序、堆排序) 、交换排序(冒泡排序、快速排序)的思想、算法及分析；同时也讲述了归并排序和基数排序的思想和算法，并对各种排序算法性能进行了分析与比较。,91,课外阅读,1、快速排序中枢点的选择。 2、SHELL排序中增量的选择。 3、其它的排序算法(如2-路插入排序等)？,