内部排序讲课教案

《内部排序讲课教案》由会员分享，可在线阅读，更多相关《内部排序讲课教案（43页珍藏版）》请在金锄头文库上搜索。

1、数据结构第十章内部排序,本章内容 10.1 基本概念 10.2 插入排序 10.3 快速排序 10.4 选择排序 10.5 归并排序 10.6 基数排序,10-3,10.1 基本概念,关键字 是记录（数据元素）中的一个（或多个）字段。通常用作检索和排序记录的依据。 关键字通常可以进行比较操作。,10-4,10.1 基本概念,排序：设含有n个记录的文件R1,R2,.,Rn，其相应的关键字为K1,K2,.,Kn，将记录按关键字值非递减(或非递增)顺序排列的过程，称为排序。 排序的稳定性：对所有的Ki=Kj (ij)（具有相同关键字）,若排序前Ri领先于Rj,排序后Ri仍领先于Rj,则称该排序方法是

2、稳定的，反之，称为不稳定的。稳定性是对序列中的两个相同的关键字在初始序列和最终有序序列中相对位置（即领先关系）是否变化。 排序分类 内部排序：待排序文件的全部记录存放在内存进行的排序，称为内部排序。 外部排序：排序过程中需要进行内外存数据交换的排序，称为外部排序。,10-6,10.2 插入排序,10.2.1 直接插入排序 它是最简单的排序方法 基本思想：依次将每个待排序的记录插入到一个有序子文件的合适位置(有序子文件记录数增1) 例如：已有待排序文件为：45,34,78,12,34,32,29,64。首先将文件的第一个记录，视为有序文件，然后从第二个记录开始，直到最后一个记录，依次将他们插入到

3、有序文件的合适位置。,12,34,32,29,64,45,34,78,10-7,10.2 插入排序,算法分析 直接插入排序的算法简洁，容易实现。从时间来看，排序的基本操作为：比较两个记录的大小和移动记录。其中： 最小比较次数：Cmin = n-1 = O(n) 最大比较次数：Cmax =(2+3+n)=(n+2)(n-1)/2 = O(n2 ) 最小移动次数：Mmin = 0 最大移动次数：Mmax = (2+1 + 3+1 + + n+1) = O(n2) 若待排序记录序列中出现各种可能排列的概率相同，则可取上述最好情况和最坏情况的平均情况。在平均情况下的关键字比较次数和记录移动次数约为 n

4、2/4。因此，直接插入排序的时间复杂度为 o(n2)。,10-8,10.2 插入排序,结论 直接插入排序的效率与待排文件的关键字排列有关； 直接插入排序的时间复杂度为O(n2)； 直接插入排序是稳定的(这一点由过程中WHILE语句的条件“”保证的，只有小于才交换)。,10-9,10.2 插入排序,10.2.2 折半插入排序(Binary Insertsort) 由于是在有序子文件中确定插入的位置，因此可用折半查找来代替直接插入排序法中的顺序查找，从而可减少比较次数。 基本思想 设在顺序表中有一个记录序列 R1, R2, , Rn。其中，R1, R2, , Ri-1 是已经排好序的记录。 在插入

5、 Ri 时，利用折半搜索法寻找 Ri 的插入位置。,10-10,i=1 (30) 13 70 85 39 42 6 20,i=2 13 (13 30) 70 85 39 42 6 20,i=7 6 (6 13 30 39 42 70 85 ) 20,i=8 20 (6 13 30 39 42 70 85 ) 20,i=8 20 (6 13 20 30 39 42 70 85 ),10.2 插入排序,10.2 插入排序,10-11,算法评价 时间复杂度:T(n)=O(n),折半插入排序只能减少排序过程中关键字比较的时间,并不能减少记录移动的时间。 稳定的排序方法,10-12,10.2 插入排序,

