【数据结构】内部排序小结- -基数排序

1 思想

• 基数排序是比较特别的内部排序，并不基于比较进行排序，而是基于关键字的各位进行排序。借助多关键字排序实现对单逻辑关键字排序。
• 有两种方法实现多关键字排序：
  最高位优先(MSD , Most Significant Digital First)
  最低位优先(LSD)

最低有先为位基数排序 过程如下：

• 最低优先位（LSD）就是权重最小的优先划分子序列，按照权重递划分成若干子序列，然后像串糖葫芦一样，串起来，最终得到一个递增有序序列。
• 每趟( d趟 ）都需要做一次 分配 和 收集 。
  关于分配：队列编号( r个 )并置空—>关键字按某种关系入队
  关于收集：将队列的结点首尾相连—>得到新结点序列—>新的线性表

2 算法分析

• 稳定性：稳定
• 空间复杂度：O（ r ）
• 与初态是否有关：无关
• 时间复杂度：
  最好时间复杂度：O ( d( n+r) )
  最坏时间复杂度：O ( d( n+r) )
  平均时间复杂度：O ( d( n+r) )

关于时间复杂度：需要d 趟分配和回收，一趟分派分配需要O（ n ）（n个元素），一趟收集需要O（ r ）（r组关键字），故时间复杂度是O ( d( n+r) )。
关于空间复杂度：每趟收集都需要辅助存储空间为r（r组关键字），在后续排序中会重复使用，故空间复杂度是O（ r ）。