桶排序是將待排序集合中處于同一個值域的元素存入同一個桶中，也就是根據元素值特性將集合拆分為多個區域，則拆分后形成的多個桶，從值域上看是處于有序狀態的。對每個桶中元素進行排序，則所有桶中元素構成的集合是已排序的。

為了使桶排序更加高效，我們需要做到這兩點：

1. 在額外空間充足的情況下，盡量增大桶的數量
2. 使用的映射函數能夠將輸入的 N 個數據均勻的分配到 K 個桶中

同時，對于桶中元素的排序，選擇何種比較排序算法對于性能的影響至關重要。 1. 什么時候最快 當輸入的數據可以均勻的分配到每一個桶中。 2. 什么時候最慢 當輸入的數據被分配到了同一個桶中。 3. 示意圖 元素分布在桶中： 然后，元素在每個桶中排序：

代碼實現

JavaScript

實例

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

   var i;
   var minValue = arr[0];
   var maxValue = arr[0];
   for (i = 1; i if (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 for (i = 0; i for (i = 0; i for (var j = 0; j return arr;
}

Java

實例

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 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 for (int[] bucket : buckets) {
           if (bucket.length 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;
   }

}

PHP

實例

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

   $minValue = $arr[0];
   $maxValue = $arr[0];
   for ($i = 1; $i $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 $buckets); $i++) {
       $buckets[$i] = [];
   }

   for ($i = 0; $i $arr); $i++) {
       $buckets[floor(($arr[$i] - $minValue) / $bucketSize)][] = $arr[$i];
   }

   $arr = array();
   for ($i = 0; $i $buckets); $i++) {
       $bucketTmp = $buckets[$i];
       sort($bucketTmp);
       for ($j = 0; $j $bucketTmp); $j++) {
           $arr[] = $bucketTmp[$j];
       }
   }

   return $arr;
}

C++

實例

#include#include#includeusing 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->mDatamNext;
       }
       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 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;
       }
}