9.6基数排序 基数排序的基本思想是: 借助多关键字排序的思想对单逻辑关键字进行排 序。即:用关键字不同的位值进行排序。 要讨论的问题 1.什么是“多关键字”排序?实现方法? 2.单逻辑关键字怎样“按位值”排序?
6 9.6 基数排序 要讨论的问题： 1. 什么是“多关键字”排序？实现方法？ 2. 单逻辑关键字怎样“按位值”排序？ 基数排序的基本思想是： 借助多关键字排序的思想对单逻辑关键字进行排 序。即：用关键字不同的位值进行排序
1.什么是“多关键字”排序?实现方法? 例1:对一副扑克牌该如何排序? 若规定花色和面值的顺序关系为 花色:◆<<<心 面值:2<3<4<5<6<7<8<9<10<J<Q<K<A 则可以先按花色排序,花色相同者再按面值排序; 也可以先按面值排序,面值相同者再按花色排序。 例2:职工分房该如何排序? 我校规定:先以总分排序(职称分+工龄分) 总分相同者,再按配偶总分排序,其次按配偶职 称、工龄、人口.等等排序。 以上两例都是典型的多关键字排序
7 1. 什么是“多关键字”排序？实现方法？ 例1：对一副扑克牌该如何排序？ 若规定花色和面值的顺序关系为： 花色： 面值：2 < 3 < 4 < 5 < 6 < 7 < 8 < 9 < 10 < J < Q < K < A 则可以先按花色排序，花色相同者再按面值排序； 也可以先按面值排序，面值相同者再按花色排序。 例2：职工分房该如何排序？ 我校规定：先以总分排序（职称分＋工龄分）； 总分相同者，再按配偶总分排序，其次按配偶职 称、工龄、人口……等等排序。 以上两例都是典型的多关键字排序！
多关键字排序的实现方法通常有两种: 最高位优先法MSD( Most Significant Digit first) 最低位优先法LSD( Least Significant Digit first) 例:对一副扑克牌该如何排序? 答:若规定花色为第一关键字(高位),面值为第二关键字 低位),则使用MSD和ISD方法都可以达到排序目的。 MSD方法的思路:先设立4个花色“箱"”,将全部牌按花色分 别归入4个箱内(每个箱中有13张牌);然后对每个箱中的牌 按面值进行插入排序(或其它稳定算法)。 LSD方法的思路:先按面值分成13堆(每堆4张牌),然后对 每堆中的牌按花色进行排序(用插入排序等稳定的算法)。 熄一想:用哪种方法更快些
8 多关键字排序的实现方法通常有两种： • 最高位优先法MSD (Most Significant Digit first) 例：对一副扑克牌该如何排序？ 答：若规定花色为第一关键字（高位），面值为第二关键字 （低位），则使用MSD和LSD方法都可以达到排序目的。 MSD方法的思路：先设立4个花色“箱”，将全部牌按花色分 别归入4个箱内（每个箱中有13张牌）；然后对每个箱中的牌 按面值进行插入排序（或其它稳定算法）。 LSD方法的思路：先按面值分成13堆（每堆4张牌），然后对 每堆中的牌按花色进行排序（用插入排序等稳定的算法）。 想一想：用哪种方法更快些？ • 最低位优先法LSD (Least Significant Digit first)