数据结构chapter 9 排序.ppt

1、第十章 排序,将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列；排序的根本目的是提高查找的速度,23-Jul-20,2,有序表和无序表队查找性能,在研究查找算法时我们发现： 对于顺序表，如果表中的元素没有顺序，那么平均查找长度为表长度的一半； 而当表中的元素有顺序时，可以采用效率很高的折半查找方法，大大提高查找效率。 构造二叉排序树或二叉平衡树的过实质上就是一个排序过程,23-Jul-20,3,排序的定义,假设含有n个记录的序列为R1,R2,Rn 各个纪录对应的关键字为K1,K2,Kn 排序就是要需要确定1,2,n的一种排列P1,P2,.,Pn 它使得其相应的关键字满足下列

2、非递减（或是非递增）的关系:,23-Jul-20,4,从而使下面的序列成为一个关键字有序的序列：,在排序过程中，如果关键字Ki是记录Ri的主关键字，则任何一个记录的无序序列经过排序后得到的结果是唯一的。 如果关键字Ki是记录Ri的次关键字，则排序结果很可能不是唯一的。,排序结果,23-Jul-20,5,排序方法的稳定性,假定排序前序列中有两个记录Ri 与Rj ， （ij），排序前Ri 在Rj的前面，且它们的关键字相同，即Ki =Kj . 如果排序后Ri仍然在Rj的前面，那么称所使用的排序方法是稳定的；反之则称所用的排序方法是不稳定的。,23-Jul-20,6,内部排序与外部排序,按待排序记录所

3、在位置（排序过程中涉及的存储器不同）可以将排序方法分为内部排序和外部排序 内部排序：待排序记录存放在内存 外部排序：排序过程中需对外存进行访问的排序,23-Jul-20,7,内部排序策略,根据策略不同，内排序可分为： 插入排序：直接插入排序、折半插入排序、希尔排序 交换排序：冒泡排序、快速排序 选择排序：简单选择排序、堆排序 归并排序：2-路归并排序 按照排序算法的时间复杂度可以分为 简单排序，时间复杂度为O(n2) 先进排序，时间复杂度为O(nlogn) 基数排序，时间复杂度为O(dn) 每一种不同的方法各有自己的优缺点和不同的应用范围和适用环境,23-Jul-20,8,排序的两项基本操作,

4、通常情况下排序过程中需要进行两项基本操作 （1）比较关键字的大小 （2）将记录从一个位置移动到另一个位置。 第一种操作通常是必须的，第二种操作通常可以通过改变数据元素的存储结构来避免移动元素。,23-Jul-20,9,待排序记录的三种不同的存储方式,将待排序的记录保存在一组地址连续的存储单元上。在排序过程中需要移动元素 将待排序的记录保存在静态链表中。排序过程中不需移动元素，只需要修改指针。 将待排序的元素放置在一组地址连续的存储单元上，同时另外设置一个指示各个记录位置的地址向量，排序结束后再根据地址向量调整元素的位置。这种方法可以减少第一种存储结构所需要移动记录的次数。,23-Jul-20,

5、10,本章约定的待排序元素的存储方式,本章假设待排序的数据元素保存在一个地址空间连续的存储单元中。C语言描述如下： #define MAXSIZE 20 typedef int KeyType; typedef struct KeyType key; InfoType otherinfo; RedType; typedef struct RedType rMAXSIZE+1; /空余一个单元 int length; SqList;,23-Jul-20,11,常见的排序方法：插入排序,基本思想：先将记录插入到一个已经排好序的有序表中，从而得到一个新的排好序的、记录数增加1的有序表 初始的时候可以

6、将序列中第1个记录看成是一个有序子序列，然后从第2个记录开始，每次将一个待排序记录，按其关键字的大小插入到前面已经排好序的文件的适当位置，直至全部记录插完为止。,23-Jul-20,12,1、直接插入排序,直接插入排序是最简单的排序方法 在已排好序的序列中进行查找(顺序查找)确定所应插入的位置，然后进行插入。 程序设计中的小技巧：在R0位置上的保存待插记录的副本，称为“监视哨” 监视哨的作用：自动控制循环的结束 直接插入排序过程中有两个基本操作： 比较关键字 移动记录,23-Jul-20,13,例：设输入记录的关键字序列为49，38，65，97，76，13，27，49，其直接插入排序过程（关键

