[数据结构与算法]C语言：桶排序（BucketSort）

题目：

排序一组数字：9 5 9 2 8 9 2 1 0 1 0 5 4

这还不简单？一个冒泡排序，或者一个快速排序，结束！好的，一个时间复杂度是O（n^2），一个时间复杂度是O (nlogn)。对于平时的小打小闹，这两种方法绝对没有问题。但作为未来码农精英的我们肯定要追求完美啦！所以，我们用O（n）复杂度来排序他！

桶排序

桶排序是所有排序中最简单的排序之一，之所以他的复杂度能达到O（n），是因为他们都是非基于比较的排序算法，不涉与元素之间的比较操作。

对于上面的这道题目的步骤如下：

1. 遍历原数组，找出原数组的最大值。

2. 根据找出的最大值，建立一个最大下标与这个最大值相同的新数组（桶数组）。原数组的最大值 为9，那么桶数组的最大下标为9（a[0]~a[9]）,所以我们创建一个大小为10的桶数组。

3. 再次遍历原数组，每遍历一个元素，桶数组中下标与之相等的元素自增。

原数组：9 5 9 2 8 9 2 1 0 1 0 5 4

4. 遍历桶数组，按照每个元素大小一个一个打印出来。

但这样的桶排序有很大的缺陷：

1. 桶排序的算法不能够操作浮点值或者负数。（负数的情况我们可以用一个方法来避免：先将原数组中的每一个元素减去元素组中最小的负数，然后排完序后每一个元素再增加原来减去的负数就行了）。

2. 如果原数组的取值间隔过大，如原数组为2 3 4 5 6 7 90 91 92，那我们想要创建一个大小为93的数组，这样会引起不必要的空间浪费。

#include<stdio.h>
#include<stdlib.h>
#define Max_len 10      //数组元素个数
 
// 打印结果
void Show(int  arr[], int n)
{
    int i;
    for ( i=0; i<n; i++ ){
        printf("%d\t", arr[i]);
	}
    printf("\n");
}
 
//获得未排序数组中最大的一个元素值
int GetMaxVal(int* arr, int len)
{
    int maxVal = arr[0]; //假设最大为arr[0]
    for(int i = 1; i < len; i++)  //遍历比较，找到大的就赋值给maxVal
    {
        if(arr[i] > maxVal)
            maxVal = arr[i];
    }
    return maxVal;  //返回最大值
}
 
//桶排序   参数：数组及其长度
void BucketSort(int* arr , int len)
{
    int tmpArrLen = GetMaxVal(arr , len) + 1;
    int tmpArr[tmpArrLen];  //获得空桶大小
    int i, j;
    
    for( i = 0; i < tmpArrLen; i++)  //空桶初始化
        tmpArr[i] = 0;
    
    for(i = 0; i < len; i++)   //寻访序列，并且把项目一个一个放到对应的桶子去。
        tmpArr[ arr[i] ]++;
    
    for(i = 0, j = 0; i < tmpArrLen; i ++)
    {
        while( tmpArr[ i ] != 0) //对每个不是空的桶子进行排序。
        {
            arr[j ] = i;  //从不是空的桶子里把项目再放回原来的序列中。
            j++;
            tmpArr[i]--;
        }
    }
}
 
int main()
{   //测试数据
    int arr_test[Max_len] = { 8, 4, 2, 3, 5, 1, 6, 9, 0, 7 };
    //排序前数组序列
    Show( arr_test, Max_len );
    //排序
    BucketSort( arr_test,  Max_len);
    //排序后数组序列
    Show( arr_test, Max_len );
    return 0;
}