数据结构 第九章 内部排序.ppt

　　例如:学生记录含三个关键字: 系别、班号和班内的序列号，其中以系别为最主位关键字。 无序序列 对K2排序 对K1排序 对K0排序 3,2,30 1,2,15 3,1,20 2,3,18 2,1,20 1,2,15 2,3,18 3,1,20 2,1,20 3,2,30 3,1,20 2,1,20 1,2,15 3,2,30 2,3,18 1,2,15 2,1,20 2,3,18 3,1,20 3,2,30 LSD的排序过程如下: 二、链式基数排序 　 假如多关键字的记录序列中，每个关键字的取值范围相同，则按LSD法进行排序时，可以采用“分配-收集”的方法，其好处是不需要进行关键字间的比较。 　对于数字型或字符型的单关键字，可以看成是由多个数位或多个字符构成的多关键字，此时可以采用这种“分配-收集”的办法进行排序，称作基数排序法。 设 Tavg(1)≤b 则可得结果： 结论: 快速排序的时间复杂度为O(nlogn) 由此可得快速排序所需时间的平均值为： 若待排记录的初始状态为按关键字有序时，快速排序将蜕化为起泡排序，其时间复杂度为O(n2)。 为避免出现这种情况，需在进行一次划分之前，进行“予处理”，即： 先对 R(s).key, R(t).key 和 R[?(s+t)/2?].key，进行相互比较，然后 取关键字为 “三者之中”的记录为枢轴记 录。 9.4 堆 排 序 简 单 选 择 排 序 堆 排 序 一、简单选择排序 假设排序过程中，待排记录序列的状态为： 有序序列R[1..i-1] 无序序列 R[i..n] 第 i 趟 简单选择排序 从中选出 关键字最小的记录 有序序列R[1..i] 无序序列 R[i+1..n] 简单选择排序的算法描述如下： void SelectSort (Elem R[], int n ) { // 对记录序列R[1..n]作简单选择排序。 for (i=1; in; ++i) { // 选择第 i 小的记录，并交换到位 } } // SelectSort j = SelectMinKey(R, i); // 在 R[i..n] 中选择关键字最小的记录 if (i!=j) R[i]←→R[j]; // 与第 i 个记录交换 时间性能分析 　对 n 个记录进行简单选择排序，所需进行的 关键字间的比较次数 总计为： 　 移动记录的次数，最小值为 0,最大值为3(n-1) 。 二、堆排序 堆是满足下列性质的数列{r1, r2, …，rn}： 或 堆的定义: {12, 36, 27, 65, 40, 34, 98, 81, 73, 55, 49} 例如: 是小顶堆 {12, 36, 27, 65, 40, 14, 98, 81, 73, 55, 49} 不是堆 (小顶堆) (大顶堆) ri r2i r2i+1 若将该数列视作完全二叉树，则 r2i 是 ri 的左孩子； r2i+1 是 ri 的右孩子。 12 36 27 65 49 81 73 55 40 34 98 例如: 是堆 14 不 　堆排序即是利用堆的特性对记录序列进行排序的一种排序方法。 例如： 建大顶堆 { 98, 81, 49, 73, 36, 27, 40, 55, 64, 12 } { 12, 81, 49, 73, 36, 27, 40, 55, 64, 98 } 交换 98 和 12 重新调整为大顶堆 { 81, 73, 49, 64, 36, 27, 40, 55, 12, 98 } { 40, 55, 49, 73, 12, 27, 98, 81, 64, 36 } 经过筛选 void HeapSort ( HeapType H ) { // 对顺序表 H 进行堆排序 } // HeapSort for ( i=H.length/2; i0; --i ) HeapAdjust ( H.r, i, H.length );//建大顶堆 for ( i=H.length; i1; --i ) { H.r[1]←→H.r[i]; // 将堆顶记录和当前未经排序子序列 // H.r[1..i]中最后一个记录相互交换 HeapAdjust(H.r, 1, i-1); // 对 H.r[1] 进行筛选 } 如何“建堆”？ 两个问题: 如何“筛选”？ 定义堆类型为: typedef SqList HeapType;