局门户网站的建设方案,哪些公司做网站开发,上海电商网站建设,保定百度首页优化基数排序是桶排序的一种#xff0c;算法思路为#xff1a;
利用队列进行数据收发创建一个队列数组#xff0c;数组大小为10#xff0c;每个元素都是一个队列#xff0c;存储取模为1~9的数从低位到高位进行数据收发#xff0c;完成排序适用于数据位不高的情况#xff08…基数排序是桶排序的一种算法思路为
利用队列进行数据收发创建一个队列数组数组大小为10每个元素都是一个队列存储取模为1~9的数从低位到高位进行数据收发完成排序适用于数据位不高的情况若不知道数据集的最大位数则只能往大了猜降低效率
基数排序是不稳定排序算法时间复杂度为K为数据最大位数也可表示为。
虽然基数排序有着非常优秀的效率甚至比快排还快但是由于算法受限于数据的位数因此并不常见。 代码示例假设测试数据数组元素最大位数为3
#define _CRT_SECURE_NO_WARNINGS 1#include iostream
#include queue
using namespace std;// 数据最大位数
#define K 3 // 取模的类别数桶数、基数
#define RADIX 10// 桶
queueint _q[RADIX];// 获取val值对应桶的位置即哈希映射
int GetPos(int a, int k)
{int pos a % RADIX;while (k--){a / RADIX;pos a % RADIX;}return pos;
} // 分发数据将数组数据按模分发到哈希桶上
void Distribute(int* arr, int left, int right, int k)
{for (int i left; i right; i){int pos GetPos(arr[i], k);_q[pos].push(arr[i]);}
} // 收集数据根据队列的特性从哈希桶上收集数据存入数组
void Collect(int* arr)
{int pos 0;for (int i 0; i RADIX; i){while (!_q[i].empty()){arr[pos] _q[i].front();_q[i].pop();}}
} void RadixSort(int* arr, int n)
{int k 0;while (k K){Distribute(arr, 0, n, k);Collect(arr);}
} /*----------测试模块---------- */// 打印数组
void PrintArr(int* arr, int n)
{for (int i 0; i n; i){printf(%4d, arr[i]);} cout endl;
} void TestRadixSort()
{cout 基数排序;int arr[20] {112, 23, 5, 17, 129, 0, 211, 4, 61, 8,511, 51, 25, 10, 210, 111, 3, 5, 18, 6};RadixSort(arr, 20);PrintArr(arr, 20);
} int main()
{TestRadixSort();return 0;
} 运行结果
