排序算法下——桶排序、计数排序和基数排序

栏目: 编程工具 · 发布时间: 6年前

内容简介:桶排序、计数排序和基数排序这三种算法的时间复杂度都为 ,因此,它们也被叫作线性排序(Linear Sort)。之所以能做到线性,是因为这三个算法是桶排序看起来很优秀,但事实上,桶排序对排序数据的要求是非常苛刻的。假如我们有 10 GB 的订单数据需要按照金额进行排序,但内存只有几百 MB ,这时候该怎么办呢?

桶排序、计数排序和基数 排序 这三种算法的时间复杂度都为 ,因此,它们也被叫作线性排序(Linear Sort)。之所以能做到线性,是因为这三个算法是 非基于比较 的排序算法,都不涉及元素之间的比较操作。

1. 桶排序(Bucket Sort)?

1.1. 桶排序原理

  • 桶排序 ,顾名思义,要用到“桶”。核心思想是将要排序的数据分到几个有序的桶里,每个桶的数据再单独进行排序。桶内排完序后,再把每个桶里的数据按照顺序依次取出,组成的序列就是有序的了。
排序算法下——桶排序、计数排序和基数排序

1.2. 桶排序的时间复杂度分析

  • 如果要排序的数据有 个,我们把它们均匀地划分到 个桶内,每个桶内就有 个元素。对每个桶内的数据进行快速排序,时间复杂度为 。 个桶排序时间复杂度就为 。当桶的个数接近数据个数时, 就是一个非常小的数,这个时候通排序的时间复杂度接近于 。

1.3. 桶排序的适用条件

桶排序看起来很优秀,但事实上,桶排序对排序数据的要求是非常苛刻的。

  • 首先, 要排序的数据需要很容易就能划分为 个桶,并且桶与桶之间有着天然的大小顺序
  • 其次, 数据在各个桶之间的分布是比较均匀的
  • 桶排序比较适合用在 外部排序 中。所谓的外部排序就是数据存储在外部磁盘中,数据比较大而内存有限,无法将数据全部加载到内存中去。

1.4. 一个桶排序的实例

假如我们有 10 GB 的订单数据需要按照金额进行排序,但内存只有几百 MB ,这时候该怎么办呢?

  • 我们先扫描一遍文件,确定订单金额的数据范围。

  • 如果扫描后发现订单金额处于 1 万元到 10 万元之间,我们将所有订单按照金额划分到 100 个桶内,第一个桶数据范围为[1, 1000],第二个桶数据范围为[1001, 2000]......,每个桶对应一个文件,同时将文件按照金额范围的大小顺序编号命名(如00、01、02...99)。

  • 如果订单金额分布均匀,则每个文件包含大约 100 MB 的数据,我们可以将每个小文件读入到内存中,进行快速排序。然后,再按顺序从各个小文件读取数据,写入到另外一个文件,即是排序好的数据了。

  • 如果订单分布不均,某一范围内数据特别多无法一次读入内存,则可以继续对此区间再进行划分,直到所有的文件都可以读入内存为止。

2. 计数排序(Counting Sort)?

2.1. 计数 排序算法 实现

  • 计数排序可以看作是桶排序的一种特殊情况。当要排序的数据所处的范围并不大时,比如最大值为 ,这时候,我们可以把数据分为 个桶,每个桶内的数据都是相同的,省掉了桶内排序的时间。

  • 假设高考分数的范围为 [0, 750],我们可以将考生的分数划分到 751 个桶内,然后再依次从桶内取出数据,就可以实现对考生成绩的排序了。因为只涉及到扫描遍历操作,因此时间复杂度为 。

但这个排序算法为什么叫计数排序呢,这是由计数排序算法的实现方法来决定的,我们来看一个简单的例子。

  • 假设有 8 个考生,他们的分数范围为 [0, 5]。这 8 个考生的成绩我们放在一个数组中,A[8] = {2, 5, 3, 0, 2, 3, 0, 3}。

  • 我们用大小为 6 的数组代表 6 个桶来统计考生的成绩分布情况,其中 下标表示考生的分数,数组内的值表示这个分数的考生个数 。我们遍历一遍数组后,就可以得到 C[6] = {2, 0, 2, 3, 0, 1,},得 0 分的共有 2 人,得 3 分的共有 3 人。

  • 如下所示,成绩为 3 的考生共有 3 个,小于 3 分的考生共有 4 个,所以在排好序的数据 R[8] 中,3 的位置应该为 4,5 和 6 。

排序算法下——桶排序、计数排序和基数排序
  • 而我们怎么得到这个位置呢?只需要对 C[6] 数组按顺序累计求和即可,这时候,C[6] 数组中的每个值就都表示 小于等于它的值的个数 了。
