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 --  9for (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();}}

测试