10.6 基数排序²排序方法Ø先按花色排序，再按面值排序——最高位优 先Ø先按面值排序，再按花色排序——最低位优 先例：对52张扑克牌排序，花色优先… … … … 10.6 基数排序♣8♣7♣2♣3♣5♣J♣9♣4♣10♣Q♣6♣K1) 梅花：13 张2) 方块：13 张3) 红桃：13 张4) 黑桃：13 张♥Q♥K♥8♥A♥7♥4♥3♥9♥5♥J♥10♥2♥6♠K♠Q♠2♠3♠9♠A♠7♠J♠5♠8♠10♠6♠4♦5♦7♦2♦3♦8♦J♦9♦4♦10♦Q♦6♦A♦KØ最高位优先: 1. 按花色排序 2.按面值排序分配（分成4组）♣2♣3……10.6 基数排序♣K♣A♦2♦3……♦K♦A♥2♥3……♥K♥A♠2♠3……♠K♠A… … … … Ø最高位优先: 1. 按花色排序 2.按面值排序10.6 基数排序收集（按面值有序）……, , ,,,, , ,……,,,,,,,Ø最低位优先: 1. 按面值排序 2 .按花色排序分配(分成13组）分配（分成4组）, , ,,,, , , …… ,,,,,,,……………………按照上述顺序放入4组中10.6 基数排序Ø最低位优先: 1. 按面值排序 2 .按花色排序……………………收集（按花色有序）10.6 基数排序分配（分成4组）… … … … Initial list: 46 91 85 15 92 35 31 22012345678991468515 9235 3122收集: 91 31 92 22 85 15 35 460123456789913192 22851535 46收集: 15 22 31 35 46 85 91 92分配(按个位)分配(按十位)typedef sturct {KeyType key[MAX_NUM_KEY]; int next; }SLCell; typedef sturct{SLCell r[MAXSIZE]int bitnum; //关键字位数int rednum; //记录个数 }SLList;typedef int ArrType[RADIX]L.r 0123456784 6 9 1 8 51 5 9 2 3 5 3 12 2 123456780L.bitnum L.recnum2 80 1 2 3 4 5 6 7 8 9f 0 1 2 3 4 5 6 7 8 9e00 00 0 0 0 0 0 00 0 0 0 0 0000 0key next0 1 2 3 4 5 6 7 8 9f 0 1 2 3 4 5 6 7 8 9e27135168L.r 0123456784 6 9 1 8 51 5 9 2 3 5 3 12 2 107468000L.bitnum L.recnum2 8key next分配0 1 2 3 4 5 6 7 8 9f 0 1 2 3 4 5 6 7 8 9e27135168L.r 0123456784 6 9 1 8 51 5 9 2 3 5 3 12 2 207468153L.bitnum L.recnum2 8key next收集0 1 2 3 4 5 6 7 8 9f 0 1 2 3 4 5 6 7 8 9e00000000L.r 0123456784 6 9 1 8 51 5 9 2 3 5 3 12 2 207468153L.bitnum L.recnum2 8key next收集0 1 2 3 4 5 6 7 8 9f 0 1 2 3 4 5 6 7 8 9eL.r 0123456784 6 9 1 8 51 5 9 2 3 5 3 12 2 205000060L.bitnum L.recnum2 8key next441783 253681分配0 1 2 3 4 5 6 7 8 9f 0 1 2 3 4 5 6 7 8 9e44178L.r 0123456784 6 9 1 8 51 5 9 2 3 5 3 12 2 435280167L.bitnum L.recnum2 8key next3 253781收集void RadixSort(SLList i0;--i){ //对关键字的第i位作一趟基数排序Distribute (L.r,i,f,e); // 分配Collect (L.r, i, f, e); // 收集} }//RadixSortvoid Distribute (SLCell j
v三种平均时间复杂度为O(nlog2n)的算法中v快速排序的平均效率高，但是最坏时间复杂 度为O(n2)，且空间复杂度为O(log2n)v堆排序的最坏时间复杂度为O(nlog2n)，且 空间复杂度仅为O(1)v归并排序的最坏时间复杂度也为O(nlog2n) ，而且是稳定算法，但是空间复杂度为O(n)排序算法小结不同的排序方法适应不同的应用环境和要求 v若n较小，可采用直接插入或简单选择排序 当记录规模较小时，直接插入排序较好，它 会比选择更少的比较次数，且是稳定的； 当记录规模较大时，因为直接选择移动的记 录数少于直接插人，所以宜用选直接选择排 序; v若初始状态基本有序，应选用直接插人、冒泡 ; v若n较大，则应采用时间复杂度为O(nlog2n)的 排序方法：快速排序、堆排序或归并排序; v特殊的基数排序;学习要点²理解各种排序方法的基本思想； ²理解“稳定”或“不稳定”的含义；²掌握各种排序方法及特点；。