6、10.2.3 Shell排序 基本思想：希尔排序（Shells Methool）又称为缩小增量排序，也是一种插入排序方法。它将待排序数据文件分割成若干个较小的子文件，对各个子文件分别进行直接插入排序，当文件达到基本有序时，再对整个文件进行一次直接插入排序。 适用条件 如果待排序文件基本有序，即文件中具有特性： ri.key Max rj .key 1jI 的记录数较少 ，则文件中大多数记录不需要进行插入， 因而排序效率可以提高，接近于O(n)。,10-13,10.2 插入排序,例1：设初始关键字为： 第一趟以步长为5分割为5个子文件： R1,R6 R2,R7 R3,R8 R4,R6 R5,R1

7、0 对每个子文件进行直接插入排序 第二趟以步长为3对第一趟排序结果分割为3 个子文件： R1,R4,R7,R10 R2,R5,R8 (R3,R6,R9 对每个子文件进行直接插入排序 第三趟以步长为1对第二趟排序结果进行直接插入排序,49 38 65 97 76 13 27 49 55 04,13 27 49 55 04 49 38 65 97 76,原始数据:,第一趟排序:,第二趟排序:,49 49 97,13 38 55 76,04 27 65,04 13 27 38 49 49 55 65 76 97,第三趟排序:,10-14,10.2 插入排序,例2：对下列数据进行shell排序，步长分

8、别选为4、2、1。,12,34,32,29,64,45,34,78,10-15,10.2 插入排序,增量的取法 最初 shell 提出取 d1 = n/2，d2 = d1/2，直到dt = 1。后来 knuth 提出取di+1 = di/3 +1。还有人提出都取奇数为好，也有人提出各增量互质为好。 算法分析 不稳定 空间代价：O(1) 增量每次除以2递减，时间代价：O(n2) 选择适当的增量序列，可以使得时间代价接近O(n) 增量每次除以2递减”时，效率仍然为O(n2) 问题：选取的增量之间并不互质 间距为2k-1的子序列都是由那些间距为2k的子序列组成的 上一轮循环中这些子序列都已经排过序了

9、，导致处理效率不高,10-16,10.3 交换排序,10.3.1 冒泡排序 冒泡排序是一种简单而且容易理解的排序方法，它和气泡从水中不断往上冒的情况有些类似。 其基本思想 对存放原始数据的数组，按从后往前的方向进行多次扫描，每次扫描称为一趟 (pass)。当发现相邻两个数据的次序与排序要求的“递增次序”不符合时，就互换两个数据。这样，较小的数据就会逐单元向前移动，好象气泡向上浮起一样。 示例,12,34,32,29,64,78,34,45,10-17,10.3 交换排序,算法评价 算法稳定 空间代价：O(1) 时间代价 ： 比较次数 ： 交换次数最多为O(n2)，最少为0，平均为O(n2)。

10、最大，平均时间代价均为O(n2)。 最小时间代价为O(n)：最佳情况下只运行第一轮循环,10-18,10.3 交换排序,10.3.2 快速排序 基本思想 任取某个记录作为基准（通常选文件的第一个记录），将所有关键字不大于它的记录放在它的前面，将所有关键字不小于它的记录放在它的后面； 这样遍历一趟文件后，将文件以该记录为界分为两部分； 然后对各部分重复上述过程，直到每一部分仅剩一个记录为止。 特点：基于分治法的排序：快速、归并。分治策略的实例 BST查找、插入、删除算法 快速排序、归并排序 二分检索 主要思想：划分、求解子问题(子问题不重叠)、综合解,10-19,10.3 交换排序,25 34

11、45 32 3412 29 64,29,32,64,25,34,最终排序结果：12 25 29 32 34 34 45 64,45,10-20,10.3 交换排序,快速排序算法评价 快速排序算法不稳定。 常用“三者取中”法来选取划分记录，即取首记录rs.key.尾记录rt.key和中间记录r(s+t)/2.key三者的中间值为划分记录。 算法分析 最差情况： 时间代价： O(n2) 空间代价： O(n) 最佳情况： 时间代价：O(nlog n) 空间代价：O(log n) 平均情况： 时间代价：O(nlog n) 空间代价：O(log n),10-21,10.4 选择排序,基本思想 每一趟 (

12、例如第 i 趟，i = 1, 2, , n-1) 在后面 n-i+1 个待排序记录中选出关键字最小的记录, 作为有序记录序列的第 i 个记录。待到第 n-1 趟作完，待排序记录只剩下1个，就不用再选了。,10-22,10.4 选择排序,10.4.1 简单选择排序 基本思想 首先在所有记录中选出关键字最小的记录，把它与第1个记录交换，然后在其余的记录中再选出关键字次最小的记录与第2个记录交换，以次类推，直到所有记录排序完成。,10-23,10.4 选择排序,初始关键字序列,34,12,49,28,31,52,51,49*,0,10-24,10.4 选择排序,算法分析 交换次数：正序时交换次数最少

13、，为0次，逆序时最多，为n-1次。 比较次数：与初始文件关键字排列无关，为n(n-1)/2次。 简单选择排序时间复杂度为O(n2)，并且是稳定的排序。,10-25,10.4 选择排序,10.4.2 堆排序 堆的定义 对于n个元素的序列k1,k2,.,kn，当且仅当满足以下关系时，称之为堆。,或,10-26,10.4 选择排序,若将堆视为一个完全二叉树，则堆的含义为：完全二叉树中所有非叶结点的值(ri) 均不大于(或不小于)其左孩子的值(r2i)、右孩子的值(r2i+1) 。 堆顶元素(完全二叉树的根)是序列中最小(或最大)的元素。,12,65,49,81,55,34,98,是堆,14,不,36

14、,40,73,27,10-27,10.4 选择排序,堆排序(Heap Sort)基本思想 以初始关键字序列，建立堆； 输出堆顶最小元素； 调整余下的元素，使其成为一个新堆； 重复2,3步，直到n个元素输出，得到 一个有序序列。 关键问题： 要解决1和3，即如何由一个无序序列建成一个堆? 如何调整余下的元素成为一个新堆?,10-28,10.4 选择排序,调整方法 将堆顶元素和堆的最后一个元素位置交换； 然后以当前堆顶元素和其左、右子树的根结点进行比较(此时，左、右子树均为堆)，并与值较小的结点进行交换； 重复第2步，继续调整被交换过的子树，直到叶结点或没进行交换为止。 称这个调整过程为筛选。,1

15、0-29,10.4 选择排序,例如：设有关键字13,38,27,49,76,65,49,97，按初始次序构成一棵完全二叉树，形成一个堆如下图：,10-30,10.4 选择排序,堆排序的时间复杂度分析 对深度为k的堆，“筛选”所需进行的关键字比较的次数至多为2(k-1); 对n个关键字，建成深度为h(=log2n+1)的堆，所需进行的关键字比较的次数至多为4n; 调整“堆顶”n-1次，总共进行的关键字比较的次数不超过2( log2(n-1) + log2(n-2)+ +log22)2n( log2n ) 因此，堆排序的时间复杂度为O(nlogn)，且不稳定。,10-31,10.5 归并排序,归并

16、 归并是指将若干个已排序好的有序表合并成一个有序表。两个有序表的归并称为二路归并。 归并排序 将待排序的n个记录，看作n个有序的子序列，每个子序列的长度为1。然后两两归并，得到n/2个长度为2或为1的子序列；再两两归并，.，如此重复，直到得到长度为n的子序列为止。这种排序的方法称为2_路归并排序。,10-32,10.5 归并排序,2_路归并排序的核心操作：将一维数组中前后两个有序序列归并为一个有序序列。 例： 将一维数组49,38,65,97,76,13,27,49进行2_路归并排序：,初始：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,10-33,10.5 归并排序,将两个有序序列归并为一个有序序列的算法,void merge (Sqlist SR,Sqlist ,10-34