排序算法--桶排序(基数排序)
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;}? ??