排序算法10 - 桶排序

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）。

算法描述

  1. 设置一个定量的数组当作空桶；

  2. 遍历输入数据，并且把数据一个一个放到对应的桶里去；

  3. 对每个不是空的桶进行排序；

  4. 从不是空的桶里把排好序的数据拼接起来。

对于整型数据可以使用以下方法实现

桶排序的思想就是把待排序的数尽量均匀地放到各个桶中，再对各个桶进行局部的排序，最后再按序将各个桶中的数输出，即可得到排好序的数。

  1. 首先确定桶的个数。因为桶排序最好是将数据均匀地分散在各个桶中，那么桶的个数最好是应该根据数据的分散情况来确定。首先找出所有数据中的最大值max和最小值min；

    根据max和min确定每个桶所装的数据的范围 size，有size = (max - min) / n + 1，n为数据的个数，需要保证至少有一个桶，故而需要加个1；

    求得了size即知道了每个桶所装数据的范围，还需要计算出所需的桶的个数count，有count = (max - min) / size + 1，需要保证每个桶至少要能装1个数，故而需要加个1；

  2. 求得了size和count后，即可知第一个桶装的数据范围为 [min, min + size)，第二个桶为 [min + size, min + 2 * size)，...，以此类推

    因此步骤2中需要再扫描一遍数组，将待排序的各个数放进对应的桶中。

  3. 对各个桶中的数据进行排序，可以使用其他的排序算法排序，例如快速排序；也可以递归使用桶排序进行排序；

  4. 将各个桶中排好序的数据依次输出，最后得到的数据即为最终有序。

  代码：

#include <stdio.h>
#include <stdlib.h>

// 定义桶的结构
typedef struct
{
      int count;
      int *values;
} Bucket;


void InsertSort(Bucket arr[],  int n)
{
	int i, j;
	int temp;

	for( i=1; i<n; i++ )
	{
		if( arr->values[i-1]>arr->values[i] )
		{
			temp = arr->values[i];
			for( j=i-1; arr->values[j]>temp; j--)
			{
				arr->values[j+1] = arr->values[j];
			}

			arr->values[j+1] = temp;
		}
	}
}

void BucketSort(int arr[], int n)
{
	int i, j, idx, bucketSize, bucketCount;
	int max = arr[0];
	int min = arr[0];	
	Bucket *buckets, *bucket;

	// 遍历找出最大值和最小值
	for (i=0; i<n; i++)
	{
		if (arr[i]>max)
		{
			max = arr[i];
		}
 
		if (arr[i]<min)
		{
			min = arr[i];
		}
	}

	// 创建桶数组
	bucketSize = (max - min)/n + 1; // 每个桶所装数据的范围
	bucketCount = (max - min)/bucketSize + 1; // 桶的数量	
	buckets = (Bucket*)calloc(bucketCount, sizeof(Bucket)); 
	if (buckets==NULL) 
	{
		perror("calloc");
		return;
	}

	// 初始化桶
	for (i=0; i<bucketCount; i++)
	{
		buckets[i].count = 0;
		buckets[i].values = NULL;
	}

	// 将元素放入桶中
	for (i=0; i<n; i++)
	{
		idx = (int)(arr[i] / bucketCount);
		bucket = &buckets[idx];

		// 扩展桶的容量
		bucket->values = realloc(bucket->values, (bucket->count + 1) * sizeof(int));
		bucket->values[bucket->count] = arr[i];
		bucket->count++;
	}

	// 对每个桶中的元素进行排序
	for (i=0; i<bucketCount; i++)
	{
		bucket = &buckets[i];
		bucketSize = bucket->count;

		// 使用简单的插入排序对桶中的元素进行排序
		InsertSort(bucket, bucketSize);
	}

	// 合并桶中的元素到原始数组
	idx = 0;
	for (i=0; i<bucketCount; i++)
	{
		bucket = &buckets[i];
		bucketSize = bucket->count;
		if (bucketSize==0)
		{
			continue;
		}

		for (j=0; j<bucketSize; j++)
		{
			arr[idx] = bucket->values[j];
			idx++;
		}
		free(bucket->values);
	}

	// 释放动态开辟的空间
	free(buckets);
	buckets = NULL;
}
 
int main(void)
{ 
	int i;
	int arr[10] = {5, 2, 6, 0, 3, 9, 1, 7, 4, 8};
	int arrLen = sizeof(arr)/sizeof(int);

    BucketSort(arr, arrLen);
 
    printf("排序后的结果是：");
    for(i=0; i<arrLen; i++)
    {
        printf("%d", arr[i]);
        if(i!=arrLen-1)
        {
            printf(", ");
        }
    }
    printf("\n");
    return 0;
}