第十章 排序.ppt

1、第十章 内部排序,10.1 概述 10.2 插入类排序 10.3 交换类排序 10.4 选择类排序 10.5 归并类排序 10.6 基数排序 10.7 各种内部排序方法的比较讨论,10.1 概述,排序:是将一些数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列。 例如：将下列关键字序列 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

2、 Kpn按此固有关系将上式记录序列重新排列为Rp1,Rp2,Rpn的操作称作排序。,10.1 概述,排序算法的分类： 按排序过程中涉及的存储器不同，可将排序方法分为两大类： 内部排序：若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序； 外部排序：在排序过程中，若参加排序的记录数量很大，不仅要使用内存，而且还需要访问外存的排序过程称为“外部排序。,排序算法的稳定性： 如果待排序记录中存在多条关键字相同的记录，经过排序后，这些记录之间的相对次序不变，则称这种排序算法为“稳定的”；反之，称为“不稳定的”。,内部排序的方法: 内部排序的过程是一个逐步扩大记录的有序序列长度的过程。,一趟

3、排序,10.1 概述,内部排序的方法: 逐步扩大记录有序序列长度的方法大致有以下几类： 1、插入类:将无序子序列中的一个或几个记录“插入”到有序序列中，从而增加记录的有序子序列的长度 2、交换类:通过“交换”无序序列中的记录从而得到其中关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度。,10.1 概述,内部排序的方法: 3、选择类:从记录的无序子序列中“选择”无序子序列中关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度。 4、归并类:通过“归并”两个或两个以上的记录有序子序列，逐步增加记录有序序列的长度。 5、其他方法,1

4、0.1 概述,10.1 概述,排序算法的评价标准： 1. 算法的时间复杂度 2. 执行算法所需的附加空间 3. 算法本身的复杂性 排序过程中需进行的两种基本操作： 1.比较两个关键字的大小（必须） 2.将记录从一个位置移动到另一个位置(是否需要移动记录取决于记录的存储方式) 顺序存储：必须移动记录 链式存储：不须移动记录，只需修改指针,本章实现排序算法时记录所采用的存储结构： typedef struct KeyType key; /主关键字域，KeyType为int等 / 其它属性域 RecType ; 也即：本章所介绍的排序算法都是在一维结构体数组上实现的。,10.1 概述,10.2 插入

5、类排序,10.2.1 直接插入排序 1. 基本思想 将一个记录插入到已经排好序的有序表中，从而得到一个新的记录数增加1的有序表。 一般情况下，第i趟直接插入排序的操作为：在含有i-1个记录的有序子序列R1.i-1中插入一个记录Ri，变成含有i 个记录的有序子序列R1i。,10.2.1 直接插入排序,10.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

6、; ,10.2.1 直接插入排序,3.算法分析 直接插入排序的算法简洁，容易实现。 从时间看，排序的基本操作为：比较两个记录的大小和移动记录。其中：（1）最小比较次数：Cmin = n-1 = O(n)（2）最大比较次数：Cmax =(2+3+n)= (n+2)(n-1)/2 = O(n2 )（3）最小移动次数：Mmin = 0 （4）最大移动次数：Mmax = (3+n+n+1) = O(n2) 故：该算法适应于待排序记录的数量n很小的情况。 从空间看，直接插入排序只需一个辅助空间。,10.2.1 直接插入排序,4.改进算法 在直接插入排序的基础上，从减少“比较”和“移动”这两种操作的次数着

7、手，可得到一些改进的插入排序算法，如： 折半插入排序：可以减少关键字之间的比较次数，但移动次数不变，故时间复杂度仍为O（n2）。其基本思想是利用折半查找来找要插入的位置。 Shell排序：可以减少比较和移动次数。,10.2.3 希尔排序,Shell排序，又称“缩小增量排序”，它也属于插入类排序，它是对直接插入排序的一种改进算法。在时间效率上比直接插入排序有较大的提高。 从对直接插入排序的分析可知，其最好的情况下时间复杂度是O（n），最坏的情况下时间复杂度为O(n2), 但是当待排序的记录已经处于“基本有序”状态时或当n值较小时，直接插入排序的效率均可大大提高。 Shell 排序方法正是基于这两

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

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

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

11、第一次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,10.3 交换类排序,结果：经过第一趟排序，得到最大值为90，放入最 后一个位置。,10.3 交换类排序,整个排序排序过程如下：,65 78 43 21 90 17,65 43 21 78 17 9

12、0,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; /*相邻记录交换位置*/ flag=1; /*

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

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

15、w=high为止。,10.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次交换后,完成一趟快 速排序,10.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 38 49

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

17、 if(lowhigh) mid=Partition(R,low,high); QuickSort(R,low,mid-1); QuickSort (R,mid+1,high); ,10.3 交换类排序,3.性能分析 快速排序的平均时间复杂度是O(nlogn),它是目前基于比较的内部排序方法中速度最快的一种，快速排序也因此而得名。 但是，若初始的关键字序列已经“基本有序”时，快速排序将退化为冒泡排序，其时间复杂度为O（n2）。 快速排序过程中需要一个栈空间来实现递归，因此空间复杂度不如前几种排序方法。,10.3 交换类排序,练习题：已知待排序的关键字序列是： 67，25，82，11，24，6，

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

19、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; ,10.4.1 简单选择排序,10.4.1 简单选择排序,3.性能分析 最好的情况下：记录移动的次数为0；最坏的情况下，记录移动的次数为 3(n-1)

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

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

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

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

24、左右子树均为堆从上到下逐层调整,10.5 归并类排序,所谓“归并”是指：将两个有序的序列合并为一个新的有序序列。 1.基本思想 将待排序序列看成为n个长度为1 的有序子序列，把这些子序列两两进行归并，便得到n/2 个长度为2的有序子序列，然后再两两归并，, 如此重复，直到最后得到一个长度为n的有序序列为止，这种方法成为二路归并方法。,10.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 9

25、7 13 27 49/ 76,13 27 38 49 49/ 65 76 97,初始无序序列,第一趟归并之后,第二趟归并之后,第三趟归并之后,10.5 归并类排序,2.性能分析 对n个记录的序列进行2-路归并排序时，必须进行 log2n 趟归并，而每趟归并所需的时间是O(n), 所以二路归并排序算法时间复杂度为O(nlog2n)。 与快速排序相比，归并排序的最大优点是，它是一种稳定的排序方法，但在一般情况下，很少利用2-路归并排序进行内部排序。,前介绍的排序方法都是根据关键字值的大小来进行排序的。本节介绍的方法是按组成关键字的各个位的值来实现排序，这种方法称为基数排序（radix sort）。采用基数排序法需要使用一批桶（或箱子），故这种方法又称为桶排序或箱排序。下面以十进制数为例来说明基数排序的过程。 假定待排序文件中所有记录的关键字为不超过d位的非负整数，从最高位到最低位（个位）的编号依次为1，2，d。设置10个队列（即上面所说的桶），它们的编号分别为0，