基数类排序

阅读量：

基本概念界定

基数排序（radix sort）是一种分配式排序（distribution sort），亦被称为桶子法（bucket sort 或 bin sort）。该算法通过依据键值进行检索，将待排序的元素分派到对应的“桶”中，从而实现排序的目的。

基本思想阐述

复制代码

    基数排序（以整形为例），将整形10进制按每位拆分，然后从低位到高位依次比较各个位。主要分为两个过程：
    (1)分配，先从个位开始，根据位值(0-9)分别放到0~9号桶中
    (2)收集，再将放置在0~9号桶中的数据按顺序放到数组中
    重复(1)(2)过程，从个位到最高位

这里写图片描述

复杂度分析与评估

复制代码

    r为基数，d为位数
    空间效率：O(n+r)
    基数排序最好为O(d(n+r)) 。
    基数排序的最坏为O(d(n+r))。
    基数排序的平均为O(d(n+r))。
    基数排序是稳定的。

全部评论 (0)

还没有任何评论哟~