介绍

鸽巢排序（Pigeonhole sort），也被称作基数分类，是一种时间复杂度为 ${\displaystyle O(n)}$ 且在不可避免遍历每一个元素并且排序的情况下效率最好的一种排序算法。但它只有在差值（或者可被映射在差值）很小的范围内的数值排序的情况下实用.

当涉及到多个不相等的元素，且将这些元素放在同一个 “鸽巢” 的时候，算法的效率会有所降低。为了简便和保持鸽巢排序在适应不同的情况，比如两个在同一个存储桶中结束的元素必然相等

我们一般很少使用鸽巢排序，因为它很少可以在灵活性，简便性，尤是速度上超过其他排序算法。事实上，桶排序较鸽巢排序更加的实用。

实现

JavaScript

/*
https://en.wikipedia.org/wiki/Pigeonhole_sort
*Pigeonhole sorting is a sorting algorithm that is suitable
* for sorting lists of elements where the number of elements
* (n) and the length of the range of possible key values (N)
* are approximately the same.
 */
function pigeonHoleSort (arr) {
  let min = arr[0]
  let max = arr[0]

  for (let i = 0; i < arr.length; i++) {
    if (arr[i] > max) { max = arr[i] }
    if (arr[i] < min) { min = arr[i] }
  }

  const range = max - min + 1
  const pigeonhole = Array(range).fill(0)

  for (let i = 0; i < arr.length; i++) {
    pigeonhole[arr[i] - min]++
  }

  let index = 0

  for (let j = 0; j < range; j++) {
    while (pigeonhole[j]-- > 0) {
      arr[index++] = j + min
    }
  }
  return arr
}

参考

• 鸽巢排序 - 维基百科，自由的百科全书 (opens new window)