非比较排序算法

基数排序算法

基数排序是非比较排序算法,算法的时间复杂度是O(n). 相比于快速排序的O(nlgn),从表面上看具有不小的优势.但事实上可能有些出入,因为基数排序的n可能具有比较大的系数K.因此在具体的应用中,应首先对这个排序函数的效率进行评估.

基数排序介绍

基数排序能达到线性的时间复杂度。
基数排序的主要思路是,将所有待比较数值(注意,必须是正整数
)统一为同样的数位长度,数位较短的数前面补零. 然后, 从最低位开始, 依次进行一次稳定排序
所以这里的排序可以使用计数排序。
这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列.

为什么要从低位开始向高位排序?

** 如果要从高位排序, 那么次高位的排序会影响高位已经排好的大小关系. 在数学中, 数位越高,数位值对数的大小的影响就越大
**

为什么同一数位的排序子程序要使用稳定排序?

** 稳定排序能保证,上一次的排序成果被保留,十位数的排序过程能保留个位数的排序成果,百位数的排序过程能保留十位数的排序成果.**

桶排序算法

桶排序是用空间换时间的排序算法。
而且桶排序是稳定的排序算法。

桶排序的思想

利用一个映射函数将带排数组划分为M个子区间，然后对每个子区间进行排序，再按序输出每个区间的元素。
注意：这里的映射函数有一个限制，就是要保证单调递增。这样才能保证桶B(i)中的元素要大于B(i-1)的元素。
因此桶排序的采用的数据结构是数组链表。而且为了保证对每个桶内元素快速排序，要让桶的数量更多，这样每个桶中的元素个数就相应的变少了。

计数排序

基于比较的函数（快排，堆排）时间复杂度是有下限的（nlgn），但是非比较类型的排序方法可以达到线性的时间复杂度，但是非比较类型的排序算法对元素自身有着限制条件。

计数排序介绍

计数排序的本质是在序列A中计算比元素x小于等于的元素个数，则就知道元素x的最终位置了。

而计算比元素x小的元素个数的方法就是用下标法直接计数（这就是时间复杂度为n的秘诀，所以整个序列的范围不能太大，否则对内存不友好）

计数排序是稳定的

计数排序的算法流程

计数排序的流程如下：
假设输入数组A，结果数组B，以及用于计数的数组C。
数组C的长度为0到m（m为A的最大元素值）
1:对元素A进行遍历，令C[A[i]]自增。
2：从前往后令C[i] += C[i-1],则C[i]表示在A中小于等于元素i元素的个数。
3：对B数组进行填充，将A中的每个元素t放在B数组的第C(t)项，然后将C(t)减去1.