[工学]数据结构10.ppt

先对 Kd-1 进行排序，然后对 Kd-2 进 行排序，依次类推，直至对最主位关键 字 K0 排序完成为止。 排序过程中不需要根据 “前一个” 关键字的排序结果，将记录序列分割成 若干个(“前一个”关键字不同的)子序列。 　　例如:学生记录含三个关键字: 系别、班号和班内的序列号，其中以系别为最主位关键字。 无序序列 对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法进行排序时，可以采用“分配-收集”的方法，其好处是不需要进行关键字间的比较。 　对于数字型或字符型的单关键字，可以看成是由多个数位或多个字符构成的多关键字，此时可以采用这种“分配-收集”的办法进行排序，称作基数排序法。 例如：对下列这组关键字 {209, 386, 768, 185, 247, 606, 230, 834, 539 } 首先按其 “个位数” 取值分别为 0, 1, …, 9 “分配” 成 10 组，之后按从 0 至 9 的顺序将 它们 “收集” 在一起； 然后按其 “十位数” 取值分别为 0, 1, …, 9 “分配” 成 10 组，之后再按从 0 至 9 的顺序将它们 “收集” 在一起； 最后按其“百位数”重复一遍上述操作。 　　在计算机上实现基数排序时，为减少所需辅助存储空间，应采用链表作存储结构，即链式基数排序，具体作法为： １．待排序记录以指针相链，构成一个链表； ２．“分配” 时，按当前“关键字位”所取值， 将记录分配到不同的 “链队列” 中，每个队列 中记录的 “关键字位” 相同； ３．“收集”时，按当前关键字位取值从小到大 将各队列首尾相链成一个链表; ４．对每个关键字位均重复 2) 和 3) 两步。 例如： p→369→367→167→239→237→138→230→139 进行第一次分配 进行第一次收集 f[0] r[0] f[7] r[7] f[8] r[8] f[9] r[9] p→230 →230← →367 ← →167 →237 →367→167→237 →138 →368→239→139 →369 ← →239 →139 →138← 进行第二次分配 p→230→237→138→239→139 p→230→367→167→237→138→368→239→139 f[3] r[3] f[6] r[6] →230 ← →237 →138 →239 →139 →367 ← →167 →368 →367→167→368 进行第二次收集 四、快速排序的时间分析 　假设一次划分所得枢轴位置 i=k，则对n 个记录进行快排所需时间： 　其中 Tpass(n)为对 n 个记录进行一次划分所需时间。 若待排序列中记录的关键字是随机分布的，则 k 取 1 至 n 中任意一值的可能性相同。 T(n) = Tpass(n) + T(k-1) + T(n-k) 设 Tavg(1)≤b 则可得结果： 结论: 快速排序的时间复杂度为O(nlogn) 由此可得快速排序所需时间的平均值为： 若待排记录的初始状态为按关键字有序时，快速排序将蜕化为起泡排序，其时间复杂度为O(n2)。 为避免出现这种情况，需在进行一次划分之前，进行“予处理”，即： 先对 R(s).key, R(t).key 和 R[?(s+t)/2?].key，进行相互比较，然后 取关键字为 “三者之中”的记录为枢轴记 录。 10.4 堆 排 序 简 单 选 择 排 序 堆 排 序 一、简单选择排序 假设排序过程中，待排记录序列的状态为： 有序序列R[1