c++数据结构算法复习基础--13--基数算法
基数排序 - 桶排序
时间复杂度 O(n*d) – d为数据的长度
每次比较一位（个位、十位。。。），所以取值范围就为0-9。
根据该特点，设计桶的概念 – 0号桶、1号桶…
1、思想
1）找出最长的数字，确定要处理的桶的趟数（位数）
2）依次由个位开始处理，把相应位数上的数字，放入相应序号的桶内，
完成后，再按照桶的序号，依次取出桶里面的数据，放回原始数据当中。
3）当处理完所有的位数，最终得到有序的序列。
2、局限性
1）数据类型改变，需要代码较大的修改。
对于之前的代码，如果换成浮点数等其他类型数据，大体代码思路一致。
但是基数算法不行，代码无法做到统一，需要进一步修改。
2）对于数据正负性，要求较高。
之前的代码，数据正负性影响不大，可比较即可。
对于基数排序，需要进一步堆数据进行修改。下文实现的代码，对于负数无法实现。
3、实现过程
1）从左到右依次遍历原始数据，先由个位开始比较。根据每个数据的个位，放入相应的桶中。一次遍历，如下图所示：
2）依次遍历各个桶，将其重新拷贝到原数据。
3）根据十位，依次放入对应桶中。
4）依次取出数据
因为此次数据最大为两位数，所以这次操作，就可以发现数据有序了。
4、核心代码：
1）循环每次取出位上的数字。
2）桶的定义，
需要为二维数组。使用vector<vector<int>>
4、代码实现
#include<iostream>
#include<stdlib.h> //包含随机数函数srand
#include<time.h> //需要用time作为随机数种子
#include<string>
#include<vector>
//基数排序代码
void RadixSort(int arr[], int size)
{
int maxData = arr[0];
//求得数据最大值
for (int i = 1; i < size; i++)
{
if (maxData < arr[i])
{
maxData = arr[i];
}
}
//使用系统自带的函数，求取最大值的位数
int len = to_string(maxData).size();
//定义桶的二维数组
vector<vector<int>> vecs;//这里底层并没有空间
int mod = 10;
int dev = 1;
//处理数据
for (int i = 0; i < len; mod *= 10, dev *= 10, i++) //O(d) d为数据的长度
{
vecs.resize(10);
for (int j = 0; j < size; j++)
{
//得到当前元素第i个位置的数字
int index = arr[j] % mod / dev;
vecs[index].push_back(arr[j]);
}
//依次遍历所有的桶，把元素拷贝回原始的数组当中
int idx = 0;
for (auto vec : vecs)
{
for (int v : vec)
{
arr[idx++] = v;
}
}
//清空桶内元素，方便下次使用
vecs.clear();
}
}
测试
int main()
{
int arr[10];
srand(time(NULL));
for (int i = 0; i < 10; i++)
{
arr[i] = rand() % 100 + 1;
}
for (int v : arr)
{
cout << v << " ";
}
cout << endl;
RadixSort(arr, sizeof(arr) / sizeof(arr[0]));
for (int v : arr)
{
cout << v << " ";
}
cout << endl;
return 0;
}
5、 对于有负数情况下，代码修改
1）桶，需要设计为20个。增加负数存放的位置。
vecs.resize(20);
2）求取最大值位数时，需要增加abs() – 绝对值函数
//求得数据最大值
for (int i = 1; i < size; i++)
{
if (maxData < abs(arr[i]))
{
maxData = abs(arr[i]);
}
}
3） 数据的存放
取得所需位数后，再加10。
负数放于0-9的桶中，正数放于10-19的桶中。
for (int j = 0; j < size; j++)
{
//得到当前元素第i个位置的数字
int index = arr[j] % mod / dev + 10;
vecs[index].push_back(arr[j]);
}
代码实现
//基数排序代码
void RadixSort(int arr[], int size)
{
int maxData = arr[0];
//求得数据最大值
for (int i = 1; i < size; i++)
{
//为了处理负数，使用abs(),取绝对值
if (maxData < abs(arr[i]))
{
maxData = abs(arr[i]);
}
}
//使用系统自带的函数，求取最大值的位数
int len = to_string(maxData).size();
//定义桶的二维数组
vector<vector<int>> vecs;//这里底层并没有空间
int mod = 10;
int dev = 1;
//处理数据
for (int i = 0; i < len; mod *= 10, dev *= 10, i++)
{
vecs.resize(20);//20个桶，为了能处理负数 -9 -- 9
for (int j = 0; j < size; j++)
{
//得到当前元素第i个位置的数字
int index = arr[j] % mod / dev + 10;
vecs[index].push_back(arr[j]);
}
//依次遍历所有的桶，把元素拷贝回原始的数组当中
int idx = 0;
for (auto vec : vecs)
{
for (int v : vec)
{
arr[idx++] = v;
}
}
//清空桶内元素，方便下次使用
vecs.clear();
}
}
测试
