排序(2010)-基数.ppt

10 6基数排序 排序方法先按花色排序 再按面值排序 最高位优先先按面值排序 再按花色排序 最低位优先 例 对52张扑克牌排序 花色优先 10 6基数排序 1 梅花 13张 2 方块 13张 3 红桃 13张 4 黑桃 13张 最高位优先 1 按花色排序2 按面值排序 分配 分成4组 10 6基数排序 最高位优先 1 按花色排序2 按面值排序 10 6基数排序 收集 按面值有序 最低位优先 1 按面值排序2 按花色排序 分配 分成13组 分配 分成4组 10 6基数排序 最低位优先 1 按面值排序2 按花色排序 收集 按花色有序 10 6基数排序 分配 分成4组 Initiallist 4691851592353122 0 1 2 3 4 5 6 7 8 9 91 46 85 15 92 35 31 22 收集 9131922285153546 0 1 2 3 4 5 6 7 8 9 91 31 92 22 85 15 35 46 收集 1522313546859192 分配 按个位 分配 按十位 typedefsturct KeyTypekey MAX NUM KEY intnext SLCell typedefsturct SLCellr MAXSIZE intbitnum 关键字位数intrednum 记录个数 SLList typedefintArrType RADIX L r 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 keynext 2 7 1 3 5 1 6 8 L r keynext 分配 2 7 1 3 5 1 6 8 L r keynext 收集 0 0 0 0 0 0 0 0 L r keynext 收集 L r keynext 4 4 1 7 8 3 2 5 3 6 8 1 分配 4 4 1 7 8 L r keynext 3 2 5 3 7 8 1 收集 voidRadixSort SLList 收集 RadixSort voidDistribute SLCell Distribute voidCollect SLCell Collect 10 6基数排序 基数排序的特点关键字包含多位k k1k2 kd最低位优先基本步骤 分配 收集时间复杂度O d n r 空间复杂度O n r 稳定 排序算法小结 排序算法小结 几点说明几种简单的排序算法 1 2 3 的最好时间复杂度都为O n 说明算法的输入在接近有序时的效率比较高 三种平均时间复杂度为O nlog2n 的算法中快速排序的平均效率高 但是最坏时间复杂度为O n2 且空间复杂度为O log2n 堆排序的最坏时间复杂度为O nlog2n 且空间复杂度仅为O 1 归并排序的最坏时间复杂度也为O nlog2n 而且是稳定算法 但是空间复杂度为O n 排序算法小结 不同的排序方法适应不同的应用环境和要求若n较小 可采用直接插入或简单选择排序当记录规模较小时 直接插入排序较好 它会比选择更少的比较次数 且是稳定的 当记录规模较大时 因为直接选择移动的记录数少于直接插人 所以宜用选直接选择排序 若初始状态基本有序 应选用直接插人 冒泡 若n较大 则应采用时间复杂度为O nlog2n 的排序