4. 非基于比较的排序算法

　　非基于比较的排序算法主要有三种，分别为：基数排序，桶排序和计数排序。这些算法均是针对特殊数据的，不如要求数据分布均匀，数据偏差不会太大。采用的思想均是内存换时间，因而全是非原地排序。

　　4.1 基数排序

　　特点：稳定排序，非原地排序，时间复杂度O(N)

　　思想：把每个数据看成d个属性组成，依次按照d个属性对数据排序（每轮排序可采用计数排序），复杂度为O(d*N)

　　适用场景：数据明显有几个关键字或者几个属性组成

　　4.2 桶排序

　　特点：稳定排序，非原地排序，时间复杂度O(N)

　　思想：将数据按大小分到若干个桶（比如链表）里面，每个桶内部采用简单排序算法进行排序。

　　适用场景：0

　　4.3 计数排序

　　特点：稳定排序，非原地排序，时间复杂度O(N)

　　思想：对每个数据出现次数进行技术（用hash方法计数，最简单的hash是数组！），然后从大到小或者从小到大输出每个数据。

　　使用场景：比基数排序和桶排序广泛得多。

5. 总结

　　对于基于比较的排序算法，大部分简单排序(直接插入排序，选择排序和冒泡排序)都是稳定排序，选择排序除外；大部分高级排序（除简单排序以外的）都是不稳定排序，归并排序除外，但归并排序需要额外的存储空间。对于非基于比较的排序算法，它们都对数据规律有特殊要求 ，且采用了内存换时间的思想。排序算法如此之多，往往需要根据实际应用选择最适合的排序算法。