Blackops

初心易得，始终难守

0%

计数排序和基数排序

发表于 分类于 ，

从leetcode上发现的问题

计数排序

  1. 先把数组中的每个数进行计数
  2. 正向计算累加数组（其实是为了计算每个数(包括自己)前面有多少个数）
  3. 反向（为了保持稳定排序，这在后面的基数排序中非常重要）把每个数放到它对应的位置。
1
2
3
4
5
6
7
8
9
10
11
12
for (int i = 0; i < n; ++i)
{
    ++cnt[a[i]];
}
for (int i = minvalue; i <= maxvalue; ++i)
{
    cnt[i] += cnt[i - 1];
}
for (int i = n-1; i >=0 ; --i)//建议逆序达达到稳定排序目的
{
    b[--cnt[a[i]] = a[i];
}

基数排序

其实就是对每一位进行计数排序， 不停地迭代排序得到最终的有序数组，例题：164. 最大间距

  1. 选定一个基数base作为基数排序的超参数（二进制基数排序就是2，十进制就是10，这个影响不大）
  2. 把每一个数在base进制下的第k位数字作为key进行计数排序

这里实现的是简单的低位到高位的基数排序，代码简单好写，但这里的计数排序最后一定要逆序遍历放置。否则低位到高位的基数排序会出现以下情况

021、041、061、171，加粗表示当前对2位进行计数排序

那么此时cnt[0] = 3, cnt[1] = 1， 累加之后变为cnt[0] = 3, cnt[1] = 4

如果正序，
那么b[—cnt[0]] = 012, 即b[2] = 021，
接着b[—cnt[0]] = 041, 即b[1] = 041,
接着b[—cnt[0]] = 061, 即b[0] = 061,
最后b[—cnt[1]] = 171, 即b[3] = 171
可以发现021,041,061顺序反了，这是因为正序不能保证计数排序是稳定排序，而基数排序中对当前第k位的计数排序需要稳定排序，即当key值相同时，要按照在第k-1位排序中的顺序进行排序

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
int n = nums.size();
vector<int>tmp = nums;
if(n <= 1)
    return 0;
int K = 0;
int Max = *max_element(nums.begin(), nums.end());
ll divisor = 1, base = 12; // base可以任意选，一般选10或者2比较好
while (Max)
{
    ++K;//计算最多要遍历几位
    Max /= base;
}

for (int k = 0; k < K; ++k)
{
    for (int i = 0; i < base; ++i)
    {
        cnt[i] = 0;
    }
    for (int i = 0; i < n; ++i)
    {
        ++cnt[(nums[i] / divisor) % base];
    }
    for (int i = 1; i < base; ++i)
    {
        cnt[i] += cnt[i - 1];
    }
    for (int i = n - 1; i >= 0 ; --i)//一定要逆序
    {
        tmp[--cnt[(nums[i] / divisor) % base]] = nums[i];
    }
    nums = tmp;
    divisor *= base;
}