桶排序

2024年04月03日

柏拉文

越努力，越幸运

一、认识

---

桶排序也称为箱排序，英文称为 Bucket Sort。它是将数组划分到一定数量的有序的桶里，然后再对每个桶中的数据进行排序，最后再将各个桶里的数据有序的合并到一起。

特点：

• 稳定排序: 如果 a 原本在 b 的前面，且 a == b，排序之后 a 仍然在 b 的前面
• 非原地排序: 需要利用额外的数组来辅助排序。
• 排序方式: Out-place (占用额外内存)
• 时间复杂度: O(n+k) [n 代表数据规模及数据量大小 k 代表桶的个数]
• 空间复杂度: O(n+k) [n 代表数据规模及数据量大小 k 代表桶的个数]

扩展:

• 排序算法的稳定性:

假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i] = r[j]，且 r[i] 在 r[j] 之前，而在排序后的序列中，r[i] 仍在 r[j] 之前，则称这种排序算法是稳定的；否则称为不稳定的。

那么排序算法的稳定性有什么意义呢？其实它只在一种情况下有意义：当要排序的内容是一个对象的多个属性，且其原本的顺序存在意义时，如果我们需要在二次排序后保持原有排序的意义，就需要使用到稳定性的算法。

二、思想

---

1. 将区间划分为 n 个相同大小的子区间，每个子区间称为一个桶
2. 遍历数组，按照一定的规则 (不同的类型，规则不同) ，将每个数字装入桶中
3. 对每个桶内的数字单独排序，这里需要采用其他排序算法，如插入、归并、快排等
4. 最后按照顺序将所有桶内的数字合并起来

三、实现

---

function quickSort(nums){
  const sort=(nums,start,end)=>{
    if(start>=end){
      return 
    }
    let left=start;
    let right=end;
    let pivot=nums[Math.floor((left+right)/2)];
    while(left<=right){
      while(nums[left]<pivot){
        left++;
      }
      while(nums[right]>pivot){
        right--;
      }
      if(left<=right){
        [nums[left],nums[right]]=[nums[right],nums[left]];
        left++;
        right--;
      }
    }
    sort(nums,start,right);
    sort(nums,left,end);
  }
  sort(nums,0,nums.length-1);
}
function sortArray(nums){
  if(nums.length<=1){
    return nums
  }
  let max=nums[0];
  let min=nums[0];
  for(let item of nums){
    if(item>max){
      max=item;
    }
    if(item<min){
      min=item;
    }
  }
  const range=max-min;
  const bucketAmount=10;
  const gap=range*1.0/(bucketAmount-1);
  let buckets=new Array(bucketAmount).fill(0).map(value=>new Array());
  for(let item of nums){
    let index=parseInt((item-min)/gap);
    buckets[index].push(item);
  }
  let index=0;
  for(let i=0;i<bucketAmount;i++){
    if(buckets[i].length){
      quickSort(buckets[i]);
      for(let j=0;j<buckets[i].length;j++){
        nums[index++]=buckets[i][j];
      }
    }
  }
  return nums
}