7、字非递减的有序序列）：,直接插入排序过程示例,23-Jul-20,14,对顺序表L作直接插入排序算法,void InsertSort(SqList ,23-Jul-20,15,直接插入排序插入示例,23-Jul-20,16,直接插入排序算法分析,直接插入排序的算法简洁，容易实现 只需要一个记录的辅助空间 最坏情况下比较的次数为(n+2)(n-1)/2，所以这种方法移动元素的次数与元素个数n的平方成正比 关键字相同的两个对象，在整个排序过程中，不会通过比较而相互交换。因此直接插入排序是稳定排序,23-Jul-20,17,折半插入排序,基本思想：在直接插入排序过程中，对于每个元素需要在排好序的序列

8、中寻找插入位置。 由于查找是在一个有序序列中进行的，因此可以用折半查找来提高查找的速度 但这种方法只能减少查找插入位置所需要的时间，不能减少元素移动的次数,23-Jul-20,18,折半插入C描述,void BInsertSort(SqList ,23-Jul-20,19,2-路插入排序,2-路插入排序是在折半查找基础上的进一步改进，它可以减少元素移动的次数，但是需要增加n个记录的辅助空间d 基本过程： 首先令d1=L.r1 对于后面的每个元素，首先与d1的值比较，如果比d1的值小则插入到d1前面有序表中，否则插入到d1后面有序表中 在插入过程可以采用折半查找来确定插入的位置 需要将辅助空间看

9、成是一个循环空间，并设两个指针first和final来记录得到的有序序列在d中的位置 由于这种方法将一个有序表当作两个有序表来处理，因此称为2-路排序,23-Jul-20,20,2-路排序示例,初始序列,辅助空间状态,i=2,i=3,23-Jul-20,21,表插入排序,无论是直接插入排序、折半排序还是2-路排序均需要移动元素 要想在排序过程中不移动元素，需要改变数据的存储结构（比如用链表结构），通过修改指针来实现 表插入排序就是通过修改节点中的指针域来实现排序而不需要移动元素的 节点结构C描述： typedef struct RcdType rc; int next; SLNode;,typ

10、edef struct SLNode rSIZE; int length; SLinkListType;,23-Jul-20,22,表插入排序基本过程,首先设数组下标为0的分量为表头节点，将头节点的关键字设定为最大的整数值MAXINT 将下标为1的数组分量与表节点构成一个循环链表 依次将2到n的分量按照非递减顺序插入循环链表中 表插入排序得到的只是一个有序链表，通常需要根据排序的结果对原来的记录进行重新排列,23-Jul-20,23,表插入排序示例,初始序列,i=2,i=3,i=4,23-Jul-20,24,重新排列算法,表插入排序方法结束后，各个节点的next指针域给出了下一个元素的位置，它

11、们形成一个有序链表 如果希望表中的元素按照非递减顺序顺序保存到数组中去，则需要进行重新排列 重新排列的基本方法：顺序扫描有序链表，将链表中的第i个节点移动到数组的第i个分量中去。 当然这隐含要求前面i-1个元素已经按照顺序移动到了自己应有的位置上,23-Jul-20,25,重排列算法C描述,void Arrage(SLinkListType /下一个记录的位置 ,23-Jul-20,26,表插入排序重排列示例,初始序列,p=6 i=1,p=7 i=2,p=2 i=3,q=7,q=2,p=7 q=1,p=1 i=4,p=6 q=8,23-Jul-20,27,希尔排序,也叫缩小增量排序，虽然也是一

12、种插入排序，但是效率比以前几种排序方法有较大的改进 对于普通的直接排序，如果序列本身就是正序，那么复杂度只有O(n) 比如：12，23，34，45 因此，如果待排记录已经“基本有序”，即序列中具有下列特性的记录较少时，直接排序的效率可以大大提高。,基本思想：将整个待排序列分为几个短的子序列分别进行直接插入排序，待整个序列基本有序后再对全体记录进行一次直接排序,23-Jul-20,28,希尔排序示例,初始序列,13,27,49,55,04,49,38,65,97,76,第一趟排序 增量为5,13,04,49,38,27,49,55,65,97,76,第二趟排序 增量为3,第三趟排序 增量为1,2

13、3-Jul-20,29,希尔排序算法C描述,void ShellInsert(SqList ,23-Jul-20,30,二 快速排序,基于记录交换实现排序的方法 交换排序的基本思想：两两比较待排序记录的关键字，若其次序相反，则进行交换直至没有逆序的记录为止。 最简单的基于交换进行排序的方法是冒泡排序法。,23-Jul-20,31,起泡排序的基本过程,首先将第一个记录与第二个记录比较，如果为逆序则交换它们 然后进行第二个记录和第三个记录的比较，直到第n-1个元素和第n个元素比较完毕，这样就完成了一趟比较。 通过这趟比较可以将n个元素中的最大值交换到最后位置上。 接下进行第2趟起泡排序，对前面n-

14、1个元素重复上面的过程，结果使关键字次大的记录被安置在第n-1个记录位置 重复上述过程，直到“在一趟排序过程中没有进行过交换记录的操作”为止,23-Jul-20,32,起泡排序法示例,例：输入关键字序列为49，38，65，97，76，13用冒泡排序方法进行排序。,第一趟比较结束,第二趟比较只对前面 n-1个元素进行比较,结束条件：在一趟比较中 没有元素交换,23-Jul-20,33,2 快速排序法,快速排序是对冒泡排序方法改进，其基本思想为：通过一趟排序将待排序的记录分割为两个独立部分，其中一部分的关键字均比另一部分记录的关键字小，然后分别对这两个序列进行排序，以达到整个序列有序。 设待排序序

15、列为L.rs,L.rs+1,.,L.rt,首先任意选取一个记录（比如L.rs）作为支点，然后按下面原则重新安排其记录： 所有关键字小于它的记录均安排在它之前，所有关键字大于它的记录均安排在它之后 以支点记录所在位置i为界线，将序列分割成两个序列L.rs,L.rs+1,.,L.ri-1,和 L.ri+1,L.ri+2,.,L.rt,23-Jul-20,34,快速排序法的具体操作,附设两个指针low，high分别指向待排序记录的最上下界。 设定一个支点值pivotkey。 首先从high所指的位置向low方向搜索，找到第一个小于pivotkey的值，然后和low所指向的值交换， 然后从low开始向

16、high方向搜索，找到第一个大于pivotkey的值，并和high指向的值交换。 这个过程一直进行下去，直到low=high则这一趟排序结束。,23-Jul-20,35,一趟快速排序法的算法描述,int partition(SqList return low ,23-Jul-20,36,快速排序法的改进,快速排序方法的缺点：交换两个元素需要完成三次记录移动操作。 比如：AB需要三次赋值操作来实现 C = A A = B B = C 可以对上述算法进行改进，用一个单元来存储pivotkey的值，排序过程只作rlow或rhigh的单向移动，当一趟排序结束后才将pivotkey的值放置到合适的位置。

17、,23-Jul-20,37,改进的一趟快速排序法的算法描述,int partition(SqList ,23-Jul-20,38,快速排序法示例,例：设输入序列为49,38, 65,97,76,13,27,49,其快速排序过程为：,pivotkey=49,23-Jul-20,39,递归形式的快速算法,void QSort(SqList ,23-Jul-20,40,快速排序C程序演示,演示如何用C程序实现快速算法 example81.c,23-Jul-20,41,快速排序算法性能分析,假设T(n)为对n个记录进行快速排序所需要的时间，由递归算法知道： 其中Tpass(n)是一趟快速排序所需要的时

18、间，由于它和记录数目有关，可以记为cn. 一趟排序将一个序列一分为二，假定前面一个序列中有k-1个元素，后面一个中有 n-k个,结论：就平均时间而言，快速排序被认为是最好的内部排序方法,23-Jul-20,42,三 选择排序,基本思想： 假定有n个记录，第一趟排序可以从n个元素中选出一个最小值；第二趟排序可以再从剩下的n-1个元素中选出一个最小值；一般地，第i趟排序的功能是从n-i+1个记录中选择一个最小的值作为第i个记录，整个排序需要做n-1趟排序。 选择排序也有很多种不同的方法，如： 简单选择排序 树形选择排序 堆排序等,23-Jul-20,43,简单选择排序,基本思路：对于n-i+1个记

19、录，通过n-i次比较选出关键字最小的记录，并和第i个位置上的记录交换。 排序过程： 首先在所有记录中选出关键字最小的记录，将它与第一个位置上的记录交换 然后在其余记录中再选出关键字次小的记录与第2个记录交换 依次类推，直至所有记录排成递增序列为止,23-Jul-20,44,简单选择排序C描述,void SelectSort(SqList /在L.ri.length中选出最小的关键字 if (i !=j) L.ri L.rj ,23-Jul-20,45,简单选择排序示例,23-Jul-20,46,对简单排序的改进,在简单排序算法中，得到第一个元素需要比较 n 次，第二个元素需要比较n-1 次，依

20、次类推 但在实际应用中，第一趟比较的某些结果可以在第二趟比较中使用，从而减少第二趟比较所需要的次数。 比如：ab，bc，则ac。这样前两次比较的结果可以用于判断第三次比较的结果。也就是说：可以充分利用前面比较的结果来减少比较的次数，这就导出了树形选择排序。,23-Jul-20,47,树形选择排序法,又称为锦标赛排序 排序过程： 首先对关键字进行两两比较，然后在其中n/2个较小者之间再进行两两比较，直到选出最小关键字的记录为止 选出最小关键字之后，将对应叶节点的关键字设定为最大，再次进行比较选择次小关键字。再这个过程中，很多前次比较的结果可以直接使用，而不需要进行比较 该过程可以用一棵有n个叶子

21、节点的完全二叉树表示。,23-Jul-20,48,选择排序思想示例,以赵钱孙李周武郑王进行比赛选出冠军亚军和第三名的过程简单描述选择排序的思想。,选拔冠军比赛程序,23-Jul-20,49,选拔亚军需要两场比赛,23-Jul-20,50,树形选择排序示例,46，55，13，42，94，17，05，70 求最小关键字和次小关键字 最小关键字选择过程,23-Jul-20,51,求次小关键字过程,23-Jul-20,52,树形选择排序性能分析,含有n个节点的完全二叉树的深度为ceil(log2n)+1 因此除最小关键字外，每选择一个次小关键字仅需要进行ceil(log2n)次比较。 缺点：需要很多的

22、辅助空间来存储非终端节点,23-Jul-20,53,堆排序,堆排序是在树形排序基础上提出的，它只需要一个记录大小的辅助空间 堆的定义如下：,23-Jul-20,54,用完全二叉树来表示堆,我们知道完全二叉树中节点的序号存在下列关系 若将此序列看成是一个完全二叉树，则堆的含义意味着二叉树中所有非终端节点的值均不大于（或不小于）其左右子节点的值 因此，如果序列是堆，那么堆顶的元素必然是n个元素的最小值（或最大值）,23-Jul-20,55,堆示例,序列96,83,27,38,11,09的堆 序列12,36,24,85,47,30,53,91的堆 注意：形态不唯一，与输入顺序与构造算法有关 问题：

23、如何由一个无序序列构造一个堆？ 输出堆顶元素后如何调整使之成为一个堆？,23-Jul-20,56,堆调整算法,在输出堆顶元素之后，将堆中最后一个元素置于堆顶位置 由于此时左右子树均为堆，因此只需要从上至下调整 首先是堆顶元素和左右子节点中的最小值互换 元素互换会影响相应子树的堆，于是需要继续进行调整，直到叶子节点 自顶至叶子的调整过程称为“筛选”,23-Jul-20,57,“筛选”过程示例,23-Jul-20,58,由无序序列到堆,从一个无序序列创建堆的过程就是一个由下至上反复“筛选”的过程 如果一个序列有n个记录，那么最后一个非终端节点的编号应该为n/2，因此应从这个元素开始筛选 筛选完n/

24、2节点后，应该筛选它前面的元素，直到根节点 筛选完根节点后，由于可能要交换元素的值，因此需要继续调整交换了值的子树，直到叶子节点,23-Jul-20,59,由无序序列创建堆的过程示例,假定输入序列为49,38,65,97,76,13,27,49,给出创建堆的过程 首先根据输入序列创建完全二叉树 接下来从第4个元素开始反复调整,49,38,65,97,76,13,27,49,49,38,65,49,76,13,27,97,49,97,13,65,49,38,13,49,76,65,27,97,13,49,38,27,49,23-Jul-20,60,“筛选”过程C描述,typedef SqList

25、 HeapType; void HeapAdjust(HeapType ,s,j,j+1,23-Jul-20,61,堆排序C描述,void HeapSort(HeapTpe /输出堆顶元素 ,23-Jul-20,62,4 归并排序,基本思想:是将两个或两个以上的有序表合并为一个有序表。 排序过程 设初始序列含有n个记录，则可看成n个有序的子序列，每个子序列长度为1 两两合并，得到n/2个长度为2或1的有序子序列 再两两合并，如此重复，直至得到一个长度为n的有序序列为止,23-Jul-20,63,归并排序示例,例：关键字序列为49，38，65，97，76，13，27，归并排序过程：,初始序列,一

26、趟归并,二趟归并,三趟归并,23-Jul-20,64,归并算法C描述,void Merge(RcdType SR, RcdType ,SR,TR,23-Jul-20,65,归并排序递归算法C描述,void MSort(RcdType SR, RcdType ,23-Jul-20,66,5 基数排序,前面所述的各种排序方法实现主要通过关键字间的比较和移动记录操作。 基数排序是与前面所述各种排序方法完全不同的一种排序方法 基数排序：不需要移动关键字，也不需要进行关键字的比较，它是借助于多关键字排序思想对单逻辑关键字进行排序的方法。,23-Jul-20,67,52张扑克牌的次序关系为： 23A 23

27、A 23A 23A 每个牌有两个关键字： 花色（ ） 面值（23A） 并且“花色”地位高于“面值”,多关键字排序举例,23-Jul-20,68,两种不同的扑克牌排序方法,方法一 先将扑克牌按不同花色分为有次序的4堆，每一堆均有相同的花色； 然后分别对每一堆按“面值”大小整理有序 方法二： 先按“面值”分为13堆，然后将13张牌自小到大叠在一起， 再将整付牌按花色分为4堆，最后将4堆牌按花色大小次序合在一起。 这两种整理扑克牌的方法就是多关键字排序方法,23-Jul-20,69,多关键字的排序,假设有n个记录的序列为：R1,R2,Rn，且每个记录Ri含有d个关键字Ki0,Ki1,Ki2,Kid-

28、1,序列对关键字K0,K1,K2,Kd-1,有序是指：对序列中任意两个记录Ri和Rj(1ijn) 都满足下列有序关系：,其中K0是主关键字， K1是次关键字，Kd-1是最次关键字,23-Jul-20,70,多关键字排序的方法,为实现多关键字排序，通常有两种方法： 最高位优先法 MSD (Most Significant Digit first) 最低位优先法 LSD (Least Significant Digit first) 需要说明的是：这两种方法只是约定了按什么样的“关键字次序”进行排序，未规定对每个关键字排序时所用的方法。,23-Jul-20,71,多关键字排序的最高位优先法,先对主

29、关键字K0进行排序，即将序列分为若干子序列，每个子序列的记录都有相同的K0 每个子序列再按关键字K1进行排序，分成若干更小的子序列，依次重复 最后按Kd-1进行排序，将所有子序列依次联接在一起成为一个有序序列 比如：扑克牌先按“花色”排序，然后对每种花色按照“面值”排序 按花色排序后得到四个子序列，四个子序列再按面值进行排序,23-Jul-20,72,多关键字排序的最低位优先法,先对最次位关键字Kd-1进行排序 再对高一位的关键字Kd-2进行排序，依次重复 最后按K0进行排序，便成为一个有序序列 比如：扑克牌先按“面值”排序，然后对每种花色按照“花色”排序 在按面值排序的之后仍然是一个序列,比

30、如：2 2 2 23 3 3 3 然后再对整个序列按花色排序，且在按花色排序的时候必须是稳定排序 即排序后的结果应该为： 2 3 2 3 2 3 2 3 因为在按面值排序后2 在3前面，在按照花色进行排序时，尽管2 3的花色是相同的，排序后2 也必须在3前面，这样才是稳定排序,23-Jul-20,73,高位优先法与低位优先法的区别,高位优先法需要按照关键字将输入序列分为子序列，而低位优先法不必分成子序列，对每个关键字都是整列参与排序。 低位优先法要求对Ki（0id-2)排序序时只能用稳定的排序方法。,23-Jul-20,74,基数排序的基本思想,基数排序把一个关键字ki看成一个d元组Ki0,K

31、i1,Ki2,Kid-1,其中：0Kijr, i=1,2,n, j=1,2,d r 称为基数，d表示关键字的位数。d值取所有待排序关键字位数的最大值，其他不足d位的在前面补0。 比如关键字在0到999之间，则可以将关键字看成是由3位十进制数构成的，即：个位、十位和百位。 于是d=3,r=10,23-Jul-20,75,基数排序过程,基数排序是通过多个“分配”和“收集” 过程来实现排序的。 以最低有效位优先为例，其基本思路为： 设立r个队列，首先按最低有效位的值把n个关键字分配到r个队列中 然后根据最低有效位从小到大将队列中的关键字收集起来 再按次低有效位把收集起来的关键字再分配到r个队列中，然后重复上述的收集工作 如此重复进行分配和收集，直到最高有效位，得到一个从小到大有序的关键字序列。,23-Jul-20,76,基数排序法示例（1）,278,109,063,930,589,184,505,269,008,083,分配过程：,关键字序列278，109，063，930，589，184，505，269，008，083，用最低位优先基数排序方法进行排序。,收集过程：930，063，083，184，505，278，008，109，589，269,23-Jul-20,77,基数排序法示例（2）,278,109