第十章 排序.ppt

1、第八章 内部排序,8.1 概述 8.2 插入类排序 8.3 交换类排序 8.4 选择类排序 8.5 归并类排序 8.6 基数排序 8.7 各种内部排序方法的比较讨论,8.1 概述,记录：记录是由一个或多个数据项根据一定的目的而组成的数据项集合。 数据项：数据项是不可分的最小数据单位。一个数据项由若干个字符或数字组成，它代表某一事物的一种属性。数据项又称为数据域、字段、属性。 关键字：是数据元素（或称为“记录”）中某个数据项的值，它可以标识（识别）一个数据元素。 主关键字：可以识别唯一一个数据元素。 次关键字：能够识别若干个数据元素。,8.1 概述,8.1 概述,排序:是将一些数据元素（或记录）

2、的任意序列，重新排列成一个按关键字有序的序列。 例如：将下列关键字序列 52，36，80，36，14，58，61，23，97，75 调整为 14，23，36，36，52，58，61，75，80，97,一般情况下:假设含n个记录的序列为R1,R2,Rn 其相应的关键字序列为K1,K2,Kn这些关键字相互之间可以进行比较，即在它们之间存在着这样一个关系Kp1 Kp2 Kp3 Kpn按此固有关系将上式记录序列重新排列为Rp1,Rp2,Rpn的操作称作排序。,8.1 概述,排序算法的分类： 按排序过程中涉及的存储器不同，可将排序方法分为两大类： 内部排序：若整个排序过程不需要访问外存便能完成，则称此类

3、排序问题为内部排序； 外部排序：在排序过程中，若参加排序的记录数量很大，不仅要使用内存，而且还需要访问外存的排序过程称为“外部排序。,排序算法的稳定性： 如果待排序记录中存在多条关键字相同的记录，经过排序后，这些记录之间的相对次序不变，则称这种排序算法为“稳定的”；反之，称为“不稳定的”。,内部排序的方法: 内部排序的过程是一个逐步扩大记录的有序序列长度的过程。,一趟排序,8.1 概述,内部排序的方法: 逐步扩大记录有序序列长度的方法大致有以下几类： 1、插入类:将无序子序列中的一个或几个记录“插入”到有序序列中，从而增加记录的有序子序列的长度 2、交换类:通过“交换”无序序列中的记录从而得到

4、其中关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度。,8.1 概述,内部排序的方法: 3、选择类:从记录的无序子序列中“选择”无序子序列中关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度。 4、归并类:通过“归并”两个或两个以上的记录有序子序列，逐步增加记录有序序列的长度。 5、其他方法,8.1 概述,8.1 概述,排序算法的评价标准： 1. 算法的时间复杂度 2. 执行算法所需的附加空间 3. 算法本身的复杂性 排序过程中需进行的两种基本操作： 1.比较两个关键字的大小（必须） 2.将记录从一个位置移动到另一个位置(是

5、否需要移动记录取决于记录的存储方式) 顺序存储：必须移动记录 链式存储：不须移动记录，只需修改指针,本章实现排序算法时记录所采用的存储结构： typedef struct KeyType key; /主关键字域，KeyType为int等 / 其它属性域 RecType ; 也即：本章所介绍的排序算法都是在一维结构体数组上实现的。,8.1 概述,8.2 插入类排序,8.2.1 直接插入排序 1. 基本思想 将一个记录插入到已经排好序的有序表中，从而得到一个新的记录数增加1的有序表。 一般情况下，第i趟直接插入排序的操作为：在含有i-1个记录的有序子序列R1.i-1中插入一个记录Ri，变成含有i

6、个记录的有序子序列R1i。,8.2.1 直接插入排序,8.2.1 直接插入排序,2. 算法描述 void insertsort(RecType R, int n) /* R为存放待排序数据元素（记录）的一维数组，大小为n+1，其中R0置空，R1到Rn为待排序的n个记录*/ for(i=2;iR0.key; j- -) Rj+1=Rj; Rj+1=R0; ,8.2.1 直接插入排序,3.算法分析 直接插入排序的算法简洁，容易实现。 从时间看，排序的基本操作为：比较两个记录的大小和移动记录。其中：（1）最小比较次数：Cmin = n-1 = O(n)（2）最大比较次数：Cmax =(2+3+n)=

