基交换排序实现？

Question

我需要一点帮助来理解基交换排序算法的实现。

基交换(我不知道它在基于英语的文献中是否确切的名称)与quicksort非常相似，但是使用了数字的二进制表示。

第一，我们在二进制表示中查找最高的数字，然后使用两个索引(从数组开始和结束时，如果给定数字为0，则增加第一个数字，如果给定数字为1时，则递增另一个索引)。然后我们交换两个数字，然后继续工作直到i=j(索引相等)。然后我们有两个独立的分区，并使用第二个最重要的数字对它们进行排序，等等.

我主要有几个问题：

1. 这个算法是真正称为基交换，还是它有其他更常用的名称？
2. 这种算法的优点是什么？这似乎是很多工作，但效果不太好？
3. 在哪里可以看到实现该算法的示例？也许它会更清楚它的真实是什么，因为它真的让我感到困惑。

Answer 1

听起来时间复杂度是O(n*k)，空间复杂度是O(k)，k是每个元素的位数。

在C++中

radixQsort(int* arrb, int* arre, int rad=INT_BITS){
    if(arrb==arre)return;

    int* arrm = std::partition(arrb,arre,[rad](a){return !(a&(1<<rad));});

    radixQsort(arrb,arrm,rad-1);
    radixQsort(arrm,arre,rad-1);
}

这是使用标准库中的隔断实现的，该库的工作方式类似于您描述的分区。

Answer 2

1. 与快速排序不同，基排序使用排序的值的“内部表示”。也就是说，它不只是简单地将它们与< >进行比较。当你对每一次排序传递采取几个比特，而不是一个，这是非常有效的。4位，也许是8位。因此，在后一种情况下，每次传递时，将数组划分为256个组。只有4张32位整数的通行证。

https://en.wikipedia.org/wiki/Radix_排序