排序算法下——桶排序、计数排序和基数排序
  • 接下来,我们从后到前依次扫描数组 A[8]。当扫描到 3 时,我们取出 C[3] 的值 7,说明小于等于 3 的个数为 7 个,那么 3 就应该放在数组 R[8] 的第 7 个位置,也就是下标为 6 的地方。当我们再次遇到 3 的时候,这时候小于等于 3 的元素个数就少了一个,也就是我们要把 C[3] 相应地减去 1 。

  • 之所以要从后到前依次扫描数组,是因为这样 之前相同的元素就仍然会保持相同的顺序,可以保证排序算法的稳定性

  • 当我们扫描完整个数组 A[8] 时,数组 R[8] 中的数据也就从小到大排好序了,其详细过程可参考下图。

排序算法下——桶排序、计数排序和基数排序
  • 代码实现
// 假设数组中存储的都是非负整数
void Counting_Sort(int data[], int n)
{
    if (n <= 1)
    {
        return;
    }

    // 寻找数组的最大值
    int max = data[0];
    for (int i = 1; i < n; i++)
    {
        if (data[i] > max)
        {
            max = data[i];
        }
    }

    // 定义一个计数数组, 统计每个元素的个数
    int c[max+1] = {0};
    for (int i = 0; i < n; i++)
    {
        c[data[i]]++;
    }

    // 对计数数组累计求和
    for (int i = 1; i <= max; i++)
    {
        c[i] = c[i] + c[i-1];
    }

    // 临时存放排好序的数据
    int r[n] = {0};
    // 倒序遍历数组,将元素放入正确的位置
    for (int i = n-1; i >= 0; i--)
    {
        r[c[data[i]] - 1] = data[i];
        c[data[i]]--;
    }

    for (int i = 0; i < n; i++)
    {
        data[i] = r[i];
    }

}
复制代码

2.2. 计数排序的适用范围

  • 计数排序只适用于 数据范围不大的场景中 ,如果数据范围 比排序的数据 大很多,就不适合用计数排序了。

  • 计数排序能给 非负整数排序 ,如果数据是其他类型的,需要将其在不改变相对大小的情况下,转化为非负整数。比如数据有一位小数,我们需要将数据都乘以 10;数据范围为 [-1000, 1000],我们需要对每个数据加 1000。

3. 基数排序(Radix Sort)?

假设要对 10 万个手机号码进行排序,显然桶排序和计数排序都不太适合,那怎样才能做到时间复杂度为 呢?

1.1. 基数排序原理

  • 手机号码有这样的规律,假设要比较两个手机号码 的大小,如果在前面几位中, 手机号码已经比 大了,那后面几位就不用看了。

  • 借助 稳定排序算法 ,我们可以这么实现。从手机号码的最后一位开始,分别按照每一位的数字对手机号码进行排序,依次往前进行,经过 11 次排序之后,手机号码就都有序了。

  • 下面是一个字符串的排序实例,和手机号码类似。

排序算法下——桶排序、计数排序和基数排序
  • 根据每一位的排序,我们可以用刚才的桶排序或者计数排序来实现,它们的时间复杂度可以做到 。如果排序的数据有 位,则总的时间复杂度为 ,当 不大时,基数排序的时间复杂度就近似为 。

  • 有时候,要排序的数据并不都是等长的,比如我们要对英文单词进行排序。这时候,我们可以 把所有单词都补足到相同长度,位数不够的在后面补 ’0‘ ,所有字母的 ASCII 码都大于 ‘0’,因此不会影响原有的大小顺序。

  • 基数排序需要数据可以分割出独立的位出来,而且位之间有递进的关系。除此之外,每一位的数据范围都不能太大,要可以用线性排序算法来进行排序。

参考资料-极客时间专栏《数据结构与算法之美》

获取更多精彩,请关注「seniusen」!

排序算法下——桶排序、计数排序和基数排序

以上所述就是小编给大家介绍的《排序算法下——桶排序、计数排序和基数排序》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

暗时间

暗时间

刘未鹏 / 电子工业出版社 / 2011-7 / 35.00元

2003年,刘未鹏在杂志上发表了自己的第一篇文章,并开始写博客。最初的博客较短,也较琐碎,并夹杂着一些翻译的文章。后来渐渐开始有了一些自己的心得和看法。总体上在这8年里,作者平均每个月写1篇博客或更少,但从未停止。 刘未鹏说—— 写博客这件事情给我最大的体会就是,一件事情如果你能够坚持做8年,那么不管效率和频率多低,最终总能取得一些很可观的收益。而另一个体会就是,一件事情只要你坚持得足......一起来看看 《暗时间》 这本书的介绍吧!

SHA 加密
SHA 加密

SHA 加密工具

Markdown 在线编辑器
Markdown 在线编辑器

Markdown 在线编辑器

HEX CMYK 转换工具
HEX CMYK 转换工具

HEX CMYK 互转工具