数据结构-用面向对象语言描述-殷人昆-第九章资料.ppt

第九章 排序;概述 插入排序 交换排序 选择排序 基数排序;概述;概述;排序算法的稳定性: 如果在元素序列中有 2 个元素r[i]和r[j], 它们的排序码 k[i] == k[j] , 且在排序之前, 元素r[i]排在r[j]前面。如果在排序之后, 元素r[i]仍在元素r[j]的前面, 则称这个排序方法是稳定的, 否则称这个排序方法是不稳定的。;内排序: 是指在排序期间数据元素全部存放在内存的排序。;外排序: 是指在排序期间全部元素个数太多，不能同时存放在内存，必须根据排序过程的要求，不断在内、外存之间移动的排序。;排序的时间开销: 排序的时间开销是衡量算法好坏的最重要的标志。排序的时间开销可用算法执行中的数据比较次数与数据移动次数来衡量。;算法运行时间代价的大略估算 一般都按平均情况进行估算。 对于那些受元素排序码序列初始排列及元素个数影响较大的，需要按最好情况和最坏情况进行估算。; 基本方法是：设待排序元素序列中的元素个数为 n。最多作 n-1 趟，i = 1, 2, ?, n-1。在第 i 趟中从后向前，j = n-1, n-2, ?, i，顺次两两比较V[j-1].key和V[j].key。如果发生逆序，则交换V[j-1]和V[j]。;;; 算法分析 第i趟对待排序元素序列V[i-1],V[i],?,V[right]进行排序，结果将该序列中排序码最小的元素交换到序列的第一个位置(i-1)。 起泡排序需要一个附加元素以实现元素值的对换。起泡排序是一个稳定的排序方法。;最多做n-1趟起泡就能把所有元素排好序。 在元素的初始排列已经按排序码从小到大排好序时，此算法只执行一趟起泡，做n-1次排序码比较，不移动元素。这是最好的情形。 最坏的情形是算法执行n-1趟起泡,第i趟 (1≤ i?n) 做n-i次排序码比较, 执行n-i次元素交换。在最坏情形下总的排序码比较次数KCN和元素移动次数RMN为：;插入排序 (Insert Sorting);直接插入排序 (Insert Sort);;;;; 算法分析 设待排序元素个数为currentSize = n, 则该算法的主程序执行n-1趟。 排序码比较次数和元素移动次数与元素排序码的初始排列有关。;最好情况下，排序前元素已按排序码从小到大有序，每趟只需与前面有序元素序列的最后一个元素比较1次，总的排序码比较次数为 n-1, 元素移动次数为0。 最坏情况下, 第 i 趟时第 i 个元素必须与前面 i 个元素都做排序码比较, 并且每做1次比较就要做1次数据移动。则总排序码比较次数KCN和元素移动次数RMN分别为 ;平均情况下排序的时间复杂度为 o(n2)。 直接插入排序是一种稳定的排序方法。 ; 希尔排序方法又称为缩小增量排序。该方法的基本思想是 : 设待排序元素序列有 n 个元素, 首先取一个整数 gap n 作为间隔，将全部元素分为 gap 个子序列，所有距离为 gap 的元素放在同一个子序列中，在每一个子序列中分别; 施行直接插入排序。然后缩小间隔 gap, 例如取 gap = ?gap/2?，重复上述的子序列划分和排序工作。直到最后取 gap == 1，将所有元素放在同一个序列中排序为止。 开始时 gap 的值较大，子序列中的元素较少，排序速度较快; 随着排序进展，gap 值逐渐变小, 子序列中元素个数逐渐变多，由于前面工作的基础，大多数元素已基本有序，所以排序速度仍然很快。;21;;;算法分析 Gap的取法有多种。最初 shell 提出取 gap = ?n/2?，gap = ?gap/2?，直到gap = 1。knuth 提出取 gap = ?gap/3? +1。还有人提出都取奇数为好，也有人提出各 gap 互质为好。 对特定的待排序元素序列，可以准确地估算排序码的比较次数和元素移动次数。;想要弄清排序码比较次数和元素移动次数与增量选择之间的依赖关系，并给出完整的数学分析，还没有人能够做到。 Knuth利用大量实验统计资料得出 : 当 n 很大时，排序码平均比较次数和元素平均移动次数大约在 n1.25 到 1.6n1.25 的范围内。这是在利用直接插入排序作为子序列排序方法的情况下得到的。 希尔排序是一种不稳定的排序方法。; 基本思想是任取待排序元素序列中的某个元素 (例如取第一个元素) 作为基准，按照该元素的排序码大小，将整个元素序列划分为左右两个子序列： 左侧子序列中所有元素的排序码都小于或等于基准元素的排序码 ;右侧子序列中所有元素的排序码都大于基准元素的排序码 基准元素则排在这两个子序列中间(这也是该元素最终应安放的位置)。 然后分别对这两个子序列重复施行上述方法，直到所有的元素都排在相应位置上为止。;pivotpos：指向基准元素位置，