简化版桶排序

1.简化版桶排序

                                          ——本文是个人学习《啊哈算法》的笔记，内容出自《啊哈算法》

例： 让计算机随机读入 5个数然后将这 5个数从大到小输出
输入：5 3 5 2 8
输出：8 5 5 3 2
思路：
先申请一个大小为 11 的数组 int a[11]；现在你已经有了 11 个变量，编号从 a[0]~a[10]。
刚开始，我们将 a[0]~a[10]都初始化为 0，表示这些0~10的数字还没出现过。例如:a[0]= 0就表示目前0数字出现0次， a[1]=0就表示目前1数字出现0次……a[10]等于 0就表示目前10数字出现0次 。
接下来，将出现过的数字打印出来，出现几次就打印几次：
a[0]为 0，表示“0”没有出现过，不打印；
a[1]为 0，表示“1”没有出现过，不打印；
a[2]为 1，表示“2”出现过 1次，打印 2；
a[3]为 1，表示“3”出现过 1次，打印 3；
a[4]为 0，表示“4”没有出现过，不打印；
a[5]为 2，表示“5”出现过 2次，打印 5 5；
a[6]为 0，表示“6”没有出现过，不打印；
a[7]为 0，表示“7”没有出现过，不打印；
a[8]为 1，表示“8”出现过 1次，打印 8；
a[9]为 0，表示“9”没有出现过，不打印；
a[10]为 0，表示“10”没有出现过，不打印；
输出“2 3 5 5 8”，完整的代码如下：

#include <stdio.h>
int main() {
	int a[11],i,j,t;
	for(i=0; i<=10; i++)
		a[i]=0;  //初始化为0
	for(i=1; i<=5; i++) { //循环读入5个数
		scanf("%d",&t);//把每一个数读到变量t中
		a[t]++;  //进行计数
	}
	for(i=0; i<=10; i++){ //依次判断a[0]~a[10]
		for(j=1; j<=a[i]; j++){ //出现了几次就打印几次
			printf("%d",i);
			}     //第二个for语句：如果可以执行，执行一次打印一次，j++，回头再判断j<=a[i]? 
			      // 直到不能执行跳出,执行 第一个for语句 
		}
	getchar();
	getchar();
	//这里的getchar();用来暂停程序，以便查看程序输出的内容
	//也可以用system("pause");等来代替
	return 0;
}
输出：8 5 5 3 2
```c
#include <stdio.h> 
int main() {    
 int book[1001],i,j,t,n;    
  for(i=0;i<=1000;i++)  book[i]=0;      
  scanf("%d",&n);//输入一个数n，表示接下来有n个数   
    for(i=1;i<=n;i++)//循环读入n个数，并进行桶排序    
     {    scanf("%d",&t);  //把每一个数读到变量t中     
         book[t]++;  //进行计数，对编号为t的桶放一个小旗子   
           }   
       for(i=1000;i>=0;i--)  //依次判断编号1000~0的桶      
        for(j=1;j<=book[i];j++)  //出现了几次就将桶的编号打印几次             
      printf("%d ",i); 
    getchar();getchar();     
    return 0; }

输入：10 （代表有十个数输入）
            8 100 50 22 15 6 1 1000 999 0
 输出：1000 999 100 50 22 15 8 6 1 0
 

```c
#include <stdio.h>
int main() {
	int book[1001],i,j,t,n;
	for(i=0; i<=1000; i++)book[i]=0;
	scanf("%d",&n);//输入一个数n，表示接下来有n个数 **//循环1001次**
	for(i=1; i<=n; i++) { //循环读入n个数，并进行桶排序
		scanf("%d",&t);  //把每一个数读到变量t中
		book[t]++;  //进行计数，对编号为t的桶放一个小旗子
	}				**//循环n次**
	for(i=1000; i>=0; i--) //依次判断编号1000~0的桶
		for(j=1; j<=book[i]; j++) //出现了几次就将桶的编号打印几次
			printf("%d ",i); **//循换(1001+n)次**
	getchar();
	getchar();
	return 0;
}					//整个排序循环2*（1001+n)次

时间复杂度：
``用大写字母 O来表示时间复杂度，因此该算法的时间复杂度是 O(2*(m+n))；*（m 是申请的数组大小，n是待排序的个数）
我们在说时间复杂度的时候可以忽略较小 的常数，故桶排序的时间复杂度为 O(m+n)。还有一点，在表示时间复杂度的时候，n和 m 通常用大写字母即 O(M+N)。