桶排序以下列程序进行：
#include <stdio.h>
#include <stdlib.h>
#define m 15 // 数组array中的数组元素的数值必须比m小，不能等于m
void bucketsort( int *a, int n ) //n是 数组长度
{
int buckets [m]; // An array of m counters, or buckets 共 m 个buckets, 下标从0...m-1
for ( int j = 0; j < m; ++j ) // 将各个bucket初始化为0
buckets[j] = 0;
for ( int i = 0; i < n; ++i ) //the buckets are used to keep a count of the number of occurrences of each value between 0 and m-1
++buckets[a[i]]; // ++buckets[i] 就是给buckets[i]的数值加1
for ( int i = 0, j = 0; j < m; ++j ) // 依次遍历各个buckets
for ( int k = buckets[j]; k > 0; --k ) // k > 0保证buckets[j]非空，k是buckets[j]中的计数器,将buckets[j]中的所有数依次输出到a[]中
a[i++] = j; // 注意buckets[j]中的下标j就是数组元素a[i]
}
int main()
{
int i;
int len;
int array[] = {8, 9, 1, 2, 3, 5, 4, 6, 7, 11, 10, 14};
len = sizeof( array ) / sizeof( *array );
printf( "排序前数组序列：\n" );
for ( i = 0;i < len;i++ )
{
printf( "%5d", array[i] );
}
bucketsort( array, len );
printf( "\n排序后数组序列：\n" );
for ( i = 0;i < len;i++ )
{
printf( "%5d", array[i] );
}
getchar();
}
At first, we define the value of m, which means that all the elements we will introduce for the array will have to be lower than m. Next, we make buckets for the size of m, and we make them null and in the end, we add the elements to the proper buckets.
If you know the range of the elements, the bucket sort is quite good.
The time complexity of bucket sort is: O(n + m) where: m is the range input values, n is the total number of values in the array. Bucket sort beats all other sorting routines in time complexity. It should only be used when the range of input values is small compared with the number of values. In other words, occasions when there are a lot of repeated values in the input. Bucket sort works by counting the number of instances of each input value throughout the array. It then reconstructs the array from this auxiliary data. This implementation has a configurable input range, and will use the least amount of memory possible.
评论