桶排序(Bucket Sort) - 算法笔记

最快的排序算法是什么?

Posted by ChungZH on 2018-10-13

这篇文章我们来学习一下桶排序

前言

最近买了一本 啊哈磊 写的《啊哈!算法》,发现挺不错的。于是,我决定每熟练掌握一个算法或数据结构就写一篇博客,既能巩固所知,又能让更多人了解。

桶排序简介

桶排序是一个非常快的排序算法,该算法的基本思想由 E.J. IssacR.C. Singleton 提出。

桶排序的意思就是:把数据放进桶里面,从而完成排序。

举个栗子:用桶排序的方法排序 10 个数: 1 0 8 3 2 5 4 9 0 9 。这些数最大的不超过 10 。

思路:

  1. 首先,我们新建大小为 11 的“桶”数组。因为从 0 到 10 之间有11个数。并把这个数组的元素初始化为 0。 int a[11] = {0};

  2. 下面开始处理每一个数:

    ①. 给第一个数字所在的桶加 1 。第一个数是 1 ,就给“桶”数组中下标为 1 的元素加一,即a[1]++;

    ②. 给第二个数字所在的桶加 1 。第二个数是 0 ,就给“桶”数组中下标为 0 的元素加一,即a[0]++;

    ③. 给第三个数字所在的桶加 1 。第三个数是 8 ,就给“桶”数组中下标为 8 的元素加一,即a[8]++;

    以此类推……

  3. 输出“桶”数组。

    1
    2
    3
    4
    5
    6
    7
    for (int i = 0; i <= 10; i++)
    {
    for (int j = 0; j < a[i]; j++) // 桶数组元素里的值是多少就循环多少次,如果为 0 就不输出
    {
    cout << i << " ";
    }
    }

桶排序实现

下面开始 C++ 代码实现(其实如果理解了算法,什么语言都差不多的。):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
using namespace std;
int main()
{
int a[11] = {0}; // 定义“桶”数组并初始化为 0
for (int i = 0; i < 10; i++) // 循环 5 次输入分数
{
int temp;
cin >> temp;
a[temp]++; // 进行计数
}

for (int i = 0; i <= 10; i++)
{
for (int j = 0; j < a[i]; j++) // 桶数组元素里的值是多少就循环多少次,如果为 0 就不输出
{
cout << i << " ";
}
}

cout << endl;

return 0;
}

输入:

1
1 0 8 3 2 5 4 9 0 9

输出:

1
0 0 1 2 3 4 5 8 9 9

成功排序~

下一篇文章我们来学习快速排序(Quicksort)。


如果你想学习数据结构和算法,却苦于没有简单易学的教程,那么我给你推荐下面这个课程:

AI前奏必备-数据结构与算法课 - 老九学堂

(此课程中还有Cocos2dx和前端入门课赠送。)


作者:ChungZH

审稿:未央