基数排序
首先来看两个经典引理:
引理1:给定n个d位数,每一个数位可以取k种可能的值。基数排序算法能以 θ(d(n+k))的时间正确地对这些数进行排序。
引理2:给定n个b位数和任何正整数r<=b,randix-sort能在 θ((b/r)(n+2^r))时间内正确地对这些数进行排序。
下面是基数排序的LSD法(最低位优先)程序实现:
#include<iostream> #include<malloc.h> using namespace std; //返回数字的第d位 int getdigit(int num, int d) { int temp = 1; for(int i=0; i<d-1; i++) temp = temp * 10; return (num/temp) % 10; } //输出 void printArr(int arr[], int n) { for(int i=0; i<n; i++) { cout << arr[i] << " "; } cout << endl; } //基数排序算法 void radix_sort(int arr[], int begin, int end, int d) { const int radix = 10; //桶的个数 int count[radix], i, j; int* bucket = (int*)malloc((end-begin+1)*sizeof(int)); //开辟桶空间 //从第1位到第d位,执行d次.按第k位数字大小,把所有的数据放到编号为0-9的桶中 for(int k=1; k<=d; k++) { //初始化 for(i=0; i<radix; i++) { count[i] = 0; } //统计各个桶中元素个数 for(i=begin; i<=end; i++) { count[getdigit(arr[i], k)]++; } //count[i]表示第i个桶的右边界索引 for(i=1; i<radix; i++) { count[i] = count[i] + count[i-1]; } //把数据依次装入桶 for(i=end; i>=begin; i--) //从右向左扫描,保证排序稳定性 { j = getdigit(arr[i], k); //求出关键码的第k位的数字,例如:576的第3位是5 bucket[count[j]-1] = arr[i]; //放入对应的桶中,count[j]-1是第j个桶的右边界索引 --count[j]; //对应桶的装入数据索引减一 } //注意:此时count[i]为第i个桶左边界 //每次分配结束后,将所有桶中的数据从小到大重新收集,为下一次分配做准备 for(i=begin,j=0; i<=end; i++, j++) { arr[i] = bucket[j]; } } free(bucket); } int main() { int num[16] = {73, 2, 931, 4213, 4455, 445314, 3428, 765, 539, 481, 2542, 3, 476, 34237, 3412, 299}; cout<<"原数据如下:"<<endl; printArr(num,16); radix_sort(num, 0, 15, 6); cout<<"排序后数据如下:"<<endl; printArr(num, 16); return 0; }下面简要讨论一下3中线性时间排序:
1. 基数排序是否比基于比较的排序算法(例如快速排序)更好呢?实际上哪一种排序算法更好取决于底层机器的实现特性(例如:快速排序通常比基数排序更为有效的利用硬件缓存),同时还取决于输入的数据;
2. 利用计数排序作为中间稳定排序的基数排序不是原地排序,而很多θ(nlgn)时间的比较排序算法则可以做到原地排序。因此,当内存容量比较宝贵时,像快速排序这样的原地排序算法可能更为可取;
3. 基数排序是在假设输入是由一个小范围内的整数构成,而桶排序则假设输入的元素均匀地分布在区间[0, 1)上。
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。