《数据结构——C语言描述 教学课件 ppt 作者 王国钧 主编 唐国民 苏晓萍 马瑜 副主编 电子教案 DS09-排序》由会员分享，可在线阅读，更多相关《数据结构——C语言描述 教学课件 ppt 作者 王国钧 主编 唐国民 苏晓萍 马瑜 副主编 电子教案 DS09-排序（88页珍藏版）》请在金锄头文库上搜索。
1、基本概念 插入排序 交换排序 选择排序 归并排序 基数排序 内部排序比较 外排序,第9章 排序,关键字(Key) 作为排序依据的数据对象中的属性域。不同的数据对象若关键字互不相同，则这种关键字称为主关键字。 排序 使一组任意排列的对象变成一组按关键字线性有序的对象。 排序算法的稳定性 判断标准：关键字相同的数据对象在排序过程中是否保持前后次序不变。,9.1 基本概念,排序方法的分类 按是否涉及数据的内、外存交换分类 外排序、内排序 按策略划分内部排序方法 插入排序、选择排序、交换排序、归并排序和基数排序。 排序算法性能评价 评价排序算法好坏的标准主要有两条：算法执行所需要的时间和所需要的附加空
2、间。 另外，算法本身的复杂程度也是需要考虑的一个因素。,不同存储方式的排序过程 以顺序表作为存储结构 对记录本身进行物理重排 以链表作为存储结构 无须移动记录，仅需修改指针。 用顺序的方式存储待排序的记录，但同 时建立一个辅助表 只需对辅助表的表目进行物理重排，适 用于难于在链表上实现，仍需避免排序 过程中移动记录的排序方法,为简单起见，数据的存储结构采用记录数 组形式，同时假定关键字是整数。记录数 组的类型说明如下： typedef int KeyType； typedef struct KeyType key； InfoType otherinfo； RecType； typedef Re
3、cType SeqListn+1；,9.2 插入排序,基本原理：每步将一个待排序的对象，按其关键字大小，插入到前面已经排好序的一组对象适当位置上，直到对象全部插入为止。,直接插入排序 希尔排序,直接插入排序,基本思想：当插入第i个对象时，前面的R1，R2，Ri-1已经排好序，此时，用Ri的关键字与Ri-1,，Ri-2，的关键字顺序进行比较，找到插入位置即将Ri插入，原来位置上对象向后顺移。,直接插入排序举例,i (0) (1) (2) (3) (4) (5) temp 21 25 49 25* 16 08 25 1 21 25 49 25* 16 08 49 2 21 25 49 25* 16
4、 08 25* 3 21 25 25* 49 16 08 16 4 16 21 25 25* 49 08 08 5 08 16 21 25 25* 49,直接插入排序算法 void lnsertSort(SeqList R) int i,j; for (i=2;in;i+) R0Ri; ji-1; while (R0.keyRj.key) Rj+1Rj- -; Rj+1R0; ,算法中引入附加记录R0有两个作用：其一是进入查找循环之前，它保存了Ri的副本，使得不至于因记录的后移而丢失Ri中的内容；其二是在while循环“监视”下标变量j是否越界，一旦越界（即j=1）。因此，我们把R0称为“监视
5、哨”。,直接插入排序的算法分析,直接插入排序算法由两重循环组成，对于有n个记录的排序，内循环表明完成一趟排序所需进行的记录关键字间的比较和记录的后移。 若初始时关键字递增有序，这是最好情况。每一趟排序中仅需进行一次关键字的比较，所以总的比较次数为n-1。在while循环之前和之中，至少要移动记录两次，所以总的比较次数为2(n-1)。 若初始时关键字递减有序，这是最坏情况。这时的记录比较和移动次数分别为：,直接插入排序的稳定性,直接插入排序是一种稳定的排序方法。 原理：关键字相同的两个对象，在整个排序过程中，不会通过比较而相互交换。,希尔排序,1959年由D.L. Shell提出，又称缩小增量排
6、序(Diminishing-increment sort) 。 基本思想：在直接插入排序中，只比较相邻的结点，一次比较最多把结点移动一个位置。如果对位置间隔较大距离的结点进行比较，使得结点在比较以后能够一次跨过较大的距离，这样就可以提高排序的速度。,希尔排序的基本过程,设待排序的对象序列有n个对象，首先取一个整数d1 n作为间隔，将全部对象分为d1个子序列，所有距离为d1的对象放在同一个序列中，在每一个子序列中分别施行直接插入排序，然后缩小间隔d2 ，如取d2 = d1 /2，重复上述的子序列划分和排序工作，直到最后取dt= 1为止。,希尔排序示例,i (0) (1) (2) (3) (4)
7、(5) di 21 25 49 25* 16 08 1 21 - - 25* 3 25 - - 16 49 - - 08 21 16 08 25* 25 49 2 21 - 08 - 25 2 16 - 25* - 49 08 16 21 25* 25 49 3 08 16 21 25* 25 49 1 08 16 21 25* 25 49,希尔排序算法 void ShellPass(SeqList R，int d) for(i=d+1；i0&R0.keyRj.key)； Rj+d=R0； ,void ShellSort(SeqList R) int increment=n； do incre
8、ment=increment/3+1； ShellPass(R，increment)； while(increment1)； ,为什么shell排序的时间性能优于直接插入排序呢？因为直接插入排序在初态为正序时所需时间最少，实际上，初态为基本有序时直接插入排序所需的比较和移动次数均较少。另一方面，当n值较小时，n和n2的差别也较小，即直接插入排序的最好时间复杂度O(n)和最坏时间复杂度O(n2)差别不大。在shell排序开始时增量较大，分组较多，每组的记录数目少，故各组内直接插入较快，后来增量逐渐缩小，分组数逐渐减少，而各组的记录数目逐渐增多，但组内元素已经过多次排序，数组已经比较接近有序状态，
9、所以新的一趟排序过程也较块。,希尔排序中增量di的取法,Shell最初的方案是d1 = n/2, di+1 = di /2，直到dt =1. Knuth的方案是di+1 = di /3+1 其它方案有：都取奇数为好；或di互质为好等等。,希尔排序的算法分析,对希尔排序的复杂度的分析很困难，在特定情况下可以准确地估算关键字的比较和对象移动次数，但是考虑到与增量之间的依赖关系，并要给出完整的数学分析，目前还做不到。 Knuth的统计结论是，平均比较次数和对象平均移动次数在n1.25 与1.6n1.25之间。 希尔排序的稳定性 希尔排序是一种不稳定的排序方法。如序列 3, 2, 2*, 5,9.3
10、交换排序,两种常见的交换排序,冒泡排序 快速排序,基本原理：两两比较待排序的对象的关键字，如果发生逆序，则交换之，直到全部对象都排好序为止。,冒泡排序的基本过程,假设待排序的n个对象的序列为R1,R2,., Rn，起始时排序范围是从R1到Rn 在当前的排序范围之内，自下至上对相邻的两个结点依次进行比较，让值较大的结点往下移(下沉)，让值较小的结点往上移(上冒)。每趟起泡都能保证值最小的结点上移至最上边，下一遍的排序范围为从下一结点到Rn。 在整个排序过程中，最多执行(n-1)遍。但执行的遍数可能少于(n-1)，这是因为在执行某一遍的各次比较没有出现结点交换时，就不用进行下一遍的比较。,冒泡排序
11、示例,i (0) (1) (2) (3) (4) (5) 21 25 49 25* 16 08 1 08 21 25 49 25* 16 2 08 16 21 25 49 25* 3 08 16 21 25 25* 49 4 08 16 21 25 25* 49,冒泡排序算法 void BubbleSort(SeqList R) int i，j，exchange； for(i=1;i=i；j-) if(Rj+1.keyRj.key) R0=Rj+1； Rj+1=Rj； Rj=R0； exchange=1； if(!exchange) return； ,冒泡排序的算法分析,考虑关键字的比较次数和
12、对象移动次数 在最好情况下，初始状态是递增有序的，一趟扫描就可完成排序，关键字的比较次数为n-1，没有记录移动。 若初始状态是反序的，则需要进行n-1趟扫描，每趟扫描要进行n-i次关键字的比较，且每次需要移动记录三次，因此，最大比较次数和移动次数分别为：,冒泡排序方法是稳定的。,快速排序的基本过程,快速排序法是一种所需比较次数较少，目前在内部排序中速度较快的方法。 其思想是取待排序的结点序列中某个结点的值作为控制值，采用某种方法把这个结点放到适当的位置，使得这个位置的左边的所有结点的值都小于等于这个控制值，而这个位置的右边的所有结点的值都大于等于这个控制值。,快速排序示例,49,38,65,9
13、7,76,13,27,49,38,65,97,76,13,27,49,27,38,65,97,76,13,49,49,38,97,76,13,65,49,49,38,13,97,76,65,49,49,38,13,76,97,65,49,49,38,13,49,76,49,65,49,49,temp,快速排序算法 void QuickSort(SeqList R，int low，int high) int pivotpos； if(lowhigh) pivotpos=Partition(R，low，high)； QuickSort(R，low，pivotpos-1)； QuickSort(R，
14、pivotpos+1，high)； ,划分算法 int Partition(SeqList R，int i，int j) ReceType pivot=Ri； while(i=pivot.key) j-； if(ij) Ri+=Rj； while(ij /endwhile Ri=pivot； return i； ,快速排序的算法分析,最好情况是每次所取的基准都是当前无序区的“中值”记录，划分的结果是基准的左右两个无序子区的长度大致相等。,考虑关键字的比较次数和对象移动次数 最坏情况是每次划分选取的基准都是当前无序区 中关键字最小（或最大）的记录，划分的结果是基准的左边（或右边）为空，划分前后无
15、序区的元素个数减少一个，因此，排序必须做n-1趟，每一趟中需做n-i次比较，所以最大比较次数为,快速排序的记录移动次数不会大于比较次数，所以，快速排序的最坏时间复杂度为O(n2)；最好时间复杂度为O(nlog2n)。 快速排序的平均时间复杂度也是(nlog2n)，空间复杂度为O(log2n)。 快速排序是不稳定的排序方法。例如2，2*，1 。,9.4 选择排序,两种常见的选择排序,直接选择排序 堆排序,基本原理: 将待排序的结点分为已排序(初始为空)和未排序两组，依次将未排序的结点中值最小的结点放入已排序的组的最后。,直接选择排序的基本过程,(1)在一组对象Ri到Rn中选择具有最小关键字的对象 (2)若它不是这组对象中的第一个对象，则将它与这组对象中的第一个对象对
