各类排序算法总结

五.分配类排序->基数排序:

基数排序是一种借助于多关键码排序的思想，是将单关键码按基数分成“多关键码”进行排序的方法。基数排序属于”低位优先”排序法,通过反复进行分配与收集操作完成排序.

对于数字型或字符型的单关键字，可以看成是由多个数位或多个字符构成的多关键字，

此时可以采用这种“分配-收集”的办法进行排序，称作基数排序法。其好处是不需要进行关键字间的比较。

例如：对下列这组关键字{278, 109, 063, 930, 589, 184, 505, 269, 008，083 },首先按其“个位数”取值分别为0, 1, …，9“分配”成10 组，之后按从0 至9 的顺序将它们“收集”在一起;然后按其“十位数” 取值分别为0, 1, …，9“分配”成10 组，之后再按从0 至9 的顺序将它们“收集”在一起;最后按其“百位数”重复一遍上述操作，便可得到这组关键字的有序序列。

在计算机上实现基数排序时，为减少所需辅助存储空间，应采用链表作存储结构，即链式基数排序，具体作法为：

(1)待排序记录以指针相链，构成一个链表；

(2)“分配”时，按当前“关键字位”所取值，将记录分配到不同的“链队列”中，每个队列中记录的“关键字位”相同；

(3)“收集”时，按当前关键字位取值从小到大将各队列首尾相链成一个链表;

(4)对每个关键字位均重复(2)和(3)两步。

【性能分析】

(1)空间效率：链式基数排序空间复杂度为O(rd)。

(2)时间效率：基数排序的时间复杂度为O(d(n+rd))。

其中，分配为O(n); 收集为O(rd)(rd 为“基”), d 为“分配-收集”的趟数。

(3）稳定性：基数排序是一个稳定的排序方法。

六. 各种内部排序算法的比较

1、时间性能

（1）按平均的时间性能来分，有三类排序方法：

时间复杂度为O(nlogn)的方法有：快速排序、堆排序和归并排序，其中以快速排序为最好；

时间复杂度为O(n^2)的有：直接插入排序、起泡排序和简单选择排序，其中以直接插入为最好，特别是对那些对关键字近似有序的记录序列尤为如此；

时间复杂度为O(n)的排序方法只有基数排序。

（2）当待排记录序列按关键字顺序有序时，直接插入排序和起泡排序能达到O(n)的时间

复杂度;而对于快速排序而言，这是最不好的情况，此时的时间性能蜕化为O(n^2)，因此是应该尽量避免的情况。

（3）简单选择排序、堆排序和归并排序的时间性能不随记录序列中关键字的分布而改变。

2、空间性能

（1）所有的简单排序方法(包括：直接插入、起泡和简单选择)和堆排序的空间复杂度为O(1)；

（2）快速排序为O(logn)，为栈所需的辅助空间;

（3）归并排序所需辅助空间最多，其空间复杂度为O(n);

（4）链式基数排序需附设队列首尾指针，则空间复杂度为O(rd)

3、排序方法的稳定性能

当对多关键字的记录序列进行LSD(基数排序)方法排序时，必须采用稳定的排序方法。

快速排序和堆排序是不稳定的排序方法。

多数情况下,排序是按记录的主关键字进行的,此时不用考虑排序方法的稳定性.如果排序是按照记录的次关键字进行的,则应充分考虑排序方法的稳定性.

4、各种排序方法的综合比较和选择

（1）各种排序方法的比较如表。

（2）选择

选择排序方法时需要考虑的因素有：待排序的记录个数n；记录本身的大小；关键字的

分布情况；对排序稳定性的要求；语言工具的条件；辅助空间的大小。

依据这些元素，可以得到以下几点结论：

①待排序的记录数目n 较小时，则采用插入排序和简单选择排序；

②若待排序记录按关键字基本有序，则宜采用直接插入排序和冒泡排序；直接插入排序是最佳的排序方法,常与快速排序,归并排序等其他排序方法综合使用.

③当n 很大且关键字的位数较少时，采用链式基数排序较好；

④若n 较大，则应采用时间复杂度为O(nlogn)的排序方法：快速排序、堆排序或归并排序。