数据结构学习笔记——基数排序和排序算法总结

一、基数排序排序思想

基数排序与前面的排序算法不一样，它不基于比较和移动元素来进行排序，而是基于多关键字排序的思想，将一个逻辑关键字分为多个关键字，它是基于关键字各位的大小进行排序的。基数排序有两种实现方式：最高位优先法（MSD）和最低位优先法（LSD），分别是按关键字高次位排序和低次位排序。

例题

例如，下面通过最低位优先法，对给定的关键字序列{110，119，007，911，114，120，122}进行排序：

1、该序列的链式结构如下：

2、首先按照关键字的个位数字大小进行第一趟基数排序：

3、根据第一趟的顺序，按照关键字的十位数字大小进行第二趟基数排序：

4、根据第二趟的顺序，按照关键字的百位数字大小进行第三趟基数排序：

即，通过最低位优先法，得到排好的序列为{007，110，114，119，120，122，911}。

二、基数排序算法分析

分析：
（1）基数排序适用于以下情况：

1、数据元素的关键字可以很容易地进行拆分成d组，且d较小；
2、每组关键字的取值范围不大，即r较小；
3、数据元素个数n较大。
1
2
3

（2）空间复杂度：每一趟基数排序需要辅助空间r个队列，每趟排序后会重复使用这些队列，基数排序的空间复杂度为O( r )。
（3）时间复杂度：由于基数排序需进行d趟分配和收集操作，所以基数排序的排序趟数与初始序列无关。其时间复杂度与初始序列无关，基数排序需进行d趟分配和收集操作，一趟分配需要O(n)数量级，一趟收集需要O( r )数量级，即总排序的时间复杂度为O(d(n+r))。
（4）稳定性：基数排序是一种稳定的排序算法。
（5）适用性：基数排序只适用于链式存储。
（6）排序方式：基数排序与前面的归并排序一样，也是是一种外部排序（Out-place）。