成都商城类网站设计,天津做app和网站的公司,网站改版声明,企业管理软件erp系统有哪些基数排序 - 桶排序
时间复杂度 O(n*d) – d为数据的长度
每次比较一位#xff08;个位、十位。。。#xff09;#xff0c;所以取值范围就为0-9。 根据该特点#xff0c;设计桶的概念 – 0号桶、1号桶…
1、思想
1#xff09;找出最长的数字#xff0c;确定要处理的…基数排序 - 桶排序
时间复杂度 O(n*d) – d为数据的长度
每次比较一位个位、十位。。。所以取值范围就为0-9。 根据该特点设计桶的概念 – 0号桶、1号桶…
1、思想
1找出最长的数字确定要处理的桶的趟数位数 2依次由个位开始处理把相应位数上的数字放入相应序号的桶内 完成后再按照桶的序号依次取出桶里面的数据放回原始数据当中。 3当处理完所有的位数最终得到有序的序列。
2、局限性
1数据类型改变需要代码较大的修改。 对于之前的代码如果换成浮点数等其他类型数据大体代码思路一致。 但是基数算法不行代码无法做到统一需要进一步修改。 2对于数据正负性要求较高。 之前的代码数据正负性影响不大可比较即可。 对于基数排序需要进一步堆数据进行修改。下文实现的代码对于负数无法实现。
3、实现过程 1从左到右依次遍历原始数据先由个位开始比较。根据每个数据的个位放入相应的桶中。一次遍历如下图所示 2依次遍历各个桶将其重新拷贝到原数据。 3根据十位依次放入对应桶中。 4依次取出数据 因为此次数据最大为两位数所以这次操作就可以发现数据有序了。
4、核心代码
1循环每次取出位上的数字。 2桶的定义
需要为二维数组。使用vectorvectorint
4、代码实现
#includeiostream
#includestdlib.h //包含随机数函数srand
#includetime.h //需要用time作为随机数种子
#includestring
#includevector//基数排序代码
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();//定义桶的二维数组vectorvectorint 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();//定义桶的二维数组vectorvectorint 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();}}测试
