排序算法——桶排序

• 把数据放进若干个桶，然后在桶里用其他排序，近乎分治思想。从数值的低位到高位依次排序，有几位就排序几次。例如二位数就排两次，三位数就排三次，依次按照个十百...的顺序来排序。

第一次排序：50 ????????12 ????????43 ????????23 ????????33???????? 15???????? 66 ????????98???????? 18???????? 89

第二次排序：12 ????????15 ????????18 ????????23 ????????33 ????????43 ????????50???????? 66 ????????89 ????????98

代码：

//桶排序
void bucket_sort(int* a, int len){	
	int n = 1;
	int idx;
	int k;
	int* pTemp = NULL;
	while (n<AREA){//循环 log10AREA 次
		//1 做桶  并初始化桶
		pTemp = malloc(10 * len *sizeof(int));
#if 0
		for (int i = 0; i < 10; i++){
			for (int j = 0; j < len; j++){
				pTemp[i*len + j] = -1;
			}
		}
#else
		for (int i = 0; i < 10*len; i++){
			pTemp[i] = -1;
		}
#endif
		//2 根据特性(对应位作为桶的编号)放入桶中
		for (int i = 0; i < len; i++){
			//a[i]
			idx = a[i] / n % 10;//获取到数据这一轮要看的位上的数据

			pTemp[ idx*len + i] = a[i];
		}
		//3 从桶中取出，覆盖a数组
		k = 0;
		for (int i = 0; i < 10 * len; i++){
			if (pTemp[i] != -1)
				a[k++] = pTemp[i];
		}
		//4 销毁桶
		free(pTemp);
		pTemp = NULL;
		n *= 10;
	}
}