十七、桶排序(Bucket Sort)

    先说下桶排序的原理，其实就是先构造一个空的数组，所有元素初始化为0。然后待排序数组进行遍历，把该元素的值在对应桶的数组的下标的位置的元素的值加一，就可以完成排序。

    对于桶排序的弊端很严重，比如我们待排序的数组有重复元素和负数那他的时间复杂度都为O(m+n),当数据足够多的时候我们的系统是承受不了的，但对于没有重复元素，也没有负数，那它的时间复杂度为O(n),这个时间是在我们接受的范围内。所以说，具体针对桶排序的应用请依据实际情况进行选择。

    本代码演示的是正负数以及重复的整数的排序

#include <stdio.h>

#define BucketSize 999 //设置桶的大小，这里接受最大的数为999-1

//对桶进行初始化
void InitBucket(int *bucketArray)
{
	for(int i = 0; i < BucketSize; i++)
	{
		bucketArray[i] = 0;
	}
} 

//桶式排序, 排序前数组， 数组长度
void buckSort(int *beforeArray, int len)
{
	int bucketArrayByPos[BucketSize]; //正数桶
	int bucketArrayByNeg[BucketSize]; //负数桶
	InitBucket(bucketArrayByPos);
	InitBucket(bucketArrayByNeg);
	int tmpByPos = beforeArray[0]; //正数最大值
	int tmpByNeg = beforeArray[0];	//负数最大值
	for(int i = 0; i < len; i++)
	{
		if(beforeArray[i] < 0)
		{
			bucketArrayByNeg[0-beforeArray[i]]++;
			if(tmpByNeg < (0-beforeArray[i]))
			{
				tmpByNeg = (0-beforeArray[i]);
			}
		}
		else
		{
			bucketArrayByPos[beforeArray[i]]++;
			if(tmpByPos < beforeArray[i])
			{
				tmpByPos = beforeArray[i];
			}
		}
	}
	int ptr = 0;
	for(int j = tmpByNeg; j >= 0; j--)
	{
		if(bucketArrayByNeg[j] == 1)
		{
			beforeArray[ptr] = (0-j);
			ptr++;
		}
		else if(bucketArrayByNeg[j] > 1)
		{
			for(int k = 0; k < bucketArrayByNeg[j]; k++)
			{
				beforeArray[ptr] = (0-j);
				ptr++;
			}
		}
	}
	for(int j = 0; j <= tmpByPos; j++)
	{
		if(bucketArrayByPos[j] == 1)
		{
			beforeArray[ptr] = j;
			ptr++;
		}
		else if(bucketArrayByPos[j] > 1)
		{
			for(int k = 0; k < bucketArrayByPos[j]; k++)
			{
				beforeArray[ptr] = j;
				ptr++;
			}
		}
	}
}

int main(void)
{
	int beforeArray[] = {55,33,11,22,-44,44,-1,-1,0,-0};
	int len = sizeof(beforeArray)/sizeof(beforeArray[0]);
	buckSort(beforeArray, len);
	for(int i = 0; i < len; i++)
	{
		printf("%d\t", beforeArray[i]);
	}
	printf("\n");
	return 0;
}