基数排序：从高位开始还是从低位开始，哪个速度更快？

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倍（当我进行原地排序而不是键排序时），这非常酷。

- Tyler Durden

---

你计时后它跑得更快了多少？ - cHao

@cHao 时间变化很大，即使对于大数组也是如此；例如，对于一个有1000万元素的数组，它排序所需的时间可以从120毫秒到160毫秒不等。 - Tyler Durden

Answer 1

根据这个想法，我认为MSB顺序会最快，但我有遗漏的地方吗？从我的经验来看，递归MSD基数排序确实比LSD基数排序实现更快。然而，其原因主要不是你提到的那个（虽然有效，但在实践中不太相关），而是这两者的结合：缓存效率：MSD适合于递归实现。如果排序对象（数字、字符串等）的数字在某种程度上是随机分布的，那么从某个递归深度开始，整个子问题都适合于更快的CPU缓存中。减少缓存未命中次数在我看来是您在设计算法时可以应用的最重要的常量优化，因为与典型的CPU相比，主内存真的很慢。在一定的问题规模下，您可以使用插入排序。如果排序对象足够小（例如，如果您对整数进行排序），并且整个子数组适合于缓存，则插入排序可能比其他任何排序算法都要快。

您的实现不是递归的，因此根据解决子问题的顺序，它可能没有这些优势（我没有真正分析算法，但如果您使用队列而不是堆栈，则可能没有非常好的缓存局部性）。

“我知道LSB执行“稳定排序”，但我看不到任何实际好处。”

有几个应用程序需要稳定性质。我能想到的一个是后缀数组构建。我已经写了一个关于如何使用基数排序和要求排序稳定的简单O(n log n)算法作为回答另一个SO问题。事实上，有MSD基数排序的稳定变体，但它们需要额外的内存。我不知道它们与LSD方法相比如何。

- Niklas B.