基数排序

痛定思痛。 2021-09-19 10:12 387阅读 0赞

在箱子排序中，尽管时间复制度仅仅有(n),但假设其箱子序列较大的话将会导致程序的空间复杂度较大，所以对于对于属性值跨度比較大的序列能够採用基数排序法。

概述：详细的做法是并不直接对这些数排序，而是採用一些基数来分解这些数，比如：用基数10来分解3725能够得到3、7、2和5。

而利用60来分解能够得到1、2、5。

然后再依据每一位基数从低位到高位对原数据进

行排序，即若最长的基数有m位。直到共进行了m次排序后则基数排序完毕。

特点：能够在o(n)时间内对0到 -1之间的n个整数进行排序。当中c为常数。

演示样例：

问题一：对以下的序列进行排序：

\{216,521,425,116,91,515,124,12434,96,24,5\}

问题二：对以下的序列进行排序：

\{1123,1657,88865,22,546,9908,111111,78786,22,515,515,9908,414,33,4,90,8765,12,543,66,99\}

演示样例实现代码及结果例如以下：

#include<iostream>
    #include<deque>
    #include<algorithm>
    #include<iterator>
    #include<vector>
    #include<map>
    using namespace std;
    
    //将10进制数data分解成n进制数的序列
    deque<int> trans(int data,int n)
    {
    	deque<int> deq;
    	for ( ; 0!=data ; )
    	{
    		deq.push_front(data%n);
    		data = (data-data%n)/n;
    	}
    	return deq;
    }
    
    void basic_sort(vector<int> & datas,int basic)
    {
    	//求出每一个数的基数并关联起来
    	map<int,deque<int>> ma;
    	for (vector<int>::iterator iter = datas.begin();iter!=datas.end();iter++)
    	{
    		ma[*iter] = trans(*iter,basic);
    	}
    	//找出最长基数个数
    	int length = 0;
    	for(map<int,deque<int>>::iterator iter = ma.begin();iter!=ma.end();iter++)
    	{
    		if(length<iter->second.size())
    			length = iter->second.size();
    	}
    	//进行每一位基数的n轮排序
    	for (int i = 0; i < length; i++)
    	{
    		//建立箱子序列
    		vector<vector<int>> box(basic);
    		//開始排序
    		for (vector<int>::iterator iter = datas.begin();iter!=datas.end();iter++)
    		{
    			//找到当前当前第i位的基数，并依据基数装箱
    			int n = 0;
    			if (i<ma[*iter].size())
    			{
    				n = ma[*iter][ma[*iter].size()-i-1];
    			}
    			box[n].push_back(*iter);
    		}
    		//将排序后结果复制给datas
    		datas.clear();
    		for (vector<vector<int>>::iterator iter = box.begin();iter!=box.end();iter++ )
    		{
    				for (vector<int>::iterator it = (*iter).begin(); it!=(*iter).end() ; it++)
    				{
    					datas.push_back(*it);
    				}
    		}
    	}
    }
    
    int main()
    {
    	//解决这个问题一
    	int array1[] = {216,521,425,116,91,515,124,12434,96,24,5};
    	vector<int> vec(array1,array1+sizeof(array1)/sizeof(array1[0]));
    	basic_sort(vec,10);
    	copy(vec.begin(),vec.end(),ostream_iterator<int>(cout," "));
    	cout<<endl;
    
    	//解决这个问题二
    	int array2[] = {1123,1657,88865,22,546,9908,111111,78786,22,515,515,9908,414,33,4,90,8765,12,543,66,99};
    	vector<int> vec1(array2,array2+sizeof(array2)/sizeof(array2[0]));
    	basic_sort(vec1,60);
    	copy(vec1.begin(),vec1.end(),ostream_iterator<int>(cout," "));
    	cout<<endl;
    }
    
    /*
     5 24 91 96 116 124 216 425 515 521 12434
     4 12 22 22 33 66 90 99 414 515 515 543 546 1123 1657 8765 9908 9908 78786 88865 111111
     请按随意键继续. . .
    */

本文转自mfrbuaa博客园博客，原文链接：http://www.cnblogs.com/mfrbuaa/p/5357813.html，如需转载请自行联系原作者