最重要的最小有效基数排序

本文介绍了最重要的最小有效基数排序的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！

问题描述

如果我只需要对由ASCII字符组成的字符串进行排序，想知道使用最高有效v.s之间有什么区别。最不重要的基数排序？我认为它们应该具有相同的结果，但是会被下面链接中的以下语句所混淆，并且如果有人可以帮助澄清，那就太好了。

If I just need to sort strings composed by ASCII characters, wondering what are the differences between using most significant v.s. least significant radix sorting? I think they should have the same results, but confused by the following statement from below link, and if anyone could help to clarify, it will be great.

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

A most significant digit (MSD) radix sort can be used to sort keys in lexicographic order. Unlike a least significant digit (LSD) radix sort, a most significant digit radix sort does not necessarily preserve the original order of duplicate keys.

预先感谢，
Lin

thanks in advance,Lin

推荐答案

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

A LSD radix sort can logically concatenate the sorted bins after each pass (consider them to be a single bin if using a counting / radix sort). A MSD radix sort has to recursively sort each bin independently after each pass. If sorting by bytes, that 256 bins after first pass, 65536 bins after second pass, 16777216 (16 million) bins after third pass, ... .

旧卡分类器首先对数据LSD进行排序。链接到其中之一的视频。卡片被送入并朝下放入滑槽。在视频中，卡片分类器将卡片放入 0至 9的纸箱中，然后操作员从0纸箱中取出纸牌，然后从1纸箱中取出纸牌并将其放置在0纸箱的顶部（后面）卡，然后将2个垃圾箱卡放到甲板后面，依此类推，将垃圾箱中的卡连接起来。对于较大的卡片组，在卡片分类机上方将在每个纸箱上方设置架子，以便在卡片组太大而无法用手拿着时放置卡片。

This is why the old card sorters sort data LSD first. Link to video of one of these in action. The cards are fed in and drop into the chutes face down. In the video, the card sorter drops the cards into bins "0" to "9", then the operator takes the cards from the 0 bin, then takes the cards from the 1 bin and places them on top (behind) the 0 bin cards, then the 2 bin cards go behind the deck, and so on, "concatenating" the cards from the bins. For large decks of cards, above the card sorter would be set of shelves above each bin to place the cards when the decks were too large to hold by hand.

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

Example C++ LSD radix sort for 32 bit unsigned integers, where each "digit" is a byte. Most of the code generates a matrix of counts which are converted into indices that mark the boundaries between variable size bins. The actual radix sort is in the last nested loop.

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

这篇关于最重要的最小有效基数排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！

Sorter