最重要 v.s。最低有效基数排序

Question

如果我只需要对由 ASCII 字符组成的字符串进行排序，想知道使用最重要的 v.s 之间有什么区别。最不重要的基数排序？我认为他们应该有相同的结果，但被下面的以下陈述弄糊涂了link，如果有人能帮助澄清，那就太好了。

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

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

提前致谢，林

Answer 1

LSD 基数排序可以在每次通过后逻辑上连接排序的 bin（如果使用计数/基数排序，则将它们视为单个 bin）。 MSD 基数排序必须在每次通过后独立地对每个 bin 进行递归排序。如果按字节排序，第一次通过后有 256 个 bin，第二次通过后有 65536 个 bin，第三次通过后有 16777216（1600 万）个 bin，...。

这就是为什么旧的卡片分类器首先对数据 LSD 进行分类的原因。 Link 到其中一个正在运行的视频。卡片被送入并面朝下落入滑槽。在视频中，卡片分类器将卡片放入“0”到“9”的垃圾箱中，然后操作员从 0 垃圾箱中取出卡片，然后从 1 垃圾箱中取出卡片并将它们放在 0 垃圾箱的顶部（后面）卡片，然后 2 个箱子卡片放在甲板后面，依此类推，"concatenating" 个箱子中的卡片。对于大副纸牌，当纸牌太大无法用手拿时，纸牌分类器上方将在每个垃圾箱上方设置一组架子以放置纸牌。

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

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

//  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);
}

Answer 2

让您感到困惑的部分是几乎所有 LSD 基数排序都保留了重复键的顺序。那是因为他们完全依赖这个属性来工作。例如，如果您有 2 次这样的迭代，首先按个位排序，然后按十位排序：

22        21        11
21   ->   11   ->   21
11        22        22

当我们按十位排序时，我们需要保留按个位排序时得到的打破平局的顺序，这样即使 21 和 22 在 10 位具有相同的数字，它们也会以正确的顺序出现。如果您实施第一个排序（按一个排序）与您执行所有其他排序的方式相同（为什么不这样做？），那么排序是稳定的。

可以使用与 LSD 基数排序相同类型的排序步骤编写 MSD 基数排序，在这种情况下它也将是稳定的。但是还有其他通常更有效的方法来实现 MSD 基数排序，但没有这个属性.

MSD-first 基数排序不保留顺序或重复项通常是就地的，即，它们无需分配单独的数组来保存已排序的元素即可工作。

请注意，如果您只是通过比较字符串的 ASCII 代码点对字符串列表进行排序，那么其中的 none 会有所不同。 "preserving the order of duplicate keys" 仅在附加了额外信息时才有意义。例如，如果键具有关联值，或者如果您以大小写无关的方式排序并且您希望 "Abe" 和 "abE" 以它们进来的相同顺序输出。

最重要 v.s。最低有效基数排序

most significant v.s. least significant radix sort

algorithm

sorting

radix-sort