基本思想:类似于哈希表的拉链法,定义一个映射函数,将值放入对应的桶中。

C#算法实现:

/// <summary>
        /// 桶排序
        /// 类似于哈希表的拉链法,定义一个映射函数,将值放入对应的桶中
        /// 最坏时间情况:全部分到一个桶中O(N^2),一般情况为O(NlogN)
        /// 最好时间情况:每个桶中只有一个数据时最优O(N)
        /// int bucketNum = arr.Length;
        /// 映射函数:int bucketIndex = arr[i] * bucketNum / (max + 1);
        /// </summary>
        /// <param name="arr"></param>
        /// <param name="max">数组的最大值</param>
        /// <returns></returns>
        private static int[] BucketSort(int[] arr, int max, int min)
        {
            int bucketNum = arr.Length;

            // 初始化桶  
            LinkedList<int>[] bucket = new LinkedList<int>[arr.Length];
            for (int i = 0; i < bucketNum; i++)
            {
                bucket[i] = new LinkedList<int>();
            }
            // 元素分装各个桶中  
            for (int i = 0; i < bucketNum; i++)
            {
                //映射函数
                int bucketIndex = arr[i] * bucketNum / (max + 1);
                InsertIntoLinkList(bucket[bucketIndex], arr[i]);
            }
            // 从各个桶中获取后排序插入  
            int index = 0;
            for (int i = 0; i < bucketNum; i++)
            {
                foreach (var item in bucket[i])
                {
                    arr[index++] = item;
                }
            }
            return arr;
        }

        /// <summary>  
        /// 按升序插入 linklist   
        /// </summary>  
        /// <param name="linkedList"> 要排序的链表 </param>  
        /// <param name="num"> 要插入排序的数字 </param>  
        private static void InsertIntoLinkList(LinkedList<int> linkedList, int num)
        {
            // 链表为空时,插入到第一位  
            if (linkedList.Count == 0)
            {
                linkedList.AddFirst(num);
                return;
            }
            else
            {
                foreach (int i in linkedList)
                {
                    if (i > num)
                    {
                        System.Collections.Generic.LinkedListNode<int> node = linkedList.Find(i);
                        linkedList.AddBefore(node, num);
                        return;
                    }
                }
                linkedList.AddLast(num);
            }
        }