非比较排序算法

作者: lintong | 来源:发表于2015-02-20 13:46 被阅读356次

    基数排序算法

    基数排序是非比较排序算法,算法的时间复杂度是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.

    相关文章

      网友评论

        本文标题:非比较排序算法

        本文链接:https://www.haomeiwen.com/subject/ruayxttx.html