C++排序算法之基数排序

た入场券 2022-06-11 05:13 262阅读 0赞

**基数排序**

基数排序是一种非比较的排序算法，它是以桶排序为基础的，其思想是“多关键字排序”。

基数排序有两种实现方式：

（1）**最高位优先**：即先按最高位排成若干子序列，在对每个子序列按次高位排序。

举例：扑克牌的例子，就是先按花色排成4个子序列，在对每种花色的13张牌进行排序，最终使所有的扑克牌整体有序。

（2）**最低位优先**：这种方式不必分成子序列，每次排序全体元素都参与。

举例：扑克牌的例子，就是先按数字将牌分配到13个桶中，然后从第一个桶开始依次收集；再将收集好的牌按花色分配到4个桶中，然后还是从第一个桶开始依次收集。经过两次“分配”和“收集”操作，最终使牌有序。

**执行过程：**

原始序列： 278 109 063 930 589 184 505 296 008 083

每个元素都是由“数字”组成，数字的范围是0~9，所以准备10个桶来放元素。如果元素不只有数字组成，例如还有一位是英文字母，那么按字母这一位进行排序时，要准备26个桶（假设不区分大小写）。注意这里所说的“桶”，相当于一个先进先出的队列（从上面进，下面出）。

![Center][]

![Image 1][]

（1）进行第一趟分配和收集，按照最后位。

**分配**过程如下（注意数据从桶的上面进入）：

278最低位是8，放入桶8中：如下图所示：

![Center 1][]

![Image 1][]

109最低位是9，放入桶9中，如下图所示：

![Center 2][]

![Image 1][]

按照这样的方法，依次（按原始序列顺序）将原始序列的每个数放到对应的桶中。第一趟分配过程完成，结果如下图所示：

![Center 3][]

![Image 1][]

**收集**过程如下：按桶0到桶9的顺序收集（注意数据时从桶的下面出）

桶0： 930

桶1： 没有元素，不收集

桶2： 没有元素，不收集

桶3： 063，083

...........

桶8： 278，008

桶9： 109，589，269

将每个桶收集的数据依次排开，所以第一趟收集后的结果为：

930 063 083 184 505 278 008 109 589 269

注意观察，最低位有序了，这就是第一趟基数排序后的结果。

（2）在第一趟排序结果的基础上，进行第二趟分配和收集：

第二趟分配过程：按中间位分配结果如下图：

![Center 4][]

![Image 1][]

第二趟收集结果为：

505 008 109 930 063 269 278 083 184 589

（3） 在第二趟排序结果的基础上，进行第三趟分配和收集：

第三趟分配过程：按最高位分配结果如下图：

![Center 5][]

![Image 1][]

第三趟收集结果为：

008 063 083 109 184 269 278 505 589 930

代码实现如下：

#include <iostream>
    #include <vector>
    #include <string>
    using namespace std;
      
    /*获得数组中数值的最大位数*/
    int maxBit(const vector<int> arr) {
    	int len = 0;
    	for (auto x : arr) {
    		int c = 0;
    		int tmp = x;
    		while (tmp > 0) {
    			tmp /= 10;
    			c++;
    		}
    		if (len < c)
    			len = c;
    	}
    	return len;
    }
    
    /*基于int型数组的基数排序简单实现*/
    void radixsort(vector<int> & arr)
    {
    	const int BUCKETS = 10;									//设置桶的个数	
    	vector<vector<int>> buckets(BUCKETS);		 //设置基数桶
    	int len = maxBit(arr);											 //获得数组中数值的最大位数，依次决定排序次数
    	int r = 1;
    	for (int i = 0; i < len; ++i)									//从低位到高位进行基数排序，依次方法桶中
    	{
    		for (int & s : arr) {											//此循环按相应基数排序
    			int k = s / r;
    			int q = k%BUCKETS;
    			buckets[q].push_back(std::move(s));
    		}
    		int idx = 0;
    		for (auto & thisBucket : buckets)					//循环每个桶中的元素
    		{
    			for (int &s : thisBucket)								//将每个桶中的元素放入原始数组中
    				arr[idx++] = std::move(s);
    			thisBucket.clear();
    		}
    		cout << "第"<<i+1<<"趟排序结果：";
    		for (auto x : arr)
    			cout << x << " ";
    		cout << endl;
    		r = r * 10;
    	}
    }
    
    int main()
    {
    	vector<int> arr = { 278,109,63,930,589,184,505,269,8,83 };
    	radixsort(arr);
    	cout << "基数排序的结果：";
    	for (auto x : arr)
    		cout << x << " ";
    	cout << endl;
    	return 0;
    }

运行结果如下：

![Center 6][]

对字符串进行基数排序的代码实现：

#include <iostream>
    #include <vector>
    #include <string>
    using namespace std;
    
    /*基于字符串基数排序的简单实现*/
    void radixsort(vector<string> & arr, int stringLen)
    {
    	const int BUCKETS = 256;
    	vector<vector<string>> buckets(BUCKETS);                //设置基数桶
    
    	for (int pos = stringLen-1; pos >= 0; pos--)                    //从低位到高位进行基数排序，依次方法桶中
    	{
    		for (string & s : arr)
    			buckets[s[pos]].push_back(std::move(s));             //此循环按相应基数排序
    
    		int idx = 0;
    		for (auto & thisBucket : buckets)                             //循环每个桶中的元素
    		{
    			for (string &s : thisBucket)                                   //将每个桶中的元素放入原始数组中
    				arr[idx++] = std::move(s);
    			thisBucket.clear();
    		}
    	}
    }
    
    /*第一趟个位数字的排序：000  001  512  343  064  125  216  027  008  729
       第二趟十位数字的排序：000  001  008  512  216  125  027  729  343  064
       第三趟百位数字的排序：000  001  008  027  064  125  216  343  512  729*/
    
    int main()
    {
    	vector<string> arr = { "064","008","216","512","027","729","000","001","343","125" };
    	radixsort(arr, 3);
    	for (auto x : arr)
    		cout << x << " ";
    	return 0;
    }

运行结果如下：

![Center 7][]

复杂度分析：

**时间复杂度**为O(d(n+r))：其中d为元素的关键字位数，n为元素个数，r为关键字的取值范围，即桶的个数。

**空间复杂度**为O(r)

[Center]: /images/20220611/bc0dde832bf44da6b0b861629b25dc97.png
[Image 1]: 
[Center 1]: /images/20220611/cd6267dab29247f7b7b2809a9a761225.png
[Center 2]: /images/20220611/c5ad1874360f484cbde02ba61ca0e024.png
[Center 3]: /images/20220611/b2ec84293b62487b81cf6e1a6a43bb8a.png
[Center 4]: /images/20220611/be759191e01648d1ace1b45c7955f324.png
[Center 5]: /images/20220611/113a6115519044a7b5ce24225809a41c.png
[Center 6]: /images/20220611/02df65fdfe374d8dabdc59d26a04b95c.png
[Center 7]: /images/20220611/166e65b796894794bdbcadf2a7af4673.png