基数排序最重要或最不重要，哪个更快？

Question

我一直在研究基数排序实现（到目前为止粘贴的代码如下）。代码是用 Java 编写的，但在 C/C++ 中应该也能正常工作。正如你从实现中看到的，我首先做的是最重要的位，整数的第 31 位。这似乎更快，因为一旦一个子组完成，它就不再需要迭代。

例如，打个比方，想象一下对单词进行排序，并且您只有一个以“A”开头的单词。一旦您看到 A 并将单词放在列表的开头，您就不再需要检查单词中的任何其他字符。另一方面，如果您从单词的末尾开始，您将不得不查看每个字母，然后才能确定它属于列表的开头。

所以，基于这个想法，我认为 MSB 订单会是最快的，但我错过了什么吗？由于某种原因，LSB 是否也一样快？我知道 LSB 执行“稳定排序”，但我认为这没有任何实际好处。

public static final int[] RadixSort_unsigned_1( int[] values1 ){ // one based key sorting
    int[] keys = new int[ values1.length ];
    int ctValues = values1[0];
    keys[0] = ctValues;
    for( int xKey = 1; xKey <= ctValues; xKey++ ) keys[xKey] = xKey;
    int iFrameListSize = (int)Math.sqrt( (double)ctValues ) + 2;
    int[] nextBottom = new int[ iFrameListSize ];
    int[] nextTop = new int[ iFrameListSize ];
    int ctFramesRemaining = 1;
    int ctFramesInNextRadix = 0;
    nextBottom[ 1 ] = 1; // the frame information is maintained in a circular queue
    nextTop[ 1 ] = ctValues;
    int xFrame = 1;
    int xFrameNextRadix = 2;
    int radix = 32;
    while( radix > 0 ){
        while( ctFramesRemaining > 0 ){ // go through all the frames and sort them
            int xLow = nextBottom[ xFrame ];
            int xHigh = nextTop[ xFrame ];
            while( true ){ // sort frame
                while( values1[ keys[ xLow ] ] == 0 ) xLow++;
                while( values1[ keys[ xHigh ] ] == 1 ) xHigh--;
                if( xLow > xHigh ) break;
                int iLowKey = keys[xLow]; // exchange high and low
                keys[xLow] = keys[xHigh];
                keys[xHigh] = iLowKey;
            }
            if( xHigh > nextBottom[ xFrame ] ){ // add a lower frame
                if( xLow < nextTop[ xFrame ] ){ // and also add an upper frame
                    xFrameNextRadix++;
                    nextBottom[ xFrameNextRadix ] = nextBottom[ xFrame ]; // bottom remains the same
                    nextTop[ xFrameNextRadix ] = xHigh;
                    xFrameNextRadix++;
                    nextBottom[ xFrameNextRadix ] = xLow;
                    nextTop[ xFrameNextRadix ] = nextTop[ xFrame ]; // top remains the same
                    ctFramesInNextRadix += 2;
                } else { // just add the lower frame
                    xFrameNextRadix++;
                    nextBottom[ xFrameNextRadix ] = nextBottom[ xFrame ]; // bottom remains the same
                    nextTop[ xFrameNextRadix ] = xHigh;
                    ctFramesInNextRadix++;
                }
            } else if( xLow < nextTop[ xFrame ] ){ // just add the upper frame
                xFrameNextRadix++;
                nextBottom[ xFrameNextRadix ] = xLow;
                nextTop[ xFrameNextRadix ] = nextTop[ xFrame ]; // top remains the same
                ctFramesInNextRadix++;
            } // otherwise add no new frames
            ctFramesRemaining--;
        }
        if( ctFramesInNextRadix == 0 ) break; // done
        radix--;
    }
    return keys;
}

请注意，在此实现中，“基数”是二进制基数，即位。

更新

顺便说一句，在 Java 中，这比内置的 Arrays.sort 运行速度快 5 倍（当我进行就地排序时，而不是键控排序时），这非常酷。

Answer 1

所以，基于这个想法，我认为 MSB 订单会是最快的，但我错过了什么吗？

根据我的经验，递归 MSD 基数排序确实比 LSD 基数排序实现快。然而，这样做的原因主要不是你提到的那个（这是有效的，但在实践中不是很相关），而是这两者的结合：

• 缓存效率：MSD 有助于递归实现。如果排序对象（数字、字符串等）的数字是合理随机分布的，则从某个递归深度开始，整个子问题适合更快的 CPU 缓存。根据我的经验，减少缓存未命中的次数是设计算法时可以应用的最重要的持续优化，因为与典型的 CPU 相比，主内存真的很慢
• 在特定问题大小之下，您可以使用插入排序。如果排序的对象足够小（例如，如果对整数进行排序）并且整个子数组适合缓存，则插入排序可能比任何其他排序算法都快。

你的实现不是递归的，所以它可能没有这些优势，这取决于它解决子问题的顺序（我没有真正分析过算法，但如果你使用队列而不是堆栈，你可能不会有很好的缓存位置）。

我知道 LSB 执行“稳定排序”，但我认为这没有任何实际好处。

有几个应用程序需要稳定性属性。我想到的一个是后缀数组构造。我写了一个简单的O(n log n)算法来做这个，作为另一个 SO question的答案。它使用基数排序并要求排序是稳定的。实际上，MSD 基数排序有一些稳定的变体，但它们需要额外的内存。我不知道它们与 LSD 方法相比如何。