基数排序是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表达字符串(比如名字或日期)和特定格式的浮点数,所以基数排序也不是只能使用于整数。
(1)什么是基数排序?
1. 通过键值得各个位的值,将要排序的元素分配至一些桶中,达到排序的作用
2. 基数排序法是属于稳定性的排序,基数排序法是效率高的稳定排序法
3. 基数排序是桶排序的扩展
(2)实现原理
将所有待比较数值(自然数)统一为同样的数位长度,数位较短的数前面补零。然后,从最低位开始,依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。
(3)LSD 基数排序动图演示
LSD 基数排序动图
(4)C语言代码实现如下:
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <math.h> #include <time.h> //定义基数为10进制 #define radix 10 //交换数值 void swap(int *a,int *b) { int temp = *a; *a = *b; *b = temp; } //打印数组 void printArray(char msg[],int arr[],int len){ printf("%s:",msg); for (int i = 0; i < len; i++){ printf("%d ", arr[i]); } printf("\n"); } //基数排序 void radix_sort(int a[],int len){ int maxvalue=a[0],minvalue=a[0]; for(int x=0;x<len;x++){ maxvalue=a[x]>maxvalue?a[x]:maxvalue; minvalue=a[x]<minvalue?a[x]:minvalue; } int* temp = (int*)malloc(len*sizeof(int)); //获取最大位数 int n=1; int d = maxvalue-minvalue; while(d>=10){ d=d/10; n++; } printf("总遍历位数:%d,最小值:%d,最大值:%d\n",n,minvalue,maxvalue); //要获取的位 int divide=1; for(int i=1;i<=n;i++){ //初始化计数器 int counter[radix]={0}; for(int j=0;j<len;j++){ //找出a[j]相对minvalue值的对应的位divide的值 int pos = ((a[j]-minvalue)/divide)%radix; //a[j]换算成计数器数组下标pos并自增 counter[pos]++; } //使用累加(counter[n]=counter[n]+counter[n-1],有点类似斐波那契数列)计算出元素所在位置,保证结果有序 for(int j=1;j<10;j++){ counter[j]=counter[j]+counter[j-1]; } //倒序遍历数组a,可以保持结果稳定性 for(int j=len-1;j>=0;j--){ //将a[j]映射到计数器下标pos,counter[pos]就是a[j]在新数组的位置 int pos=((a[j]-minvalue)/divide)%radix; //获取元素位置mappos,--counter[pos]:每放一个元素到数组temp,counter[pos]值自减,保证结果稳定有序 int mappos=(--counter[pos]); temp[mappos]=a[j]; } //把temp有序数组赋值给a for(int j=0;j<len;j++){ a[j]=temp[j]; } printf("遍历位数%d:\n",divide); for(int j=0;j<len;j++){ printf("a[%d]=%d,a[%d]-%d=%d\n",j,a[j],j,minvalue,a[j]-minvalue); } printf("\n"); //获取数值的下个位,比如个位数,下个是十位数 divide=divide*radix; } free(temp); } int main() { int len=10; int arr[len]; srand((unsigned)time(NULL)); //随机生成长度为"len"的数组 for(int i=0;i<len;i++){ arr[i]=rand()%200; } printArray("未排序前",arr,len); radix_sort(arr,len); printArray("基数排序",arr,len); //防止windows下控制台窗口闪退 int s; scanf("%d",&s); return 0; }
如果我们编译并运行上述程序,那么它应该产生以下结果:
未排序前:80 155 178 14 59 36 195 15 141 143 总遍历位数:3,最小值:14,最大值:195 遍历位数1: a[0]=14,a[0]-14=0 a[1]=155,a[1]-14=141 a[2]=195,a[2]-14=181 a[3]=15,a[3]-14=1 a[4]=36,a[4]-14=22 a[5]=178,a[5]-14=164 a[6]=59,a[6]-14=45 a[7]=80,a[7]-14=66 a[8]=141,a[8]-14=127 a[9]=143,a[9]-14=129 遍历位数10: a[0]=14,a[0]-14=0 a[1]=15,a[1]-14=1 a[2]=36,a[2]-14=22 a[3]=141,a[3]-14=127 a[4]=143,a[4]-14=129 a[5]=155,a[5]-14=141 a[6]=59,a[6]-14=45 a[7]=178,a[7]-14=164 a[8]=80,a[8]-14=66 a[9]=195,a[9]-14=181 遍历位数100: a[0]=14,a[0]-14=0 a[1]=15,a[1]-14=1 a[2]=36,a[2]-14=22 a[3]=59,a[3]-14=45 a[4]=80,a[4]-14=66 a[5]=141,a[5]-14=127 a[6]=143,a[6]-14=129 a[7]=155,a[7]-14=141 a[8]=178,a[8]-14=164 a[9]=195,a[9]-14=181 基数排序:14 15 36 59 80 141 143 155 178 195
1720 | 数据结构-基数排序 |
知识点标签:排序
本文固定URL:https://www.dotcpp.com/course/938
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程,并配有习题和答疑,点击了解:
一点编程也不会写的:零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码?手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程:算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程