为什么没有一个桶排序库(或者有？)

Question

我一直在学习算法，我只是偶然发现了这类问题。虽然它只能在少数情况下使用，但它看起来太高效了，不能在标准库中实现，因为它可以在O(n)时间内对列表进行排序。所以我的问题是，为什么在大多数语言中没有支持桶排序的给定库，或者其他类似计数排序的算法，比如基排序？我已经检查了java、python和c++库，但是它似乎不支持任何排序算法，除了基于比较的排序算法。

虽然实现这样的算法需要列表在特定的范围内有整数，但实现这种方法似乎并不是不可能的。例如，Java可以有一个类似比较器()的接口，该接口返回给定范围内的整数，用作排序的索引。那么，为什么没有使用O(n)排序算法呢？或者说，是否有一个库实际上使用了我刚刚错过的桶类？对不起，如果这是一个愚蠢的问题，我只是认为一定有一个原因，使O(n)算法未使用。

Answer 1

Java有一个静态方法Arrays.sort，原则上它可以作为接受整数类型(https://docs.oracle.com/javase/10/docs/api/java/util/Arrays.html#sort(int[]) )的重载的基排序来实现。他们选择用快速排序实现。没有给出任何理由，但我想1。基排序需要额外的内存，而快速排序不需要2。n log n和n之间的区别由于快速排序具有良好的缓存局部性这一事实而变得模糊，而基排序则不是这样。

Answer 2

Java

Arrays.sort(byte[])、Arrays.sort(short[])和Arrays.sort(char[])

至少从Java 7开始，可以使用带有计数排序的就地O(n) time和O(1) space复杂性来实现：

static void sort(short[] a, int low, int high) {
  if (high - low > MIN_SHORT_OR_CHAR_COUNTING_SORT_SIZE) {
    countingSort(a, low, high);
  } else {
    sort(a, 0, low, high);
  }
}

private static void countingSort(short[] a, int low, int high) {
  int[] count = new int[NUM_SHORT_VALUES];

  /*
   * Compute a histogram with the number of each values.
   */
  for (int i = high; i > low; ++count[a[--i] & 0xFFFF]);

  /*
   * Place values on their final positions.
   */
  if (high - low > NUM_SHORT_VALUES) {
    for (int i = MAX_SHORT_INDEX; --i > Short.MAX_VALUE; ) {
      int value = i & 0xFFFF;

      for (low = high - count[value]; high > low;
           a[--high] = (short) value
      );
    }
  } else {
    for (int i = MAX_SHORT_INDEX; high > low; ) {
      while (count[--i & 0xFFFF] == 0);

      int value = i & 0xFFFF;
      int c = count[value];

      do {
        a[--high] = (short) value;
      } while (--c > 0);
    }
  }
}

计数排序实现

Arrays.sort(int[])、Arrays.sort(long[])、Arrays.sort(float[])和Arrays.sort(double[])

有一个票证JDK-8266431和相关的拉请求https://github.com/openjdk/jdk/pull/3938打算切换到大型数组的基排序。

基数排序效率

无论在理论上还是在实践中，基类都比快速排序或其他基于比较的排序算法更快。有多个基准证明了这一点：

​

​

https://erik.gorset.no/2011/04/radix-sort-is-faster-than-quicksort.html https://probablydance.com/2016/12/02/investigating-radix-sort/

Answer 3

绝对是个疏忽。JgrahT有一个实现，但只适用于Integer。如果您想从任何用户定义的类中对对象数组进行排序，则需要一次只遍历一次键。因此，类必须提供像getIthKeyBit()这样的方法。奇怪的是这被忽视了。