java - 基数排序最重要的优先或最不重要的，哪个更快？

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

So, based on this idea, I would think MSB order would be fastest, but am I missing anything?

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

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

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

I know that LSB performs "stable sort", but I don't see any practical benefit to this.

有几种应用需要稳定性。我想到的是 suffix array construction .我写过一个简单的 O(n log n) 算法来实现 answer to another SO question .它使用基数排序，要求排序稳定。其实有stable variations of MSD radix sort , 但它们需要额外的内存。我不知道它们与 LSD 方法相比如何。