北安网站设计,好的ppt模板免费下载网站,网站开发河南,中英文切换的网站怎么做的# 基本思想基数排序(radix sort)#xff0c;同样时一种非比较的内部排序算法#xff0c;主要基于多关键字排序的思想进行排序#xff0c;它将单个关键字按照基数分成“多个关键字”进行排序。例如整数789是一个关键字#xff0c;可以按照十进制位划分多关键字#xff08;十… # 基本思想基数排序(radix sort)同样时一种非比较的内部排序算法主要基于多关键字排序的思想进行排序它将单个关键字按照基数分成“多个关键字”进行排序。例如整数789是一个关键字可以按照十进制位划分多关键字十进制数字取值0-9所以基数是10从高到低分为三个关键字“7、8、9”这样对每位关键字进行排序即可得到排序。基数排序对关键字数据元素有要求一般是等长的整数和字符串。基数排序是一种稳定的内部排序算法。时间复杂度是O(d*(n radix)d是关键字位数radix是基数。例如对于(21, 12, 31, 10, 30)进行基数排序可以按照以下步骤进行。1.根据每一位数字划分组最多10组因为基数为10代表数字0-9。2.首先看十位数字从小到大排序后可以得到(12,10)(21)(31,30)三组数数字相同的分为一组。3.再看个位数字对上述三组分别进行从小到大排序后得到(10,12)(21)(30,31)最终得到有序序列。以上基数排序采用最高位优先方法从高位到低位进行划分同样还可以采用从最低位开始排序。最高位优先法排序时候必须不断对划分子序列进行排序编程实现复杂最低位优先方法可以每次从低位开始对整个序列进行排序无需划分。# 代码实现1.实现基于“链式基数排序”方法具体理论参见数据结构相关书籍。2.基数排序关键操作是分配和收集分配就是每次根据关键字分组到链队列中收集是将分组链队列排序后的数据记录整理成完整的链表。3.使用数组实现静态链表存放待排序的数据记录。4.需要两个数组辅助大小为基数一个数组负责指向链队列头部一个数组指向链队列尾部。/* 名称 C语言必学的12个排序算法 功能 链基数排序 环境 Windows 10 Dev-C 编译 作者 一只会C的猫 公众号 C语言大全(coderpointer) 时间 2020.7.25 */#include#include// 对整数基数为10 #define RADIX 10// 最大元素个数#define MAX_LENGTH 100 // 静态链表结点 struct node{ int data; // 下标代替指针表示下一个结点 int next;}; // 获取关键字每一位数字// i1 表示个位i2表示十位 int get_digit(int n, int loc){ int i; for(i1; i n n/10; return n%10;} // 分配和收集操作void distri_collect(struct node r[], int length, int loc){ // 辅助数组,指向每个链队列 int front[RADIX], rear[RADIX]; // 初始为空 int i; for(i0; i { front[i] 0; rear[i] 0; } // 遍历整个静态链表按照关键字分配到各链队列 int p,digit; for(p r[0].next ; p!0 ; pr[p].next) { digit get_digit(r[p].data, loc); // 链队列为空时直接插入 if(front[digit] 0) front[digit] p; else { // 插入尾部 r[rear[digit]].next p; } rear[digit] p; } // 收集合并 // 找到第一个1非空链队列 for(i0; front[i] 0 i r[0].next front[i]; p rear[i]; while(iRADIX) { // 寻找下一个非空链队列 for(i ;iRADIX-1 front[i]0; i); // 对最后一个元素特殊处理 if(iRADIX) break; if(front[i]) { // 链接两个非空链队列 r[p].next front[i]; p rear[i]; } } r[p].next 0;}void radix_sort(int a[], int length, int k){ // 创建静态链表保存数据 // r[0]表示头结点 struct node r[MAX_LENGTH]; // 初始化链表为空 r[0].next 0; int i; for(i0; i { r[i].next i 1; r[i 1].data a[i]; } // 链表最后一个元素指向0表示链表结束 r[i].next 0; // 对关键字按照从低位到高位进行排序 for(i1; ik; i ) distri_collect(r, length, i); // 将排序后的结果复制到原数组a中 nbs声明本文于网络整理版权归原作者所有如来源信息有误或侵犯权益请联系我们删除或授权事宜。