7、 (n+2)(n-1)/2 = O(n2 )（3）最小移动次数：Mmin = 0 （4）最大移动次数：Mmax = (3+n+n+1) = O(n2) 故：该算法适应于待排序记录的数量n很小的情况。 从空间看，直接插入排序只需一个辅助空间。,8.2.1 直接插入排序,4.改进算法 在直接插入排序的基础上，从减少“比较”和“移动”这两种操作的次数着手，可得到一些改进的插入排序算法，如： 折半插入排序：可以减少关键字之间的比较次数，但移动次数不变，故时间复杂度仍为O（n2）。其基本思想是利用折半查找来找要插入的位置。,2_路插入排序:可以减少排序过程中移动记录的次数，但为此需要n个记录的辅助空间。

8、 例：初始关键字： 49 38 65 97 76 13 27 49 i=1: (49) first| final i=2: （49) (38) final| |first i=3: (49 65) (38) |final |first i=4: (49 65 97) (38) |final |first i=5: (49 65 76 97) (38) |final |first i=6: (49 65 76 97) (13 38) |final |first i=7: (49 65 76 97) (13 27 38) |final |first i=8: (49 49 65 76 97 13

9、27 38) |final |first,移动次数约为n2/8.因此，这种方法只能减少移动次数，而不能避免移动。并且当第一个元素是待排序记录中最小或最大的记录时，该方法就完全失去它的优越性。,表插入排序：就是通过链接指针，按关键码的大小，实现从小到大的链接过程，为此需增设一个指针项。操作方法与直接插入排序类似，所不同的是直接插入排序要移动记录，而表插入排序是修改链接指针。用静态链表来说明。,表插入排序得到一个有序的链表，查找则只能进行顺序查找，而不能进行随机查找，如折半查找。为此，还需要对记录进行重排。 重排记录方法：按链表顺序扫描各结点，将第i个结点中的数据元素调整到数组的第i个分量数据域。

