非比较排序

  |  

$1.1 计数排序

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

使用场景:

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

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

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
    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]--;
    }
    }
    }
  • 保证稳定, 借助 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];
    }

75. 颜色分类

三色排序

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
class Solution {
public:
void sortColors(vector<int>& nums) {
_countingsort(nums);
}

private:
// 基本计数排序
void _countingsort(vector<int>& nums)
{
if(nums.empty()) return;
int n = nums.size();
if(n == 1) return;

// 数据范围 0-2
// 计数排序空间复杂度 O(N + K), K = 3
int K = 3;
vector<int> cnt(K, 0);
for(int i = 0; i < n; ++i)
++cnt[nums[i]];

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

另解:双指针, 类似单指针 partition 的操作

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
class Solution {
public:
void sortColors(vector<int>& nums) {
_twopointers(nums);
}

private:
// 双指针
// 类似单指针 partition 的操作
void _twopointers(vector<int>& nums)
{
if(nums.empty()) return;
int n = nums.size();
if(n == 1) return;

int left = 0, right = n - 1; // n >= 2, right >= 1
// left 的左侧都是 0, right 的右侧都是 2
for(int i = 0; i <= right;)
{
if(nums[i] == 0)
swap(nums[i++], nums[left++]);
else if(nums[i] == 2)
swap(nums[i], nums[right--]);
else
++i;
}
}
};

280. 摆动排序

与计数排序无关,324. 摆动排序 II 的铺垫。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
void wiggleSort(vector<int>& nums) {
if(nums.empty()) return;
int n = nums.size();
if(n == 1) return;

// n >= 2
for(int i = 1; i < n; ++i)
{
// if(i % 2 == 1 && nums[i] < nums[i - 1])
// swap(nums[i], nums[i - 1]);
// if(i % 2 == 0 && nums[i] > nums[i - 1])
// swap(nums[i], nums[i - 1]);

// 简化写法
if ((i % 2 == 0) == (nums[i] > nums[i + 1]))
swap(nums[i], nums[i - 1]);
}
}
};

324. 摆动排序 II

280. 摆动排序 中的小于等于改成严格小于,大于等于改成严格大于。其它条件不变。

三色排序是其中一步:上坡,下坡,平原可以视为三种颜色

力扣324-摆动排序II,三色排序应用

274. H 指数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
int hIndex(vector<int>& citations) {
if(citations.empty()) return 0;
int n = citations.size();
vector<int> cnt(n + 1, 0);
for(int i: citations)
++cnt[min(i, n)];
int k = n;
for(int s = cnt[n]; k > s; s += cnt[k])
--k;
return k;
}
};

945. 使数组唯一的最小增量

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
class Solution {
public:
int minIncrementForUnique(vector<int>& A) {
int n = A.size();
if(n < 2) return 0;
int M = 40000;
_countingsort(A, M);
int cur = A[0];
int res = 0;
for(int i = 1; i < n; ++i)
{
if(A[i] > cur)
cur = A[i];
else
{
res += cur - A[i] + 1;
++cur;
}
}
return res;
}

private:
void _countingsort(vector<int>& A, int M)
{
vector<int> cnt(M, 0);
for(int num: A) ++cnt[num];
int n = A.size();
int j = 0;
for(int i = 0; i < (int)cnt.size(); ++i)
{
int k = cnt[i];
while(k > 0)
{
A[j] = i;
++j;
--k;
}
if(j == n) break;
}
}
};

1122. 数组的相对排序

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
class Solution {
public:
vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) {
vector<bool> in_arr2(1001, false);
for(int num: arr2)
in_arr2[num] = true;
vector<int> cnt(1001, 0);
for(int num: arr1)
++cnt[num];
vector<int> result;
for(int num: arr2)
{
if(cnt[num] > 0)
{
for(int i = 0; i < cnt[num]; ++i)
result.push_back(num);
}
}
for(int num = 0; num <= 1000; ++num)
{
if(in_arr2[num]) continue;
if(cnt[num] == 0) continue;
for(int i = 0; i < cnt[num]; ++i)
result.push_back(num);
}
return result;
}
};

$1.2 桶排序

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

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

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

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

极端情况每个数都是 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
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-桶排序

347. 前 K 个高频元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int, int> mapping; // num -> cnt
for(int num: nums)
++mapping[num];
int n = nums.size();
vector<vector<int> > buckets(n + 1, vector<int>());
for(auto it = mapping.begin(); it != mapping.end(); ++it)
buckets[it -> second].push_back(it -> first);
vector<int> result;
for(int i = n; i >= 1 && k > 0; --i)
{
int cur_cnt = buckets[i].size();
if(cur_cnt > 0)
result.insert(result.end(), buckets[i].begin(), buckets[i].end());
k -= cur_cnt;
}
return result;
}
};

451. 根据字符出现频率排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
string frequencySort(string s) {
int n = s.size();
if(n <= 2) return s;
unordered_map<char, int> char_cnt;
for(char c: s)
++char_cnt[c];
vector<vector<char> > buckets(n + 1, vector<char>());
for(auto it = char_cnt.begin(); it != char_cnt.end(); ++it)
buckets[it -> second].push_back(it -> first);
string result;
for(int i = n; i >= 1; --i)
if(!buckets[i].empty())
{
for(char c: buckets[i])
{
string item(i, c);
result.insert(result.end(), item.begin(), item.end());
}
}
return result;
}
};

1424. 对角线遍历 II

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
class Solution {
public:
vector<int> findDiagonalOrder(vector<vector<int>>& nums) {
int n = nums.size();
vector<vector<int>> buckets;
int all = 0;
for(int i = 0; i < n; ++i)
{
int m = nums[i].size();
all += m;
for(int j = 0; j < m; ++j)
{
int k = i + j;
if((int)buckets.size() < k + 1)
buckets.push_back({});
buckets[k].push_back(nums[i][j]);
}
}
vector<int> result(all);
int idx = 0;
int N = buckets.size();
for(int k = 0; k < N; ++k)
{
int bn = buckets[k].size();
for(int i = bn - 1; i >= 0; --i)
result[idx++] = buckets[k][i];
}
return result;
}
};

$1.3 基数数排序

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

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

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