数据结构ch09 排序.pptxVIP

第9章 排序提纲CONTENTS9.1 排序的基本概念9.5 归并排序9.6 基数排序9.2 插入排序9.7 各种内排序方法的比较和选择9.3 交换排序9.4 选择排序9.8 外排序9.1 排序的基本概念1. 什么是排序 所谓排序，就是要整理表中的元素，使之按关键字递增或递减有序排列，本章仅讨论递增排序的情况，在默认情况下所有的排序均指递增排序。排序的输入输出如下：输入：n个元素序列为R0、R1、…、Rn-1，其相应的关键字分别为k0、k1、…、kn-1。输出：Ri0，Ri1，…，Rin-1 ，使得ki0≤ki1≤…≤kin-1。2. 内排序和外排序在排序过程中，若整个表都是放在内存中处理，排序时不涉及数据的内、外存交换，则称之为内排序。反之，若排序过程中要进行数据的内、外存交换，则称之为外排序。3. 内排序的分类插入排序交换排序选择排序归并排序基于比较的排序内排序基数排序不基于比较的排序4. 基于比较的排序算法的性能基于比较的排序算法中，主要进行以下两种基本操作：比较：元素关键字之间的比较。移动：元素从一个位置移动到另一个位置。排序算法的性能由算法的时间和空间确定的，而时间又是由比较和移动的次数确定的。若待排序元素的关键字顺序正好和排序顺序相同，称此表中元素为正序。反之，若待排序元素的关键字顺序正好和排序顺序相反，称此表中元素为反序。基于比较的排序算法的下界n=3的决策树(R1,R2,R3)k1≤k2(R1,R2,R3)k2≤k3(R2,R1,R3)k1≤k3是是否否①④(R1,R3,R2)k1≤k3(R2,R3,R1)k2≤k3(R1,R2,R3)(R2,R1,R3)是是否否②③⑤⑥(R1,R3,R2)(R3,R1,R2)(R2,R3,R1)(R3,R2,R1)正序不变，逆序交换！ 3!=6个叶子结点(R1,R2,R3)k1≤k2(R1,R2,R3)k2≤k3(R2,R1,R3)k1≤k3是是否否①④(R1,R3,R2)k1≤k3(R2,R3,R1)k2≤k3(R1,R2,R3)(R2,R1,R3)是是否否②③⑤⑥(R1,R3,R2)(R3,R1,R2)推广为n个元素（假设关键字均不同）(R2,R3,R1)(R3,R2,R1)排序算法所用的比较次数等于决策树中最深的叶子结点的深度。所用的平均比较次数等于决策树中叶子结点的平均深度即树的高度。n个元素排序结果有n!种情况，对应的决策树是一棵有n!个叶子结点的二叉树。设其高度为h，其中没有单分支结点，总结点个数=2n!-1，其高度等同于含2n!-1个结点的完全二叉树的高度，则h=?log2(2n!)?= log2n!+1，而log2n!≈nlog2n，即h=O(nlog2n)。排序中移动次数与比较次数属于同数量级。n个元素采用基于比较的排序方法平均时间复杂度为O(nlog2n)，最坏情况下的时间下界也为O(nlog2n)。基于比较排序算法的平均时间复杂度不可能优于O(nlog2n)5. 排序的稳定性当待排序元素的关键字均不相同时，排序的结果是唯一的，否则排序的结果不一定唯一。如果待排序的表中，存在有多个关键字相同的元素，经过排序后这些具有相同关键字的元素之间的相对次序保持不变，则称这种排序方法是稳定的。反之，若具有相同关键字的元素之间的相对次序发生变化，则称这种排序方法是不稳定的。6. 排序数据的组织以顺序表作为排序表的存储结构（除基数排序采用单链表外）。假设关键字为int类型，待排序的顺序表直接采用Python列表R[0..n-1]表示。如10个整数关键字序列表示为：R=[1,6,2,5,3,7,4,8,2,4]（存在相同的关键字）。若待排序表中每个元素除整数关键字外还有其他数据项，可以采用嵌套列表表示。如3个学生元素，每个元素由学号和姓名组成，R表示为：R=[[1,Mary],[3,John],[2,Smith]]。9.2 插入排序基本思路有序区无序区一个一个地插入不是全局有序，全局有序区中的元素在后面排序中不再发生位置的改变主要的插入排序方法：（1）直接插入排序（2）折半插入排序（3）希尔排序一趟排序10.2.1 直接插入排序1. 排序思路有序区无序区 R[0]…… R[i-1] R[i] …… R[n-1] R[0]…… R[i-1] R[i]R[i+1] …… R[n-1]有序区无序区初始时，有序区只有一个元素R[0]i＝1~n-1，共经过n-1趟排序一趟直接插入排序：在有序区中插入R[i]的过程。有序区R[0..i-1]R[i]当R[i]R[i-1]时jj=i-1tmp插入位置 R[j]大时便后移R[j+1]=tmp使R[0..i]有序 ? 扩大有序区 【例9.1】 设待排序表有10个元素，其关键字序列为（9，8，7，6，5，4，3，2，1，0）。说明采用直