sort/桶排序.cpp

9. 桶排序

9.1 描述
桶排序利用了函数的映射关系.
设置一个定量的数组当作空桶；
遍历输入数据，并且把数据一个一个放到对应的桶里去；
对每个不是空的桶进行排序；
从不是空的桶里把排好序的数据拼接起来。 

9.2 复杂程度
时间复杂度O(n+k)                 空间复杂度O(n+k)
9.3 代码
#include<stdio.h>
#define Max_len 14     //数组元素个数
 
void Show(int  arr[], int n)
{
    int i;
    for ( i=0; i<n; i++ )
        printf("%d  ", 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] = { 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 }; //排序前数组序列
    Show( arr_test, Max_len );//排序
    BucketSort( arr_test,  Max_len);//排序后数组序列
    Show( arr_test, Max_len ); 
     return 0;
}

9.4 运行时间
0.007088s