什么是桶排序？

为了使桶排序更加高效，我们需要做到这两点：

1. 在额外空间充足的情况下，尽量增大桶的数量
2. 使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中

同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。
1. 什么时候最快
当输入的数据可以均匀的分配到每一个桶中。
2. 什么时候最慢
当输入的数据被分配到了同一个桶中。
3. 示意图
元素分布在桶中：

然后，元素在每个桶中排序：

实例

function bucketSort(arr, bucketSize) {
    if (arr.length === 0) {
      return arr;
    }

    var i;
    var minValue = arr[0];
    var maxValue = arr[0];
    for (i = 1; i < arr.length;="" i++)="" {="" if="" (arr[i]="">< minvalue)="" {="" minvalue="arr[i];" 输入数据的最小值="" }="" else="" if="" (arr[i]=""> maxValue) {
          maxValue = arr[i];                // 输入数据的最大值
      }
    }

    //桶的初始化
    var DEFAULT_BUCKET_SIZE = 5;            // 设置桶的默认数量为5
    bucketSize = bucketSize || DEFAULT_BUCKET_SIZE;
    var bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;  
    var buckets = new Array(bucketCount);
    for (i = 0; i < buckets.length;="" i++)="" {="" buckets[i]="[];" }="" 利用映射函数将数据分配到各个桶中="" for="" (i="0;" i="">< arr.length;="" i++)="" {="" buckets[math.floor((arr[i]="" -="" minvalue)="" bucketsize)].push(arr[i]);="" }="" arr.length="0;" for="" (i="0;" i="">< buckets.length;="" i++)="" {="" insertionsort(buckets[i]);="" 对每个桶进行排序，这里使用了插入排序="" for="" (var="" j="0;" j="">< buckets[i].length;="" j++)="" {="" arr.push(buckets[i][j]);="" }="" }="" return="" arr;="">

实例

public class BucketSort implements IArraySort {

    private static final InsertSort insertSort = new InsertSort();

    @Override
    public int[] sort(int[] sourceArray) throws Exception {
        // 对 arr 进行拷贝，不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        return bucketSort(arr, 5);
    }

    private int[] bucketSort(int[] arr, int bucketSize) throws Exception {
        if (arr.length == 0) {
            return arr;
        }

        int minValue = arr[0];
        int maxValue = arr[0];
        for (int value : arr) {
            if (value < minvalue)="" {="" minvalue="value;" }="" else="" if="" (value=""> maxValue) {
                maxValue = value;
            }
        }

        int bucketCount = (int) Math.floor((maxValue - minValue) / bucketSize) + 1;
        int[][] buckets = new int[bucketCount][0];

        // 利用映射函数将数据分配到各个桶中
        for (int i = 0; i < arr.length;="" i++)="" {="" int="" index="(int)" math.floor((arr[i]="" -="" minvalue)="" bucketsize);="" buckets[index]="arrAppend(buckets[index]," arr[i]);="" }="" int="" arrindex="0;" for="" (int[]="" bucket="" :="" buckets)="" {="" if="" (bucket.length=""><= 0)="" {="" continue;="" }="" 对每个桶进行排序，这里使用了插入排序="" bucket="insertSort.sort(bucket);" for="" (int="" value="" :="" bucket)="" {="" arr[arrindex++]="value;" }="" }="" return="" arr;="" }="" *="" *="" 自动扩容，并保存数据="" *="" *="" @param="" arr="" *="" @param="" value="" */="" private="" int[]="" arrappend(int[]="" arr,="" int="" value)="" {="" arr="Arrays.copyOf(arr," arr.length="" +="" 1);="" arr[arr.length="" -="" 1]="value;" return="" arr;="" }="">

实例

function bucketSort($arr, $bucketSize = 5)
{
    if (count($arr) === 0) {
      return $arr;
    }

    $minValue = $arr[0];
    $maxValue = $arr[0];
    for ($i = 1; $i < count($arr);="" $i++)="" {="" if="" ($arr[$i]="">< $minvalue)="" {="" $minvalue="$arr[$i];" }="" else="" if="" ($arr[$i]=""> $maxValue) {
          $maxValue = $arr[$i];
      }
    }

    $bucketCount = floor(($maxValue - $minValue) / $bucketSize) + 1;
    $buckets = array();
    for ($i = 0; $i < count($buckets);="" $i++)="" {="" $buckets[$i]="[];" }="" for="" ($i="0;" $i="">< count($arr);="" $i++)="" {="" $buckets[floor(($arr[$i]="" -="" $minvalue)="" $bucketsize)][]="$arr[$i];" }="" $arr="array();" for="" ($i="0;" $i="">< count($buckets);="" $i++)="" {="" $buckettmp="$buckets[$i];" sort($buckettmp);="" for="" ($j="0;" $j="">< count($buckettmp);="" $j++)="" {="" $arr[]="$bucketTmp[$j];" }="" }="" return="" $arr;="">

实例

#include
#include
#include
using namespace std;
const int BUCKET_NUM = 10;

struct ListNode{
        explicit ListNode(int i=0):mData(i),mNext(NULL){}
        ListNode* mNext;
        int mData;
};

ListNode* insert(ListNode* head,int val){
        ListNode dummyNode;
        ListNode *newNode = new ListNode(val);
        ListNode *pre,*curr;
        dummyNode.mNext = head;
        pre = &dummyNode;
        curr = head;
        while(NULL!=curr && curr->mData<=val){ pre="curr;" curr="curr-">mNext;
        }
        newNode->mNext = curr;
        pre->mNext = newNode;
        return dummyNode.mNext;
}


ListNode* Merge(ListNode *head1,ListNode *head2){
        ListNode dummyNode;
        ListNode *dummy = &dummyNode;
        while(NULL!=head1 && NULL!=head2){
                if(head1->mData <= head2-="">mData){
                        dummy->mNext = head1;
                        head1 = head1->mNext;
                }else{
                        dummy->mNext = head2;
                        head2 = head2->mNext;
                }
                dummy = dummy->mNext;
        }
        if(NULL!=head1) dummy->mNext = head1;
        if(NULL!=head2) dummy->mNext = head2;
       
        return dummyNode.mNext;
}

void BucketSort(int n,int arr[]){
        vector buckets(BUCKET_NUM,(ListNode*)(0));
        for(int i=0;imData;
                head = head->mNext;
        }
}