排序算法-桶排序(基数排序)

排序算法--桶排序(基数排序)

1.基数排序

基数排序的思想是针对整数的每一位进行排序，它是一种稳定的排序，从个位开始比较，小的再前面，大的排在后面，然后顺次取出，对取出后的数据组针对下一位再进行排序，一直排到位数最多的那一位排完为止！

当桶排序的输入符合均匀分布时，可以期待线性期望时间运行，它的时间复杂度大概为o(n*m);n代表数组长度，m代表最长位的位数。

但桶排序的缺点是耗费空间比较大，而且它并不能排序小数，不过可以先将小数转换为整数，再排序，以及负数，负数要分两部分排，首先是纯正数A那一块先排，然后负数为一块B化为正数再排，然后转换为负数颠倒，然后再加上原先的正数A那一堆组合起来！

示例代码如下：

#include <iostream>
#include<vector>
using namespace std;


vector< vector<int> > myVector;//二维

//后续处理
//取出排序后的数
void follow_Slove(int* A)
{   
	int vert = 0;

	for ( int i=0; i< myVector.size(); i++)
	{
		for ( int j=0; j< myVector[i].size(); j++)
		{
                A[vert] = myVector[i][j];
				vert++;
		}
		myVector[i].clear();//移除所有元素
	}

}


/*基数排序，又名桶排序
   A:待排数组
   len:数组长度
   bitLen:最长整数的位数
   默认采用10进制数
*/
void bucket_Sort(int* A,int len,int bitLen,int scale)
{
	//基于每个数的个位，十位，百位，分别每次排序
	
	int baseValue = 10;//为了求余取出各位数字
	int vert;
	myVector.resize(scale);
	//每一位
	for (int i=0;i<bitLen;i++)
	{  
		//每一个数
       for ( int j=0;j < len;j++)
       {    
		   //注意这里取每一位数的方法
            vert = A[j] % baseValue;//这是得到余数
            vert = vert / (baseValue/10) ; //这才取到每一位上的数
			myVector[ vert ].push_back(A[j]);
       }

	   //将这一遍的排序后的顺序从vector中取出并保存到原数组A，再进行下一次评价
	   //以及清空vector，以便下次排序
	   follow_Slove(A);
	   baseValue = baseValue * 10; //改变求余
	}
	
}

//计算整数的最长位是多少
void cal_bitLen(int* A,int len,int& bitLen)
{  
   int max = -1; //保存最长位
   int temp;
   int count = 1;

   for ( int i=0; i < len ; i++)
   {
        temp = A[i];
		count = 0;

		while ( temp)
		{
			temp = temp/10;
			count++;
		}

		if ( count > max)
		  max = count;
   }
   bitLen = max ; 
}
int main(void)
{  
	int A[6] = {1111,22,22,224,50,0};
	int bitLen;
	cal_bitLen(A,6,bitLen);
	bucket_Sort(A,6,bitLen,10);

	for (int i=0;i<6;i++)
	{
		cout << A[i]<<" ";
	}
	cout<<endl;
	return 0;
}

排序算法-桶排序(基数排序)

相关推荐