桶排序

1、实现原理

之前所有的排序都是基于比较的方法，时间复杂度最低限制在O(n*logn)。
但是桶排序不是基于比较的排序，其排序与数的个数无关。
但是也存在瓶颈，就是数据本身特性（位数和范围）
原理：（类似于计数排序）
1、需要额外的空间辅助，创建一个数组中最大值+1的bucket容器
2、bucket放置原数组中相应值的统计个数
3、遍历bucket，将bucket每个位置上的数填回原数组

2、代码
时间复杂度：O（n）
额外空间复杂度：O(n)
稳定

#include<bits/stdc++.h>
using namespace std;

void BucketSort(int a[],int n)
{
    int maxn = 0;
    for(int i = 0; i < n; ++i){
        maxn = max(a[i],maxn);
    }

    int bucket[maxn+1] = {0};

    for(int i = 0; i < n; ++i)
    {
        bucket[a[i]]++;
    }

    int i = 0;
    for(int j = 0; j < maxn+1; ++j)
    {
        while(bucket[j]-- > 0)
        {
            a[i++] = j;
        }
    }
}

int main(){

    int a[5] = {0,9,5,8,3};
    BucketSort(a,5);
    printf("%d",a[0]);
	for(int i = 1; i < 5; i++)
	{
		printf(" %d",a[i]);
	}
    return 0;
}