C 语言 简单桶排序 算法&实现

C 语言 简单桶排序 算法&实现

输入n个0~m的数据，对他们进行从小到大的排序

算法思想：

      这里我们需要m+1个桶， 用来表示0~m之间每一个数出现的次数，这里的每一个桶的作用就是用来标记每一个数出现的次数

        例如，对于数字序列：5, 4, 1, 5 ,4,2,3; 这些数字中最大的为5。

        我们就要准备0～5也就是6个桶，换句话说就是创建一个容量为6的数组，

        

桶排序

桶(数组)	0	1	2	3	4	5
出现的次数	0次	1次	1次	1次	2次	2次

然后直接每一个桶中有几个数，就输出几次桶的下标(数组的索引)就可以了。

看到一个图，借来一用

时间复杂度为O(M+N), 这是一个非常快的排序算法，但是当数据范围较大时候，存储空间浪费较严重

~~~~算法结束

#include <iostream>

using namespace std;

int main(void)
{
	int a[100] = {0}, b[11] = {0};//b为桶，存储每一个数字出现的次数，初始化为0
	int n;
	cin >>n;//要排序的个数
	
	for(int i=0; i<n; i++)
	{//输入数据
		cin >> a[i];
	}

	for(i=0; i<n; i++)
	{//计数
		b[a[i]]++;
	}

	for(i=0; i<=10; i++)
	{//0~10的数字
		for(int j=0; j<b[i]; j++)
		{//每个数字出现的次数
			cout << i << " ";
		}
	}

	cout << endl;

	system("pause");
	return 0;

}

程序运行结果