【转】桶排序(Bucket Sort)

转自： http://blog.csdn.net/weiwenhp/article/details/8618500

 

桶排序的思想和基数排序有点类似,都要借助临时空间.基数排序是先映射到大小为10的计数数组中,然后再映射到大小等于待排序数组长度的临时数组中.

而桶排序就是直接整个足够大的临时数组,把待排序的元素全部映射过来.其索引为待排序元素数值.所以为了确定临时数组的大小得先算出数组中最大数.

 

简单桶排序

简单桶排序的缺点很明显

1.不能有重复的元素.

2.元素不能为负数.

int GetMaxVal(int* arr, int len)
{
	int maxVal = arr[0];
	for (int i = 1; i < len; i++)
	{
		if (arr[i] > maxVal)
			maxVal = arr[i];
	}
	return maxVal;
}



void SimpleBucketSort(int* arr, int len)
{
	int tmpArrLen = GetMaxVal(arr, len) + 1;  //因为数组索引是从0开始,所以数组得是最大数加1
	int* tmpArr = new int[tmpArrLen];
	int i, j;
	for (i = 0; i < tmpArrLen; i++)
		tmpArr[i] = -1; //把临时数组的值全部赋予-1,如果赋予0的话待排序数组中有0值就不能排序了

	for (i = 0; i < len; i++)
		tmpArr[arr[i]]++;
	
	for (i = 0, j = 0; i < tmpArrLen; i++)
	{
		if (tmpArr[i] != -1)
		{
			arr[j] = tmpArr[i];
			j++;
		}
	}
}

 

 

对于第2点我们无能为力,但对于第一点可以改进下.

改进的桶排序

因为临时数组的索引就是待排序数组元素的值了,所以临时数组中可以不必再存储元素的值了.此时先把临时数组全部赋值为0,当有元素映射过来时就加1,有重复有元素就大于1

public static void BucketSort(int[] arr, int len, int max)
{
    int[] count = new int[max + 1];

    for (int i = 0; i < len; i++)
        count[arr[i]]++;

    for (int i = 0, j = 0; i < count.Length; i++)
    {
        while (count[i] != 0)
        {
            arr[j] = i;
            j++;
            count[i]--;
        }
    }  
}

 

 

评论

1 楼 北极的。鱼 2015-05-01  

另一种简单桶排序实现：

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication1
{
    public class Program
    {
        public static void Main(string[] args)
        {
            int[] nums = new int[9] { 2, 1, 9, 2, 7, 3, 1, 8, 2 };//初始化一个数组,其中有9个数，每个数都不大于10，这里假定是我们输入的数，需要从小到大排序
            int[] a = new int[11];//因为每个数都不大于10，所以初始化一个包含11个数的数组a
            int i, j, t;
            for (i = 0; i <= 10; i++) a[i] = 0;//给a数组赋值都为0

            for (i = 0; i < nums.Length; i++)
            {
                t = nums[i];//获取当前的数
                a[t]++;//进行计数
            }
            for (i = 0; i <= 10; i++)//依次判断a[0]~a[10]
                for (j = 1; j <=a[i]; j++)//出现了几次就输出几次
                    Console.Write("  " + i);
        }
    }
}

缺点：

1.不适用于小数

2.当数值过多，太浪费空间，比如数值范围为0~99999，那需申请100000个变量，也就是要写成a[1000000]。