python - 为什么没有桶排序库(或者有？)

Question

我一直在研究算法，刚刚遇到这种桶排序。虽然它只能用于少数情况，但它看起来太高效了，不能在标准库中实现，因为它可以在 O(n) 时间内对列表进行排序。所以我的问题是，为什么在大多数语言中没有支持桶排序或任何其他类似计数排序的算法(例如基数排序)的给定库？我检查了 java、python 和 c++ 库，但它看起来不支持除基于比较的排序算法之外的任何排序算法。
虽然实现这样的算法需要列表具有特定范围内的整数，但实现这样的方法似乎并非不可能。例如，Java 可以有一个类似于 Comparator() 的接口(interface)，它返回给定范围内的整数，用作排序的索引。那么是什么原因导致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 之间的区别由于快速排序具有良好的缓存位置这一事实而变得模糊，而基数排序则更少。