首页 > 代码库 > 基本排序系列之基数排序
基本排序系列之基数排序
基数排序
一、基数排序是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。
其实现原理:将所有待比较数值(正整数)统一为同样的数位长度,数位较短的数前面补零。然后,从最低位开始,依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。
二、具体操作:此排序的真正实现是通过队列的装置,先进先出的原理,通过把个位,十位,百位,等其他进制也一样,放到不同的队列中(俗称桶)再按照先进先出的原理得到新的序列,在通过百位将其重新入桶回收等操作有获取新的序列,按此以来得到最终的序列便是排序好的序列。
三、基数排序不同于其他排序,一般我们见到的排序都是通过比较得到的,快排,归并都不例外,这个排序对于整数有特别好的效率而且也是一种稳定的排序。对于基数排序算法中要m次的n个节点来存放临时元素所以给予链式队列的基数排序,其算法复杂度为O(n)。对于顺序队列和链式队列基数排序算法的时间复杂度相同也为O(2mn)。
接下来我们以十进制:
500,342,45,666,006,841,429,134,78,264为例:
第一次:
0 | 500 | ||
1 | 841 | ||
2 | 342 | ||
3 | |||
4 | 134 | 264 | |
5 | 45 | ||
6 | 666 | 006 | |
7 | |||
8 | 78 | ||
9 | 429 |
第二次:
0 | 500 | 006 |
1 | ||
2 | 429 | |
3 | 134 | |
4 | 841 | 342 45 |
5 | ||
6 | 264 | 666 |
7 | 78 | |
8 | ||
9 |
第三次:
0 | 006 | 45 78 |
1 | 134 | |
2 | 264 | |
3 | 342 | |
4 | 429 | |
5 | 500 | |
6 | 666 | |
7 | ||
8 | 841 | |
9 |
这就得到了排序。
排序段代码:
/** *基数排序的操作方法实现Radix_sort() *SNode *S 用来接收tub的地址 *@param int a[] 表示接受要排序的数组 *@param int length 表示该要排序的数组的长度 *@param int d 表示进制,这里假设是十进制 *@param int m 表示的是要比较的数的最大的位数 *@return 无 */ void Radix_sort(DataType a[],int length ,int d,int m){ int power = 1,k; //用来计算装桶的次数 int count= 1; //把d个队列定义成动态数组 Queue *tub ; tub = (Queue *)malloc(sizeof(Queue)*d); //对每一个队列进行初始化 cout<<"_____________________________________________"<<endl; for(int i = 0;i <d;i++){ QueueInitiate(&tub[i]); } cout<<"_____________________________________________"<<endl; //对桶内进行m此的放入和收回 for(int i = 0;i <m;i++){ if(i == 0){ power = 1; }else{ power *=d; } //将数据元素按照关键字第k位的数值放到相应的队列中 cout<<"第"<<count<<"次装桶过程!"<<endl; cout<<"_____________________________________________"<<endl; for(int j = 0;j <length ;j++){ //在接收了传进来的进制和位数后我们必须对每一个数进行处理 k =a[j]/power-(a[j]/(power *d))*d; QueueAppend(&tub[k],a[j]); } cout<<"_____________________________________________"<<endl; //顺序的回收队列中的数据元素到a的数组中 k = 0; cout<<"第"<<count<<"次回收装桶后的元素!"<<endl; cout<<"_____________________________________________"<<endl; for(int j = 0;j < d;j++){ while( QueueNotEmpty(tub[j])!=0){ QueueDelete(&tub[j],&a[k]); cout<<"回收装桶元素成功!"<<endl; k++; } /* for(int i = 0;i <d ;i++){ cout<<">>>>>第"<<i+1<<"个元素:"<<a[i]<<endl; }*/ if(j==d){ cout<<"回收装桶元素成功!"<<endl; } } count++; cout<<"_____________________________________________"<<endl; } }
插入段代码:
<span style="font-size:18px;">/** *队列的插入,即桶的数据的装桶操作 *@param Queue *Q用来接收传进来的地址 *@param int num 表示要入桶的数 *return Queue * */ Queue *QueueAppend(Queue *Q,int num){ /** *这里我们首先得为rear ,front申请空间并初始化 * */ /* Queue *Q; *判断有无空间可申请,并是否申请成功 *if(Q != NULL){ * free(Q); * Q =NULL; *} *Q = (Queue *)malloc(sizeof(Queue)); *if(Q !=NULL){ * cout<<"Q-头节点和尾节点申请空间成功!"<<endl; *}else{ * cout<<"内存空间不足!"<<endl; * return ; *} *初始化头节点和尾节点 *Q->rear = NULL; *Q->front = NULL; */ /** *这里判断R是否为空并释放空间 *然后对其申请空间按 */ SNode *p =NULL; if(p != NULL){ free(p); p =NULL; } p = (SNode *)malloc(sizeof(SNode)); if(p !=NULL){ cout<<"申请空间成功!"<<endl; }else{ cout<<"内存空间不足!"<<endl; return Q; } p->data = http://www.mamicode.com/num;//这里得放其位数如个位,十位,百位>
回收段代码:/** *链式队列中的元素的删除 *@param Queue *q 用来接收要回收的元素的地址 *@param DataType *d 用来存储储存收回的元素 *@return int */ int QueueDelete(Queue *q,DataType *d){ SNode *p; /** *判断内存中是否有数据,有就输出,没有返回0 * */ if(q->front == NULL){ cout<<"此时队列中无元素出列!"<<endl; return 0; }else{ *d = q->front->data; p = q->front; q->front= q->front->next; } if(q->front == NULL){ q->rear = NULL; } free(p);//释放节点内存空间 return 1; }全部代码:/** *基数排序原理就是利用桶也就是队列来排序的 *@author 菜鸟 *@version 2014.6.15 */ #include <iostream> #include <windows.h> #include <malloc.h> #define MaxSize 100 using namespace std; typedef int DataType; //定义节点用来做链式队列 typedef struct Node{ DataType data; struct Node *next; }SNode; //定义一个结构体将队列的头尾指针放在一起 typedef struct{ SNode *rear; SNode *front; }Queue; //初始化头节点与尾节点 void QueueInitiate(Queue *q){ q->rear = NULL; q->front = NULL; cout<<"成功初始化!"<<endl; } //判断队列非空 int QueueNotEmpty(Queue q){ if(q.front== NULL){ return 0; }else { return 1; } } /** *队列的插入,即桶的数据的装桶操作 *@param Queue *Q用来接收传进来的地址 *@param int num 表示要入桶的数 *return Queue * */ Queue *QueueAppend(Queue *Q,int num){ /** *这里我们首先得为rear ,front申请空间并初始化 * */ /* Queue *Q; *判断有无空间可申请,并是否申请成功 *if(Q != NULL){ * free(Q); * Q =NULL; *} *Q = (Queue *)malloc(sizeof(Queue)); *if(Q !=NULL){ * cout<<"Q-头节点和尾节点申请空间成功!"<<endl; *}else{ * cout<<"内存空间不足!"<<endl; * return ; *} *初始化头节点和尾节点 *Q->rear = NULL; *Q->front = NULL; */ /** *这里判断R是否为空并释放空间 *然后对其申请空间按 */ SNode *p =NULL; if(p != NULL){ free(p); p =NULL; } p = (SNode *)malloc(sizeof(SNode)); if(p !=NULL){ cout<<"申请空间成功!"<<endl; }else{ cout<<"内存空间不足!"<<endl; return Q; } p->data = http://www.mamicode.com/num;//这里得放其位数如个位,十位,百位>代码经验证过!
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。