基数排序笔记

基数排序是一种非比较型排序算法他根据数字的每一位来排序通常用于整数排序通过若干次“分配”“收集”来实现算法思想1获取待排序元素最大值并确定其位数2从最低位开始依次对所有元素“分配”和“收集”操作3在每一位上根据该位上的数字的值将元素分配到相应的桶里十进制就建十个桶4对每个桶的元素顺序排序重复上述步骤直到所有位都进行了排序演示时间复杂度O(d(nr)),d是数字位数n是待排元素数量r是基数位数较少效率较高空间复杂度需要额外空间具体空间取决于桶的数量和存储桶的方式很容易排有固定宽度的数字序列。int maxbit(int data[], int n) //辅助函数求数据的最大位数{int maxData data[0]; /// 最大数/// 先求出最大数再求其位数这样有原先依次每个数判断其位数稍微优化点。for (int i 1; i n; i){if (maxData data[i])maxData data[i];}int d 1;int p 10;while (maxData p){//p * 10; // Maybe overflowmaxData / 10;d;}return d;/* int d 1; //保存最大的位数int p 10;for(int i 0; i n; i){while(data[i] p){p * 10;d;}}return d;*/}void radixsort(int data[], int n) //基数排序{int d maxbit(data, n);int *tmp new int[n];int *count new int[10]; //计数器int i, j, k;int radix 1;for(i 1; i d; i) //进行d次排序{for(j 0; j 10; j)count[j] 0; //每次分配前清空计数器for(j 0; j n; j){k (data[j] / radix) % 10; //统计每个桶中的记录数count[k];}for(j 1; j 10; j)count[j] count[j - 1] count[j]; //将tmp中的位置依次分配给每个桶for(j n - 1; j 0; j--) //将所有桶中记录依次收集到tmp中{k (data[j] / radix) % 10;tmp[count[k] - 1] data[j];count[k]--;}for(j 0; j n; j) //将临时数组的内容复制到data中data[j] tmp[j];radix radix * 10;}delete []tmp;delete []count;}