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

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;}

?