这篇文章简介一下 桶排序

桶排序简介

桶排序是一个非常快的排序算法,该算法的基本思想由 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. 输出“桶”数组。

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

桶排序实现

C++ 代码实现:

#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 0 8 3 2 5 4 9 0 9

输出:

0 0 1 2 3 4 5 8 9 9