数据结构中各种排序的思路(4)

基数排序:基数排序(radix sort)属于“分配式排序”(distribution sort),又称“桶子法”(bucket sort)或bin sort,顾名思义,它是透过键值的部份资讯,将要排序的元素分配至某些“桶”中,藉以达到排序的作用,基数排序法是属于稳定性的排序,其时间复杂度为O (nlog(r)m),其中r为所采取的基数,而m为堆数,在某些时候,基数排序法的效率高于其它的稳定性排序法。

第一步
以LSD为例,假设原来有一串数值如下所示:
73, 22, 93, 43, 55, 14, 28, 65, 39, 81
首先根据个位数的数值,在走访数值时将它们分配至编号0到9的桶子中:
0
1 81
2 22
3 73 93 43
4 14
5 55 65
6
7
8 28
9 39

第二步
接下来将这些桶子中的数值重新串接起来,成为以下的数列:
81, 22, 73, 93, 43, 14, 55, 65, 28, 39
接着再进行一次分配,这次是根据十位数来分配:
0
1 14
2 22 28
3 39
4 43
5 55
6 65
7 73
8 81
9 93

第三步
接下来将这些桶子中的数值重新串接起来,成为以下的数列:
14, 22, 28, 39, 43, 55, 65, 73, 81, 93
这时候整个数列已经排序完毕;如果排序的对象有三位数以上,则持续进行以上的动作直至最高位数为
止。

//基数排序:利用哈希桶原理把数据排序,可选择从低位到高位或从高位到低位
//利用稀疏矩阵压缩存储进行数据定位
int  GetDigit(int* arr, size_t size)
{
    int maxDigit = 1;
    int maxNum = 10;
    for (int i = 0; i < size; ++i)
    {
        if (arr[i] >= maxNum)
        {
            int count = maxDigit;
            while (maxNum <= arr[i])
            {
                maxNum *= 10;
                ++count;
            }
            maxDigit = count;
        }
    }
    return maxDigit;
}
void LSDSort(int* arr, size_t size)//从低位开始排  MSD从高位开始排
{
    int counts[10] = { 0 };//存位数对应数据个数
    int startCounts[10] = { 0 };
    int *bucket = new int[size];
    int digit = 1;//表示先取各位
    int maxDigit = GetDigit(arr, size);
    int divider = 1;//除数
    while (digit++ <= maxDigit)
    {
        memset(counts, 0, sizeof(int) * 10);
        memset(startCounts, 0, sizeof(int) * 10);
        for (int i = 0; i < size; ++i)
            counts[(arr[i]/divider)% 10]++;
        for (int i = 1; i < 10; ++i)
            startCounts[i] = startCounts[i - 1] + counts[i - 1];
        for (int i = 0; i < size; ++i)
        {
            bucket[startCounts[(arr[i] / divider) % 10]++] = arr[i];
        }
        divider *= 10;
        memcpy(arr, bucket, sizeof(int)*size);
    }
    memcpy(arr, bucket, sizeof(int)*size);
    delete[] bucket;
}

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/7a8e8cd03556fc3b9668251dfbad0283.html