桶排序法(Bucket Sort)，與前面幾篇的排序法不一樣，前面都是經由兩兩互相比較而成的排序，稱為比較排序法，而桶排序是非比較排序，屬於「分配性」的排序。原理是先準備幾個桶子，每個桶子都是有限的固定區間，再將待排序的資料分配到對應區間的桶子中，接著每個桶再個別排序（可以使用別的排序演算法），最後再依序收集排序好的資料。
如果記憶體更大的話, 可以使用增加桶子的數量來降低區間，這樣將可以減少排序的次數，所以桶排序是一種可以用空間來換時間的排序法。

操作流程:

1. 設定定量的空桶子
2. 走訪原始資料並分配到對應桶子中
3. 對每個不是空的桶子進行排序
4. 依序從不是空的桶子中，把排序好資料收集回來

下面利用9 15 12 23 33 26 7 31 42 36由小到大排序

k = 桶子的數量
n = 資料數量
平均時間複雜度為: O(n+k)

JavaScript

function bucketSort(arr){
  let min = Math.min(...arr);
  let max = Math.max(...arr);
  let size = 5
  
  //產生空桶子
  let buckets = Array.from(
    { length: Math.floor((max - min) / size) + 1 },() => []);

	//依規則分類到各桶子
  arr.forEach(function(val){
   	buckets[Math.floor((val - min) / size)].push(val);
  });
     
  result=[];
  //各桶子裡資料排序
  for (i = 0; i < buckets.length; i++) { 
  	buckets[i].sort()//偷懶使用sort()，可以自行使用其他排序法
    //拉出合併
    for (var j = 0; j < buckets[i].length; j++) { 
      result.push(buckets[i][j]); 
    } 
  } 
	
  return result

};

let arr = [9, 15, 12, 23, 33, 26, 7, 31, 42, 36]

console.log(bucketSort(arr))
//[7, 9, 12, 15, 23, 26, 31, 33, 36, 42]

Python

#Bucket Sort
import math
 
def bucketSort(array):
    maxx = max(array)
    minn = min(array)
    size = 5
 
    buckets = [[] for i in range(math.floor((maxx-minn)/size+1))]

    for i in range(len(array)):
        val = int(array[i])
        buckets[math.floor((val-minn)/size)].append(val)
 
    result = []

    for i in range(len(buckets)):
        buckets[i] = sorted(buckets[i])

        for j in range(len(buckets[i])):
            result.append(buckets[i][j])
                
    return result
 
data = [9, 15, 12, 23, 33, 26, 7, 31, 42, 36]

print(bucketSort(data))
#[7, 9, 12, 15, 23, 26, 31, 33, 36, 42]