《《数据结构（C语言描述）》-斯庆巴拉-电子教案 第9章典型排序算法》由会员分享，可在线阅读，更多相关《《数据结构（C语言描述）》-斯庆巴拉-电子教案 第9章典型排序算法（39页珍藏版）》请在金锄头文库上搜索。
1、第9章 典型排序算法,排序的定义和各种排序方法的特点，排序方法“稳定”或“不稳定”的含义 各种排序方法的原理、排序过程、时间复杂度的分析和实现算法 内排序和外排序的区别及适用情况 希尔排序、快速排序、堆排序和归并排序等高效方法是本章学习的重点和难点,第9章 典型排序算法,9.1 实例：统计学生成绩表 9.2 插入排序 9.3 选择排序 9.4 交换排序 9.5 归并排序和基数排序 9.6 比较各种内排序方法 9.7 外排序 本章总结,9.1 实例：统计学生成绩表,9.1.1 问题描述 9.1.2 问题分析 9.1.3 实现算法 9.1.4 排序定义及相关概念,9.1.1 问题描述,某校学生报考
2、英语四级考试，要求成绩下发后进行各专业成绩统计，此时可以按照考试成绩进行排序，也可以按照学号进行排序。,9.1.2 问题分析,如何将原始成绩表变成有序表呢？ 最常用的方法就是通过互相比较来完成排序。 实现过程：假设有一张登记n个学生英语四级考试成绩的表，则先从这n个人中找出学号最小的学生记录，把它排在第一位，然后对剩下的n-1个学生记录，还重复上述操作，即找出最小的，把它放在最前面。重复此过程n-1次，表中n个学生的记录就会按学号的从小到大的排列顺序有序。,9.1.3 实现算法,成绩表中学生记录的类型定义为:(略) 成绩表在内存中以顺序表的形式存储，则数据类型定义为： (略) 实现算法： (略
3、),9.1.4 排序定义及相关概念,排序就是把一组记录按照某个关键字（或称排序码）的值的递增或递减顺序重新排列的过程。在表中的先后次序进行排序后，记录的相对次序仍然不变，则称此排序方法是稳定的，否则称此排序方法不稳定。 排序分类： 内排序记录量不大，可以在内存中完成整个排序过程的排序方法。 外排序记录量大，需要将一部分记录放置在内存，另一部分记录放置在外存上，排序过程中需要在内外存之间多次交换数据才能得到排序结果的排序方法称为。 内排序分为插入排序、交换排序、选择排序、归并排序和基数排序等五类。,struct Rtype/排序记录 KeyType key; /关键字域 ; # define m
4、axlen maxsize/分配的存储单元个数 struct ListSq/顺序表 Rtype e maxlen ; /0号单元空闲 int len ; ,数据类型定义为：,9.2 插入排序,9.2.1 直接插入排序 9.2.2 折半插入排序 9.2.3 希尔排序,9.2.1 直接插入排序,基本思想： 每一趟将一个待排序的记录，按其关键字值的大小插入到已经排好序的有序表中，直到无序表中的所有记录全部插入到有序表中为止。 排序过程：把线性表中的n个元素看成是一个有序表和一个无序表。开始时，有序表中只有一个元素L.stu0，无序表为其余的n-1个元素。依次从无序表中取出一个元素，把它插入到有序表的
5、合适位置，使之成为一个新的有序表，这称一趟排序过程。经过n-1趟排序后，无序表中的n-1个元素全部插入到有序表中，无序表变成一个空表，排序过程结束。,直接插入排序的实现算法：（略） 时间复杂度： 最好情况是原始记录已按关键字递增有序排列，整个排序过程的比较次数为n-1次，时间复杂度为O(n) 。 最坏情况是原始记录按关键字递减有序排列，整个排序过程的比较次数为 (n+2)(n-1)/2，记录移动的次数为 (n+4)(n-1)/2，时间复杂度是O(n2) 。 平均情况下，时间复杂度是O(n2)。 直接插入排序是一种稳定的排序方法。,9.2.2 折半插入排序,基本思想： 在有序表中进行查找时，将查
6、找合适位置的过程用折半查找来实现。 折半插入排序的实现算法：（略） 时间复杂度：折半插入排序减少了记录关键字之间的比较次数，而未改变记录的移动次数。折半插入排序的时间复杂度为O(n2)。,9.2.3 希尔排序,基本思想： 把记录按一定增量分组，对每组记录使用插入排序，接着减小增量，随着增量的减小，每个分组中包含的记录也越来越多，到增量的值减小到1时，整个数据合并为一组，成为一个有序序列，排序过程结束。 折半插入排序的实现算法：（略） 时间复杂度： 时间复杂度为O(nlog2n)，是一种不稳定的排序方法。,9.3 选择排序,9.3.1 直接选择排序 9.3.2 堆排序 选择排序基本思想：每一趟在
7、n-i+1(i=1,2,n-1)个记录中选取关键字值最小的记录作为有序序列中第i个记录。,9.3.1 直接选择排序,基本思想： 每一趟排序在n-i+1(i=1,2,n-1)个记录中选取关键字值最小的记录，并和第i(1in)个记录交换，共重复n-1次。 直接选择排序的实现算法：（略） 时间复杂度： 直接选择排序的时间复杂度为O( )，是一种不稳定的排序方法。,9.3.2 堆排序,堆的定义：n条记录的关键字序列为k1，k2，kn，当且仅当满足下列关系时，称之为堆： kik2i且kik2i+1 或 kik2i 且kik2i+1 (1i ) 结论：堆是一个所有非终端结点的值均不大于（或不小于）其左右孩
8、子结点值的完全二叉树。由此，堆顶元素（或完全二叉树的根）必为这n个元素中的最小值或（最大值）。堆顶元素为最小值的堆称为小根堆，堆顶元素为最大值的堆称为大根堆。（以小根椎为准） 堆排序基本思想：若输出堆顶元素之后，使得剩余的元素序列重又建成一个堆，则得到 其中的次小值。反复执行，便能得到一个有序序列。,堆排序需要解决的两个问题： 1 如何将一个无序序列建成一个堆? 2 在输出堆顶元素之后，如何将剩余元素调整为一个新的堆?,一个无序序列建成一个堆的过程： 是一个反复“筛运算”的过程。先将待排序序列按顺序构造成一棵完全二叉树，然后对完全二叉树中的所有非终端结点进行调整。按完全二叉树中结点的编号顺序来
9、讲，最后一个非终端结点是第 个元素，由此“筛运算”只需从第 个元素开始，一直调整到根结点。 调整原则：根据堆的定义，使得所的的双亲结点与它的孩子结点都满足堆定义，不满足时结点间进行交换。,将剩余元素调整为一个新堆的过程： 输出堆顶元素之后，以堆中最后一个元素来替代根结点。此时根结点的左、右子树均为堆，则仅需自上至下进行调整即可。 首先将堆顶元素与其左、右子树根结点的值进行比较，若不满足堆的定义，进行结点间的交换，继续往下调整，直到叶子结点 。,堆排序的实现算法：（略） 时间复杂度： 每次筛运算的时间复杂度为O(log2n)，整个堆排序的时间复杂度为O(n )，是一种不稳定的排序方法。,9.4
10、交换排序,9.4.1 冒泡排序 9.4.2 快速排序,9.4.1 冒泡排序,基本思想：通过对无序区中相邻记录的关键字间的比较和位置的交换，使关键字最小的记录像气泡一样逐渐上浮直至“水面”。 具体过程：首先将第一条记录的关键字和第二条记录的关键字进行比较，若为逆序，则将两个记录交换，然后比较第二条记录和第三条记录的关键字，逆序时交换。依次类推，直至第n-1条记录和第n条记录的关键字比较完为止。上述过程称作第一趟起泡排序，其结果使得关键字最大的记录被安置到最后一条记录的位置上。重复此过程，直到全部有序为止。整个过程中，关键字越大的记录越下沉到底，同时使关键字小的记录相对上浮。,冒泡排序的实现算法：
11、（略） 在排序过程中，如果某一趟排序中不存在相邻元素的交换，意味着待排序序列已有序，无需进行下一趟排序。所以，在算法中设置了一个标志flag，初值为1，每一趟排序开始时，都将标志flag的值设置为0，只有在比较过程中存在元素交换时，才把标志flag的值设为1。 时间复杂度： 时间复杂度为O( n2 )，是一个稳定的排序方法。,9.4.2 快速排序,基本思想：通过一趟排序将待排序记录分割成独立的两个区间，其中左区间中记录的关键字的值均比右区间中记录的关键字的值小，再分别对这两个区间中的记录进行快速排序，以达到整个序列有序为止。 排序过程：在待排序的n条记录中任取一条记录（通常取第一条记录）作为基
12、准元素，确定该条记录的最终位置，将待排序序列以基准元素为界限分割成两个区间，这个过程称作一趟快速排序。之后对所有的区间分别重复上述过程，直至每个区间内只有一条记录为止。 结论：快速排序是一个递归过程，整个排序过程中对不同的区间进行快速排序。,快速排序的实现算法：（略） 时间复杂度： 快速排序的时间复杂度为O(nlogn)，是一种不稳定的排序方法。,9.5 归并排序和基数排序,9.5.1 归并排序 9.5.2 基数排序,9.5.1 归并排序,基本思想：将两个或两个以上的有序数据序列合并成一个新的有序序列的过程。 排序过程：假设初始序列含有n个记录，则可看成是n个有序的子序列，每个子序列的长度为1
13、，然后两两归并，得到 个长度为2或1的有序子序列；再两两归并，如此重复，直到得到一个长度为n的有序序列为止，这种排序方法称为2-路归并排序。,二路归并排序的实现算法：（略） 时间复杂度： 二路归并排序的时间复杂度为o(n ) ，是一种稳定的排序方法。,9.5.2 基数排序,基本思想：不需要对排序码进行比较，而是一种借助多关键字排序的思想来实现单个关键字排序的方法，是一种重复的分配和收集过程。 分类：第一种方法是先按高位关键字进行排序，称为“最高位优先”法，简称MSD法；第二种方法是先按低位关键字排序，被称之为“最低位优先”法，简称LSD。,9.6 比较各种内排序方法,各种内排序方法的比较 ：
14、从时间复杂度比较 直接插入排序、折半插入排序、直接选择排序和冒泡排序的时间复杂度为o(n2)，而快速排序、希尔排序、堆排序和归并排序的时间复杂度为o(nlog2n)。 从空间复杂度比较 归并排序空间复杂度最大，为o(n)，快速排序空间复杂度为o(log2n)，其他排序方法的空间复杂度均为o(1)。,从稳定性比较 直接插入排序、折半插入排序、冒泡排序、归并排序和基数排序是稳定的排序方法，而直接选择排序、堆排序、快速排序和希尔排序是不稳定的排序方法。 从算法的简单性比较 直接插入排序、折半插入排序、直接选择排序和冒泡排序都是简单排序方法，排序过程易于理解、实现算法也简单。而快速排序、希尔排序、堆排
15、序和归并排序等是前面几种简单排序的一种改进型排序方法，所以相对来讲，实现算法较复杂一些。,各种内排序方法的选择： 影响选择排序方法的因素 在选取合适的排序方法时需要考虑以下因素： (1) 待排序的元素数目n； (2) 记录本身信息量的大小； (3) 排序方法的稳定性； (4) 辅助空间的大小等。 在选取排序方法时，首先应考虑排序稳定性，其次考虑待排序记录数n的大小，从而选取适当的排序方法。,(1) 若n较小(n = 30)，则可以采用直接插入排序或直接选择排序。 (2) 若文件的初始状态已按关键字基本有序，则选用直接插入或冒泡排序为宜。 (3) 若n较大，应采用快速排序、堆排序或归并排序等。
16、(4) 在基于比较的排序方法中，每次比较两个关键字的大小之后，仅仅出现两种可能的转移，由此得：当n个关键字随机分布时，借助“比较“的排序算法，至少需要O(nlog2n)的时间。 (5) 当记录本身信息量较大时，可用链表作为存储结构。,选择排序方法的规则：,9.7 外排序,9.7.1 外排序的基本过程 9.7.2 多路归并排序 外排序是指大文件的排序，即待排序的记录存储在外存储器上，在排序过程中需要进行多次的内、外存之间的交换。,9.7.1 外排序的基本过程,外排序由相对独立的两个步骤组成： （1）按可用内存大小，利用内排序的方法，构造若干个(记录的)有序子序列，通常称外存的这些记录有序子序列为“归并段”; （2）通过“归并”，逐步扩大(记录的)有序子序列的长度，直至外存中整个记录序列按关键字有序为止。,外部排序所需总时间 = 内部排序（产生初始归并段）所需的时间 m*tis +外部信息读写的时间 d*tio +内部归并所需的时间 s*utmg 其中：
