归并排序算法分析： 。时间效率：O(nlog2n) 因为在递归的归并排序算法中，函数Merge()做一趟两路归 并排序，需要调用merge()函数「n/(2lem)≈O(n/lem）次，而 每次merge()要执行t比较Olem)次，另外整个归并过程有 「log2n1“层”，所以算法总的时间复杂度为0(log2m)。 ● 空间效率：O(n) 因为需要一个与原始序列同样大小的辅助序列(T)。这 正是此算法的缺点。 。稳定性：稳定 6
6 归并排序算法分析： • 时间效率： O(nlog2n) 因为在递归的归并排序算法中，函数Merge( )做一趟两路归 并排序，需要调用merge ( )函数 n/(2len) O(n/len) 次，而 每次merge( )要执行比较O(len)次，另外整个归并过程有 log2n “层” ，所以算法总的时间复杂度为O(nlog2n)。 • 空间效率： O(n) 因为需要一个与原始序列同样大小的辅助序列（TR）。这 正是此算法的缺点。 • 稳定性：稳定
10.6 基数排序 (Radix Sort) 基数排序的基本思想是： 借助多关键字排序的思想对单逻辑关键字进行排 序。即：用关键字不同的位值进行排序。 要时论的问题： 1.什么是“多关键字”排序？实现方法？ 2.单逻辑关键字怎样“按位值”排序？
7 10.6 基数排序 (Radix Sort) 要讨论的问题： 1. 什么是“多关键字”排序？实现方法？ 2. 单逻辑关键字怎样“按位值”排序？ 基数排序的基本思想是： 借助多关键字排序的思想对单逻辑关键字进行排 序。即：用关键字不同的位值进行排序
1.什么是“多关键字”排序？实现方法？ 例1：对一副扑克牌该如何排序？ 若规定花色和面值的顺序关系为： 花色：◆<品<v< 面值：2<3<4<5<6<7<8<9<10<J<Q<K<A 则可以先按花色排序，花色相同者再按面值排序； 也可以先按面值排序，面值相同者再按花色排序。 例2：职工分房该如何排序？ 我校规定：先以总分排序（职称分+工龄分)： 总分相同者，再按配偶总分排序，其次按配偶职称、 工龄、人口.等等排序。 以上两例都是典型的多关键字排序/
8 1. 什么是“多关键字”排序？实现方法？ 例1：对一副扑克牌该如何排序？ 若规定花色和面值的顺序关系为： 花色： 面值：2 < 3 < 4 < 5 < 6 < 7 < 8 < 9 < 10 < J < Q < K < A 则可以先按花色排序，花色相同者再按面值排序； 也可以先按面值排序，面值相同者再按花色排序。 例2：职工分房该如何排序？ 我校规定：先以总分排序（职称分＋工龄分）； 总分相同者，再按配偶总分排序，其次按配偶职称、 工龄、人口.等等排序。 以上两例都是典型的多关键字排序！