算法基础算法

非比较排序

字数统计: 1.4k字   |   阅读时长: 6分
, , ,

摘要: 计数排序、桶排序、基数排序

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

$1 计数排序

当数据范围较小，例如十万级，可以通过一个计数数组统计各个数字出现的次数，然后在按照出现的数字和次数从小到大依次写回原数组。

使用场景:

  • 数据范围说明用计数排序。
  • 某些数据结构的操作也基于计数排序，例如后缀数组。

整个流程是先计数，再统计。统计阶段有种实现方式，一种不稳定但是好写，另一种稳定但是不好写。

代码模板 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 计数排序,
// 1 <= A.length <= 10000
// -50000 <= A[i] <= 50000
void countingsort(vector<int>& nums)
{
    if(nums.empty()) return;
    int n = nums.size();
    if(n == 1) return;
    // 范围 [-50000, 50000] 映射到[0, 100000]
    for(int i = 0; i < n; ++i)
        nums[i] += 50000;
    int m = 100001; //[0, 100000]
    // _countingsort1(nums, m);
    _countingsort2(nums, m);
    for(int i = 0; i < n; ++i) // 减回来
        nums[i] -= 50000;
}

(1) 不保证稳定, 也叫假计数排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void _countingsort1(vector<int>& nums, int m)
{
    int n = nums.size();
    vector<int> cnt(m + 1, 0);
    for(int i = 0; i < n; ++i) cnt[nums[i]]++;

    for(int i = 0, k = 0; i <= m; ++i)
    {
        while(cnt[i]){
            nums[k++] = i;
            cnt[i]--;
        }
    }
}

(2) 保证稳定, 借助 cnt 数组的前缀和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void _countingsort2(vector<int>& nums, int m)
{
    int n = nums.size();
    vector<int> cnt(m + 1, 0);
    for(int i = 0; i < n; ++i) cnt[nums[i]]++;

    vector<int> presum_cnt(m + 2, 0);
    for(int i = 1; i < m + 2; ++i)
        presum_cnt[i] = presum_cnt[i - 1] + cnt[i - 1];
    vector<int> tmp(nums.begin(), nums.end()); // nums 的副本

    for(int i = n - 1; i >= 0; --i)
        nums[--presum_cnt[tmp[i]]] = tmp[i];
}

三色排序

三色排序是计数排序的一个特例。由于待排序的数组值只有三种，因此除了用标准的计数排序实现，也可以用双指针解决。

三色排序涉及到以下题目，参考文章 三色排序。

题目清单

$2 桶排序

把数据范围通过一个映射函数分为若干个桶，假定各个桶里的数据量是均匀的。且要保证桶间有序。

当数据范围很大，例如20亿以上时，计数排序就不行了。但是可以分成1000个桶，桶的数据范围: 第一个桶 [0, 199999] 以此类推。每个桶的期望元素个数为 $n/1000$。这里有个关键假设: 每个桶里的元素个数比较平均。

桶内的排序可以使用任意一种排序，也可以继续使用桶排序。

映射函数要保证桶间的顺序，桶内可以是无序的。

极端情况每个数都是 1 个桶就是计数排序。

代码模板 (C++)

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
// 桶排序
// 范围 [-50000, 50000] 映射到[0, 100000]
void bucketsort(vector<int>& nums)
{
    if(nums.empty()) return;
    int n = nums.size();
    if(n == 1) return;
    int m = 11; // m 个桶, 每个桶里 100000/m 个数, 100000 单独是一个桶
    _bucketsort2(nums, m);
}

// 用 vector 指针的 vector 存桶
void _bucketsort(vector<int>& nums, int m)
{
    // 数字 num -> 桶编号 i
    // (num + 50000) / 1000
    vector<vector<int>* > buckets(m, nullptr);
    for(int i = 0; i < m; ++i)
        buckets[i] = new vector<int>();

    int n = nums.size();
    for(int i = 0; i < n; ++i)
        buckets[(nums[i] + 50000) / (100000 / (m - 1))] -> push_back(nums[i]);

    for(int i = 0; i < m; ++i)
        quicksort(*(buckets[i]));

    int iter = 0;
    for(vector<int> *bucket: buckets)
        for(int num: *bucket)
            nums[iter++] = num;

    for(int i = 0; i < m; ++i)
        delete buckets[i];
}

// 用 vector 的 vector 存桶
void _bucketsort2(vector<int>& nums, int m)
{
    // 数字 num -> 桶编号 i
    // (num + 50000) / 1000
    vector<vector<int> > buckets(m);

    int n = nums.size();
    for(int i = 0; i < n; ++i)
        buckets[(nums[i] + 50000) / (100000 / (m - 1))].push_back(nums[i]);

    for(int i = 0; i < m; ++i)
        quicksort(buckets[i]);

    int iter = 0;
    for(vector<int> bucket: buckets)
        for(int num: bucket)
            nums[iter++] = num;
}

分桶思想

桶排序背后的分桶思想可以解决很多问题，参考文章 分桶法。

最经典的题目是 164. 最大间距。题解参考：力扣164-桶排序。

题目清单

$3 基数数排序

按照数位进行映射的桶排序，0~9 一共10个桶。int 范围 正负 20 亿，先按个位排，再按十位排，…，最多有10个数位，所以最多要做10次桶排序。

有大量的取模和除法运算，使得 $O(N)$ 的常数很高，一般跑不过一般的 $O(N\log N)$ 算法，较少用到。

代码 (模板，C++)

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
// 基数排序, 只能对正数用(以下代码用在含负数的数组报错)
// 且O(N)的常数较大，实际比 $O(N\log N)$ 慢, 很少用
void radixsort(vector<int>& nums)
{
    if(nums.empty()) return;
    int n = nums.size();
    if(n == 1) return;

    for(int i = 0; i < n; ++i)
        nums[i] += 50000;
    _radixsort(nums);
    for(int i = 0; i < n; ++i) // 减回来
        nums[i] -= 50000;

}

void _radixsort(vector<int>& nums)
{
    int n = nums.size();
    // 定义桶
    vector<vector<int> > cnt(10); // 数位一共有 10 种, 10 个桶
    for(int i = 0; i < 10; ++i)
    {
        for(int j = 0; j < 10; ++j) cnt[j].clear();

        for(int j = 0; j < n; ++j)
            cnt[get(nums[j], i)].push_back(nums[j]);

        for(int j = 0, k = 0; j < 10; ++j)
            for(int num: cnt[j])
                nums[k++] = num;
    }

}

int get(int x, int i) // 返回 x 的第 i 位
{
    while(i--) x /= 10;
    return x % 10;
}
Share