TheRiver | blog

You have reached the world's edge, none but devils play past here

0%

基数排序+计数排序+桶排序

Posted on Edited on
Symbols count in article: 4.5k Reading time ≈ 4 mins.

基数排序+计数排序+桶排序梳理

计数排序

计数排序（Counting sort）是一种稳定的线性时间排序算法。该算法于1954年由 Harold H. Seward 提出。计数排序使用一个额外的数组{\displaystyle C} C ，其中第i个元素是待排序数组{\displaystyle A}A中值等于{\displaystyle i}i的元素的个数。然后根据数组{\displaystyle C} C 来将{\displaystyle A}A中的元素排到正确的位置。

数据量大，范围小,非比较排序

用累加数组解决稳定性问题

基数排序

基数排序（英语：Radix sort）是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。

桶排序

桶排序（Bucket sort）或所谓的箱排序，是一个排序算法，工作的原理是将数组分到有限数量的桶里。每个桶再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）。桶排序是鸽巢排序的一种归纳结果。当要被排序的数组内的数值是均匀分配的时候，桶排序使用线性时间。但桶排序并不是比较排序，他不受到nlogn下限的影响。

桶排序以下列程序进行：

  • 设置一个定量的数组当作空桶子。
  • 寻访序列，并且把项目一个一个放到对应的桶子去。
  • 对每个不是空的桶子进行排序。
  • 从不是空的桶子里把项目再放回原来的序列中。

拷贝一份wiki上的代码:

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
56
57
58
59
60
61
62
63
64
#include<iterator>
#include<iostream>
#include<vector>
using namespace std;
const int BUCKET_NUM = 10;

struct ListNode{
	explicit ListNode(int i=0):mData(i),mNext(NULL){}
	ListNode* mNext;
	int mData;
};

ListNode* insert(ListNode* head,int val){
	ListNode dummyNode;
	ListNode *newNode = new ListNode(val);
	ListNode *pre,*curr;
	dummyNode.mNext = head;
	pre = &dummyNode;
	curr = head;
	while(NULL!=curr && curr->mData<=val){
		pre = curr;
		curr = curr->mNext;
	}
	newNode->mNext = curr;
	pre->mNext = newNode;
	return dummyNode.mNext;
}


ListNode* Merge(ListNode *head1,ListNode *head2){
	ListNode dummyNode;
	ListNode *dummy = &dummyNode;
	while(NULL!=head1 && NULL!=head2){
		if(head1->mData <= head2->mData){
			dummy->mNext = head1;
			head1 = head1->mNext;
		}else{
			dummy->mNext = head2;
			head2 = head2->mNext;
		}
		dummy = dummy->mNext;
	}
	if(NULL!=head1) dummy->mNext = head1;
	if(NULL!=head2) dummy->mNext = head2;
	
	return dummyNode.mNext;
}

void BucketSort(int n,int arr[]){
	vector<ListNode*> buckets(BUCKET_NUM,(ListNode*)(0));
	for(int i=0;i<n;++i){
		int index = arr[i]/BUCKET_NUM;
		ListNode *head = buckets.at(index);
		buckets.at(index) = insert(head,arr[i]);
	}
	ListNode *head = buckets.at(0);
	for(int i=1;i<BUCKET_NUM;++i){
		head = Merge(head,buckets.at(i));
	}
	for(int i=0;i<n;++i){
		arr[i] = head->mData;
		head = head->mNext;
	}
}

164

基数排序求解

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:
    // 'nums' must consist of values from 0 to 1000000000 only
    int maximumGap(vector<int>& nums) {
        int n = nums.size();
        if (n < 2)
            return 0;

        vector<int> oVec(n);
        int max_num = *max_element(nums.cbegin(), nums.cend());

        for (int i = 1; i <= max_num; i *= 10)
        {
            array<int, 10> count{};
            for (int j = 0; j < n; ++j)
            {
                int idx = nums[j] / i % 10;
                count[idx]++;
            }

            for (int k = 1; k < 10; ++k)
                count[k] += count[k-1];

            // 反向很重要，保持稳定性，这样排百位的时候个位也是有序的
            for (int j = n - 1; j >= 0; --j)
            {
                int idx = nums[j] / i % 10;
                oVec[count[idx] - 1] = nums[j];
                count[idx]--;
            }

            nums.swap(oVec);
        }

        int ans = 0;
        for (int i = 1; i < n; ++i)
            ans = max(nums[i] - nums[i-1], ans);

        return ans;
    }
};

桶排序求解

计算桶的长度：

1
l = max(1, ((max_num - min_num) / (n - 1)))

这里算的是非负整数，长度至少为1。长度这么取也是有道理的：

数组里面每2个数之间的差值都 >= (max_num - min_num) / (n - 1)),可以证明:

1
2
3
4
5
6
7
8
假定数组里面每2个数的差值都< (max_num - min_num) / (n - 1)),一共有n个数，故可知：

num(n) - num(n-1) + num(n-1) - num(n-2) ... + num(2) - num(1)
= num(n) - num(1) 

num(n) - num(1) < (n-1)*(max_num - min_num) / (n - 1))
num(n) - num(1) < max_num - min_num
这显然不合理，所以就是说数组中必然存在2数之间差值大于(max_num - min_num) / (n - 1)的，而(max_num - min_num) / (n - 1)指的是桶的长度，所以说数组中必然存在相邻2数之间差值大于桶长度l的，也就是存在相邻的2个数跨相邻(相邻中间也可能存在空的桶)的桶。这个数必然大于一个桶内的2个数的差值，所以只需要记录每个桶的最大值和最小值，最后计算"相邻"桶的最大值和最小值的差值来找最大值就是结果。

计算桶的个数：

1
((max_num - min_num) / l ) + 1

因为是左开右闭区间，加1保证最大值在一个桶内

计算一个输入值对应桶的索引:

1
(num - min_num) / l

因为是左开右闭区间，数组又是从0开始的

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
// 桶排序
class Solution {
public:
    int maximumGap(vector<int>& nums) {
        int n = nums.size();
        if (n < 2)
            return 0;

        int max_num = *max_element(nums.begin(), nums.end());
        int min_num = *min_element(nums.begin(), nums.end());
        int bl = max(1, (max_num - min_num) / (n - 1));
        int bc = (max_num - min_num) / bl + 1;
        // 本题的数的取值范围是
        // nums' must consist of values from 0 to 1000000000 only
        vector<pair<int, int>> bucket(bc, {INT_MAX, INT_MIN});
        int ans = 0;
        for (const auto& num : nums)
        {
            int idx = (num - min_num) / bl;
            bucket[idx].first = min(bucket[idx].first, num);
            bucket[idx].second = max(bucket[idx].second, num);
        }

        int prev_second = INT_MIN;
        for (int i = 0; i < bc; ++i)
        {
            if (prev_second != INT_MIN && bucket[i].first != INT_MAX)
                ans = max(ans, bucket[i].first - prev_second);

            if (bucket[i].second != INT_MIN)
                prev_second = bucket[i].second;
        }

        return ans;
    }
};

reference

leetcode 164

https://zh.wikipedia.org/wiki/%E6%A1%B6%E6%8E%92%E5%BA%8F

----------- ending -----------