桶排序是一种效率很高的排序算法，它的时间复杂度为O(N+M)，(N个元素，范围为0--M)，但桶排序有一定的限制，必须为非负整数，而且元素不宜过大。

算法思想：

设待排序序列的元素取值范围为0到m，则我们新建一个大小为m+1的临时数组并把初始值都设为0，遍历待排序序列，把待排序序列中元素的值作为临时数组的下标，找出临时数组中对应该下标的元素使之+1；然后遍历临时数组，把临时数组中元素大于0的下标作为值按次序依次填入待排序数组，元素的值作为重复填入该下标的次数，遍历完成则排序结束序列有序。

1 void BucketSort(int intArray[], int Count_intArray, int max) 2 { 3     //待排序序列intArray的元素都是非负整数 4     //设待排序序列intArray的元素有Count_intArray个 5     //其取值范围为0到max，则我们新建一个大小为max+1的临时数组并把初始值都设为0 6     //此处是开辟max+1而不是max，因为比如给909,...0排序，是有1000个数，需要开辟999+1长度的数组 7     int *TmpArray = (int*)malloc(sizeof(int)*(max+1));//开辟一个新数组，这个数组即为桶； 8     for (int *p = TmpArray; p < TmpArray + max+1 ; p++) *p = 0;//初始化桶，是桶中的每个元素为0； 9     for (int *p = intArray; p < intArray + Count_intArray; p++) TmpArray[*p] += 1;///将TmpArray下标中等于intArray[i]的元素+110     int InsertIndex = 0;//指向intArray的指标11     for (int j=0; j < max + 1; j++)12     {13         for (int k = 1; k <= TmpArray[j]; k++)//需要插入的元素的个数必须>114             intArray[InsertIndex++] = j;15     }16     free(TmpArray);17 }

 

该例程输入待排序整形矩阵intArray，元素个数Count_intArray，以及元素最大值max（该max其实只要大于元素中最大的值就行）。

测试函数

1 #include
     
       2 #include
      
        3 int main() 4 { 5     void BucketSort(int intArray[], int Count_intArray,int max); 6     int intArray[10] = { 999,55,10,1,0,1,87,45,55,4 }; 7     int Count_intArray = 10; 8     int max = 999; 9     BucketSort(intArray, Count_intArray, max);10     for (int i = 0; i < 10; i++)11         printf("%d ", intArray[i]);12     printf("\n");13 }
      
     

结果：