简化版桶排序

简化版桶排序笔记

问题说明：
班上有五个学生，他们分别考了5，3，5，2，8分，现在要将他们的分数进行从大到小的排序，即计算机随机读入五个数，然后将这五个数从小到大进行输出。

首先我们开辟一个长度为11的数组，首先将他们全部初始化为零，a[0] = 0就表示还没有人得零分，a[10] = 0就表示还没有人得十分。

下面开始处理每个人的分数，第一个人得分是5分，所以数组元素a[5]加一，这就表示5分出现过一次，第二个人的分数是3分，则a[3]加一，以此类推。

所以我们会发现，数组的标号其实就是分数，而且已经排好序了，而数组的元素表示这个分数出现了多少次，接下来打印即可

#include<iostream>
using namespace std;

int main(void)
{
	//数组的值表示出现几次  数组标号表示多少分 
	int a[11],t;
	
	for(int i = 0; i <= 10; i++)
	{
		a[i] = 0;//先将他们初始化 
	} 
	
	for(int i = 0; i < 5; i++)//依次读入五个数 
	{
		scanf("%d",&t);
		a[t]++;//进行计数 对应标号 
	}
	
	for(int i = 10; i >= 0; i--)
	{
		for(int j = 1; j <= a[i]; j++)//出现几次就打印几次 
		{
			cout<<i<<" ";
		} 
	} 
    return 0;
}

时间复杂度分析：前两个for循环，总共运算m+n次，后面一个双重for循环总共运算m+n次，时间复杂度为O(M+N)。

这个排序算法不是真正的桶排序算法