数据结构课件10资料.ppt

第十章 排序;;10.1 概述;1、什么是排序？;2、内部排序和外部排序;3、内部排序的方法; 时间效率——排序速度（比较次数与移动次数） 空间效率——占内存辅助空间的大小 稳定性——A和B的关键字相等，排序后A、B的先后次序保持不变，则称这种排序算法是稳定的。;排序算法分类;10.2 插入排序;有序序列R[1..i-1];直接插入排序;;从R[i-1]起向前进行顺序查找， 监视哨设置在R[0]；; 对于在查找过程中找到的那些关键字不小于R[i].key的记录，并在查找的同时实现记录向后移动；;令 i = 2，3，…, n, 实现整个序列的排序。;void InsertionSort ( SqList L ) { // 对顺序表 L 作直接插入排序。 for ( i=2; i=L.length; ++i ) if (L.r[i].key L.r[i-1].key) { } } // InsertSort;内部排序的时间分析：;算法分析;最坏情况下：第 i 趟比较i次，移动i+1次 ;若出现各种可能排列的概率相同，则可取最好情况和最坏情况的平均情况 平均情况比较次数和移动次数为n2/4; 因为 R[1..i-1] 是一个按关键字有序的有序序列，则可以利用折半查找实现“在R[1..i-1]中查找R[i]的插入位置”，如此实现的插入排序为折半插入排序。;i=2;i=3;i=4;i=5;i=6;void BiInsertionSort ( SqList L ) { } // BInsertSort;low = 1; high = i-1; while (low=high) { };14 36 49 52 80;折半查找比顺序查找快，所以折半插入排序就平均性能来说比直接插入排序要快 它所需要的关键码比较次数与待排序对象序列的初始排列无关，仅依赖于对象个数。在插入第 i 个对象时，需要经过 ?log2i? +1 次关键码比较，才能确定它应插入的位置;当 n 较大时，总关键码比较次数比直接插入排序的最坏情况要好得多，但比其最好情况要差 在对象的初始排列已经按关键码排好序或接近有序时，直接插入排序比折半插入排序执行的关键码比较次数要少 折半插入排序的对象移动次数与直接插入排序相同，依赖于对象的初始排列 ;减少了比较次数，但没有减少移动次数 平均性能优于直接插入排序;算法思想的出发点：;希尔排序;其中，d 称为增量，它的值在排序过程中从大到小逐渐缩小，直至最后一趟排序减为1。;38;时间复杂度是n???d的函数： 空间复杂度为 o(1) 是一种不稳定的排序方法;10.3 交换排序;一、起泡排序;基本思想：每趟不断将记录两两比较，并按“前小后大” 规则交换;例;算法分析;;快速排序;一趟快速排序（一次划分）;s;int Partition (RedType R[], int low, int high) { }// Partition ;三、快速排序;void QSort (RedType R[], int s, int t ) { // 对记录序列R[s..t]进行快速排序 if (s t-1) { // 长度大于1 } } // QSort;void QuickSort( SqList L) { // 对顺序表进行快速排序 QSort(L.r, 1, L.length); } // QuickSort;可以证明，平均计算时间是O(nlog2n)。 实验结果表明：就平均计算时间而言，快速排序是我们所讨论的所有内排序方法中最好的一个。 快速排序是递归的，需要有一个栈存放每层递归调用时参数（新的low和high）。 最大递归调用层次数与递归树的深度一致，因此，要求存储开销为 O(log2n) 。;算法分析;算法分析;10.4 选择排序;一、简单选择排序;;;简单选择排序的算法描述如下：;算法分析;二、堆排序;ri;(87,78,53,45,65,09,31,17,23);判定(80,75,40,62,73,35,28,50,38,25,47,15)是否为堆;堆排序;void HeapSort ( HeapType H ) { // 对顺序表 H 进行堆排序 } // HeapSort;如何“建堆”？;;从第?n/2?个元素起，至第一个元素止，进行反复筛选;;;;;;;;将根结点r[1]与左、右子树根结点比较，并与小者交换 重复直至叶子结点，得到新的堆;;堆的重新调整－1;堆的重新调整－2;堆的重新调整－2;堆的重新调整－2;堆的重新调整－3;堆的重