桶排序

定义

桶排序（Bucket sort）或所谓的箱排序，是一个排序算法，工作的原理是将数组分到有限数量的桶里。每个桶再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序，本文使用的是插入排序）。桶排序是鸽巢排序的一种归纳结果。当要被排序的数组内的数值是均匀分配的时候，桶排序使用线性时间 O(n)。

排序实例

• 在此说明一下，在创建桶的时候，桶和桶之间的数值间距不是一定要定义为 1，可以定义为任意数值，要适情况而定，比如当知道要排序的数值在 0 -100 之间，就可以定义 10 个桶，桶与桶间的距离为 10。
• 桶排序适用在知道要排序数值的范围的情况下，若不知道范围，最好不要适用该算法。
• 桶排序是典型的以空间换时间的排序算法
• 在使用桶排序的时候，有一个小技巧，比如定义每个桶的容量为 10，每个桶中的第一个数据要定义为该桶中已经存入的数据的个数，也就是每个桶的实际容量为 9，这样做的好处是可以直接知道该桶中下一个将要存入的数据的位置

代码实现

namespace SuanFa.Sequence
{
    class BucketSort
    {static void Main()
        {
            //create an object
            BucketSort bs = new BucketSort();
            bs.bucketSort();}
        public void bucketSort()
        {
            //define ordered sequence
            int[] array = { 21, 8, 6, 11, 36, 50, 27,42,30,12};
            //define buckets,ten buckets ,the size of the bucket is ten
            int[,] bucket = new int[10,10];
            //initialize buckets
            for(int i=0;i<bucket.GetLength(0);i++)
            {for(int j=0;j<bucket.GetLength(1);j++)
                {bucket[i, j] = 0;
                }
            }
            //sort
            for(int i=0;i<array.Length;i++)
            {int index = getIndex(array[i]);
                insertSort(bucket,array[i],index);
            }
            //put the ordered sequence to array
            int t = 0;
            for (int i = 0; i < bucket.GetLength(0); i++)
            {for (int j = 0; j < bucket.GetLength(1); j++)
                {if(bucket[i,j]!=0&&j!=0)
                    {array[t] = bucket[i,j];
                        t++;
                    }
                }
            }
            //print ordered array
            print(array);
        }
        //insert sort
        public void insertSort(int[,] array,int k,int index)
        {
            //the position of the new element
            int i = array[index,0] + 1;
            while (i>0&&k<array[index,i])
            {
                //move the bigger element  back
                array[index,i + 1] = array[index,i];
                i--;
            }
            //save new element
            array[index,i + 1] = k;
            array[index, 0]++;
        }
        //the index of the bucket
        public int getIndex(int i)
        {return i / 10 % 10;}
        /// <summary>
        /// print
        /// </summary>
        /// <param name="nums">the array which will printed</param>
        public void print(int[] nums)
        {for (int i = 0; i < nums.Length; i++)
            {Console.WriteLine("i=" + nums[i] + " ");
            }
            Console.WriteLine();}
    }
}

时间复杂度

桶排序速度很快，但同时多占用了大量内存，该算法的时间复杂度为 O(n)

稳定性

本文在实现排序算法时，使用的是桶排序 + 直接插入排序算法，所以稳定性较高。

参考资料

• https://zh.wikipedia.org/wiki…
• http://www.cnblogs.com/skywan…