最重要的与最不重要的基数排序

Question

如果我只需要对由ASCII字符组成的字符串进行排序,那么想知道使用最重要和最不重要的基数排序之间有什么区别？我认为他们应该有相同的结果,但是被以下链接中的以下声明搞糊涂了,如果有人可以帮助澄清,那就太棒了.

https://en.wikipedia.org/wiki/Radix_sort

最高位数(MSD)基数排序可用于按字典顺序对键进行排序.与最低有效位(LSD)基数排序不同,最重要的数字基数排序不一定保留重复键的原始顺序.

林先生,提前谢谢

Answer 1

LSD基数排序可以在每次传递后在逻辑上连接已排序的二进制数(如果使用计数/基数排序,则将它们视为单个二进制数).MSD基数排序必须在每次传递后独立地递归排序每个bin.如果按字节排序,第一次传递后为256个二进制位,第二次传递后为65536个二进制位,第三次传递后为16777216(1600万个)二进制位,....

这就是旧卡分类器首先对数据LSD进行排序的原因.链接到其中一个实际的视频.这些卡片被送入并向下滑入滑槽.在视频中,卡片分类器将卡片放入"0"到"9"的箱子中,然后操作员从0箱中取出卡片,然后从1箱中取出卡片并将它们放在0箱子的顶部(后面)卡片,然后2个bin卡片在牌组后面,依此类推,将卡片连接起来.对于大型卡片组,卡片分拣机上方将设置在每个箱子上方的架子上,以便在甲板太大而无法用手握住时放置卡片.

http://www.youtube.com/watch?v=jJH2alRcx4M

示例C++ LSD基数排序,用于32位无符号整数,其中每个"数字"是一个字节.大多数代码生成一个计数矩阵,这些计数矩阵被转换为标记可变大小区间之间边界的索引.实际的基数排序位于最后一个嵌套循环中.

//  a is input array, b is working array
uint32_t * RadixSort(uint32_t * a, uint32_t *b, size_t count)
{
size_t mIndex[4][256] = {0};            // count / index matrix
size_t i,j,m,n;
uint32_t u;
    for(i = 0; i < count; i++){         // generate histograms
        u = a[i];
        for(j = 0; j < 4; j++){
            mIndex[j][(size_t)(u & 0xff)]++;
            u >>= 8;
        }       
    }
    for(j = 0; j < 4; j++){             // convert to indices
        m = 0;
        for(i = 0; i < 256; i++){
            n = mIndex[j][i];
            mIndex[j][i] = m;
            m += n;
        }       
    }
    for(j = 0; j < 4; j++){             // radix sort
        for(i = 0; i < count; i++){     //  sort by current lsb
            u = a[i];
            m = (size_t)(u>>(j<<3))&0xff;
            b[mIndex[j][m]++] = u;
        }
        std::swap(a, b);                //  swap ptrs
    }
    return(a);
}