算法------基数排序

153 阅读 0 评论 101 点赞

我是靠谱客的博主开朗钢笔，这篇文章主要介绍算法------基数排序，现在分享给大家，希望可以做个参考。

基数排序

借助多关键字排序的思想，不利用关键字之间比较，而是“分配”和“收集”。

分类：

LSD：从最低位优先排序。

MSD:最高位优先排序。

举个栗子：

73 22 93 43 55 14 28 65 39 81

首先根据个位数的数值，在遍历数据时将它们各自分配到编号0至9的桶中。

分配结束后，进行桶中重新收集，得到如下序列：

81 22 73 93 43 14 55 65 28 39

再进行一次分配，这次按照十位数值来进行分配，得到结果

得到序列：14 22 28 39 43 55 65 73 81 93

排序完成。

LSD过程：（1）先统计整个原始数组的最大位数，有d位数就进行d次分配，收集。例如，最大位数为55，就进行两次。

（2）用一维数组digitcount[]对原始数组的最右边数（从最低位开始）开始统计，对应到0-9中。

（3）然后就是找出digitcount[]数组与bucket[]数组之间的联系，将统计的相应数据放入bucket[]中（顺序不能乱，保证稳定性）。

（4）再重复收集，分配给bucket[],直至循环结束。

digitcount[]与bucket[]之间的联系：

算法代码：

复制代码

//基数排序（稳定算法）
void RadixSortLSD(int *array, int length)
{
        int i, maxval = 0, digition = 1;
        int  buckets[10];
        //遍历一遍得到数组中最大位数的数
        for (i = 0; i < length; ++i)
        {
               if (array[i] > maxval)
                       maxval = array[i];
        }
        int pass = 1;
        //根据位数进行循环
        while ((maxval / digition)>0)
        {
               //执行一遍之后需要进行清空
               int digitcount[10] = { 0 };
               //统计最右边位数出现次数
               for (i = 0; i < length; ++i)
               {
                       digitcount[(array[i] / digition) % 10]++;
               }
               //将统计出来的数字进行总的计数
               for (i = 1; i < 10; i++)
               {
                       digitcount[i] += digitcount[i - 1];
               }
               //找出对应buckets的下标，并放入
               for (i = length - 1; i >= 0; --i)
               {
                       buckets[--digitcount[(array[i] / digition) % 10]] = array[i];
               }
               //排列好之后重新放回原数组中
               for (i = 0; i < length; ++i)
               {
                       array[i] = buckets[i];
               }
               digition *= 10;
        }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
//基数排序（稳定算法）
void RadixSortLSD(int *array, int length)
{
        int i, maxval = 0, digition = 1;
        int  buckets[10];
        //遍历一遍得到数组中最大位数的数
        for (i = 0; i < length; ++i)
        {
               if (array[i] > maxval)
                       maxval = array[i];
        }
        int pass = 1;
        //根据位数进行循环
        while ((maxval / digition)>0)
        {
               //执行一遍之后需要进行清空
               int digitcount[10] = { 0 };
               //统计最右边位数出现次数
               for (i = 0; i < length; ++i)
               {
                       digitcount[(array[i] / digition) % 10]++;
               }
               //将统计出来的数字进行总的计数
               for (i = 1; i < 10; i++)
               {
                       digitcount[i] += digitcount[i - 1];
               }
               //找出对应buckets的下标，并放入
               for (i = length - 1; i >= 0; --i)
               {
                       buckets[--digitcount[(array[i] / digition) % 10]] = array[i];
               }
               //排列好之后重新放回原数组中
               for (i = 0; i < length; ++i)
               {
                       array[i] = buckets[i];
               }
               digition *= 10;
        }
}