10、因为第i个结点可能是数组的第j个分量，数据元素调整仅需将两个数组分量中数据元素交换即可，但为了能对所有数据元素进行正常调整，指针域也需处理。,void Arrange (SqList / p 指向下一个将要调整的记录 / for / Arrange,8.2.3 希尔排序,Shell排序，又称“缩小增量排序”，它也属于插入类排序，它是对直接插入排序的一种改进算法。在时间效率上比直接插入排序有较大的提高。 从对直接插入排序的分析可知，其最好的情况下时间复杂度是O（n），最坏的情况下时间复杂度为O(n2), 但是当待排序的记录已经处于“基本有序”状态时或当n值较小时，直接插入排序的效率均可大大提高。

11、 Shell 排序方法正是基于这两点考虑，对直接插入排序加以改进而提出的一种插入排序算法。,8.2.3 希尔排序,1.基本思想 Shell排序，又称“缩小增量排序”， 先将整个待排序序列分割成为若干个子序列，分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。 例如：假设待排序的10个记录，其关键字分别是： 49，38，65，97，76，13，27，49/，55，04 。增量序列取值依次为：5，3，1。则对其进行希尔排序的过程如下：,8.2.3 希尔排序,49 38 65 97 76 13 27 49/ 55 04,13 27 49/ 55 04 49 3

12、8 65 97 76,一趟排序结果（步长为5）,二趟排序结果（步长为3）,13 04 49/ 38 27 49 55 65 97 76,04 13 27 38 49/ 49 55 65 76 97,三趟排序结果,8.2.3 希尔排序,2.算法分析 Shell 排序的分析是一个复杂的数学问题，特别是如何选择增量序列才能产生最好的排序效果问题。因此，到目前为止还没能求得一种最好的增量序列。但不管是哪一种增量序列，最后一个增量值必须是1。 增量序列可以有多种取法，常用的增量序列是Shell本人最初提出的：取di=n/2, di+1=di/2, , dt=1,其中t=log2n。 目前研究已得知，当n

13、在某个特定范围内时，Shell 排序的平均比较次数和平均移动次数都是n1.3左右，当n时可减少至n ( log2n )2。,8.2.3 希尔排序,练习题：已知待排序的11个数据元素，其关键字分别是： 67，58，25，97，82，11，24，6，39，4，56 ，采用希尔排序将其按关键字排列为递增有序的序列，增量序列取值依次为：5，3，1。,8.3 交换类排序,一、冒泡排序 1.算法思想（从小到大排序） 相邻两数比较，若前面数大，则两数交换位置，直至最后一个元素被处理，最大的元素就“沉”到最下面，即在最后一个元素位置。这样，如有n个元素，共进行上述操作n-1趟，每趟让剩余元素中最大的元素“沉”

14、到下面，从而完成排序。,第一次65和78比较后结果： 65 78 43 21 90 17,输入数据： 65 78 43 21 90 17 第一趟排序过程如下：,第二次78和43比较后结果 ： 65 43 78 21 90 17,第三次78和21比较后结果： 65 43 21 78 90 17,第四次78和90比较后结果： 65 43 21 78 90 17,第五次90和17比较后结果： 65 43 21 78 17 90,8.3 交换类排序,结果：经过第一趟排序，得到最大值为90，放入最 后一个位置。,8.3 交换类排序,整个排序排序过程如下：,65 78 43 21 90 17,65 43

15、21 78 17 90,43 21 65 17 78 90,21 43 17 65 78 90,21 17 43 65 78 90,17 21 43 65 78 90,第1趟冒泡排序,第2趟冒泡排序,第3趟冒泡排序,第4趟冒泡排序,第5趟冒泡排序,结论：6个数据需要进行5趟排序， n个数据需要进行n1趟排序，第i趟排序需要比较n-i次。,2.算法描述（从小到大排序） void BubbleSort(RecType R,int k) int i,j, flag; RecType t; for (j=0;jRi+1.key) t=Ri; Ri=Ri+1; Ri+1=t; /*相邻记录交换位置*/

16、flag=1; /*有元素交换,标志置1*/ if (flag=0) break; /*没有交换元素，结束循环*/ ,8.3 交换类排序,8.3 交换类排序,3.算法分析 最好的情况下:初始序列为“正序”，只需进行一趟排序，进行n-1次比较，不需要移动任何记录； 最坏的情况下:初始序列为“逆序”，则需要进行n-1趟排序，第i（1in-1）趟排序需要比较n-i次共(n-1)n/2次比较，同时还要移动元素3n(n-1)/2次。 因此，冒泡排序总的时间复杂度是O(n2).,二、快速排序 1.基本思想 通过一趟排序将待排序的记录分割成两个独立的部分，其中一部分记录的关键字均比另一部分记录的关键字小，然

17、后再分别对这两部分记录继续进行排序，以达到整个序列有序。 2.做法 首先选取一个记录作为“枢轴”（通常选第一个记录），以它的关键字为基准重排其余记录：将所有关键字比它大的记录都排在它之后，而将所有关键字比它小的记录都排在它之前，由此完成一趟快速排序。之后，分别再对这两个子序列进行快速排序。,8.3 交换类排序,具体操作为： 附设两个指针low和high，它们的初值分别为1和n，设枢轴记录的关键字为key（一般取第一个关键字作为key）。 首先从high所指的位置起向前搜索，找到第一个比key小的关键字，交换位置； 然后从low所指的位置起向后搜索，找到第一个比key大的关键字，交换位置； 重复

18、上两步直至low=high为止。,8.3 交换类排序,49 38 65 97 76 13 27 49/,27 38 65 97 76 13 49 49/,27 38 49 97 76 13 65 49/,27 38 13 97 76 49 65 49/,27 38 13 49 76 97 65 49/,初始关键字,第2次交换后,第3次交换后,第4次交换后,第1次交换后,完成一趟快 速排序,8.3 交换类排序, 27 38 13 49 76 97 65 49/ , 49 38 65 97 76 13 27 49/ , 13 27 38 , 49/ 65 76 97 ,49/ 65, 13 27

19、38 49 49/ 65 76 97 ,一次划分之后,初始状态,分别进行快速排序,最后结果,快速排序示例,8.3 交换类排序,2.算法描述（从小到大排序） void QuickSort(RecType R, int low,int high) /* R为待排序记录的集合*/ int mid; if(lowhigh) mid=Partition(R,low,high); QuickSort(R,low,mid-1); QuickSort (R,mid+1,high); ,8.3 交换类排序,int Partition(RecType R, int low,int high) int mid=Rl

20、ow.key; RecType pass; while(low=mid) -high; pass=Rlow; Rlow=Rhigh; Rhigh=pass; while(lowhigh ,8.3 交换类排序,3.性能分析 快速排序的平均时间复杂度是O(nlogn),它是目前基于比较的内部排序方法中速度最快的一种，快速排序也因此而得名。 但是，若初始的关键字序列已经“基本有序”时，快速排序将退化为冒泡排序，其时间复杂度为O（n2）。如：初始关键字序列为： 45 50 70 60 15 10 23 17 快速排序过程中需要一个栈空间来实现递归，因此空间复杂度不如前几种排序方法。,8.3 交换类排序

21、,练习题：已知待排序的关键字序列是： 67，25，82，11，24，6，39，4 ，采用快速排序法将其按关键字排列为递增有序的序列。,8.3 交换类排序,8.4 选择类排序,选择排序的基本思想：每一趟在n-i+1（i1,2,n-1)个记录中选取关键字最小的记录，作为有序序列中的第i个记录。 8.4.1 简单选择排序 1.基本思想 第i 趟（1in）简单选择排序的操作为：通过n-i次关键字的比较，从n-i+1个记录中选出关键字最小的记录，并和第i个记录交换位置。,8.4.1 简单选择排序,例如，用简单选择排序对如下关键字序列进行排序：,65 78 43 21 90 17,17 78 43 21

22、90 65,17 21 43 78 90 65,17 21 43 78 90 65,17 21 43 65 90 78,17 21 43 65 78 90,第1趟选择排序,第2趟选择排序,第3趟选择排序,第4趟选择排序,第5趟选择排序,2.算法描述 void SelectSort(SecType R ,int n) /* R为待排序记录的集合，n为待排序记录的条数*/ int i; SecType t; for(i=0;iRj.key) k=j; if(k!=i)t=Ri;Ri=Rk;Rk=t; ,8.4.1 简单选择排序,8.4.1 简单选择排序,3.性能分析 最好的情况下：记录移动的次数为

23、0；最坏的情况下，记录移动的次数为 3(n-1) 次。 但无论在什么情况下，需要进行的关键字间的比较次数均为 n(n-1)/2。 因此，总的时间复杂度是O(n2).,改进的方法：减少关键字间的比较次数。 如何减少？ 体育锦标赛就是一种改进了的选择排序方法。,8.4.2 堆排序,1.堆的定义 堆是一个关键字序列k1,k2,kn,它具有如下特性： ki k2i , ki k2i+1 或者 ki k2i , ki k2i+1 其中 (i=1,2, n/2),若将此序列所对应的一维数组看作是一棵完全二叉树的顺序存储结构，则堆的含义表明： 完全二叉树中任一结点的关键字都小于或等于它的左右孩子的关键字（小

24、顶堆）； 或者完全二叉树中任一结点的关键字都大于或等于它的左右孩子的关键字（大顶堆）。,8.4.3 堆排序,判断下列关键字序列是否是堆： 5,23,16,68,94, 20,71,73 96,83,27,38,11,9,最小值,最大值,8.4.3 堆排序,2.堆排序的基本思想 若在输出堆顶的最小值之后，调整剩余的n-1个元素序列为一个新的堆，则可得到n个元素中的次小值。如此反复，便能得到一个有序序列，这个过程称之为堆排序。 实现堆排序要解决的两个问题是： （1）如何由一个无序序列建成一个堆？ （2）如何在输出堆顶元素后，调整剩余元素为一个堆？,8.4.3 堆排序,如何在输出堆顶元素后，调整剩余

25、元素为一个堆？ 方法是：以堆中的最后一个元素和堆顶元素进行交换，此时根结点的左、右子树均为堆，然后从上到下逐层调整即可。,左右子树均为堆,8.4.3 堆排序,逐步调整为新堆的过程如下:,左子树为堆,调整右子树,8.4.3 堆排序,重复此过程，直至输出所有关键字为止,输出：5，16，20，,上述从堆顶到叶子的调整过程称为“筛选”。 从一个无序序列建堆的过程就是一个反复“筛选”的过程。,8.4.3 堆排序,3.建堆过程 将无序序列看成是一个完全二叉树，则最后一个非叶子结点就是第n/2个结点，因此“筛选”只需要从第n/2个结点开始（一个叶子结点一定是一个堆）。 例如：已知8个元素的无序序列为： 49

26、，38，65，97，76，13，27，49/ ， 它所对应的完全二叉树如下图a 所示，要求创建一个小顶堆。 逐步筛选，从第4个元素97开始：,8.4.3 堆排序,无序序列： 49，38，65，97，76，13，27，49/ ,图a：无序序列,图b：97被筛选后的状态,调整以97为根的子树,8.4.3 堆排序,图d：65被筛选后的状态,图c：调整以65为根的子树,8.4.3 堆排序,图f：38被筛选后的状态,图e：调整以38为根的子树,图g：调整以49为根的树,图h：49被筛选后建成的堆,图h即为一个新建的小顶堆，小顶堆建立后，堆顶就是最小关键字。,void HeapAdjust (Elem R

27、 , int s, int m) rc=Rs; for ( j=2*s;j=Rj.key) break; /rc应插入在位置s上 Rs=Rj; s=j; Rs=rc; /插入,void HeapSort (Elem R , int n) / 对记录序列R1n进行堆排序 for (i=n/2;i0;-i) HeapAdjust (R,i,n); /建大顶堆 for (i=n;i1;-i) R1 Ri; /将堆顶记录和当前未经排序子序列 /R1i中最后一个记录相互交换 HeapAdjust(R,1,i-1); / 对R1进行筛选 ,10.4.3 堆排序,4.性能分析： 堆排序的时间主要由建立初始堆

28、和不断重复调整堆这两部分的时间开销构成。 经分析，堆排序在最坏情况下的总的时间复杂度是 ：O(n log2n)。相对于快速排序来说，这是堆排序的最大优点。 在空间上，堆排序仅需一个记录大小供交换使用的辅助空间。 由于初始建堆所需的比较次数较多，所以堆排序不适于记录数较少的文件，但对n较大的文件是很有效的。,8.5 归并类排序,所谓“归并”是指：将两个有序的序列合并为一个新的有序序列。 1.基本思想 将待排序序列看成为n个长度为1 的有序子序列，把这些子序列两两进行归并，便得到n/2 个长度为2的有序子序列，然后再两两归并，, 如此重复，直到最后得到一个长度为n的有序序列为止，这种方法成为二路归

29、并方法。,8.5 归并类排序,例如：采用2路归并法将无序序列 49, 38, 65, 97, 76, 13, 27, 49/ 排列为一个递增有序序列。,49 38 65 97 76 13 27 49/,38 49 65 97 13 76 27 49/,38 49 65 97 13 27 49/ 76,13 27 38 49 49/ 65 76 97,初始无序序列,第一趟归并之后,第二趟归并之后,第三趟归并之后,8.5 归并类排序,2.性能分析 对n个记录的序列进行2-路归并排序时，必须进行 log2n 趟归并，而每趟归并所需的时间是O(n), 所以二路归并排序算法时间复杂度为O(nlog2n)。 与快速排序相比，归并排序的最大优点是，它是一种稳定的排序方法，但在一般情况下，很少利用2-路归并排序进行内部排序。,前介绍的