【Day28】[演算法]-桶排序法Bucket Sort

桶排序法(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]