频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
基本排序系列之基数排序
2014-06-18 10:59:29      个评论    来源:基本排序系列之基数排序  
收藏   我要投稿

基数排序


一、基数排序是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。

其实现原理:将所有待比较数值(正整数)统一为同样的数位长度,数位较短的数前面补零。然后,从最低位开始,依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。


二、具体操作:此排序的真正实现是通过队列的装置,先进先出的原理,通过把个位,十位,百位,等其他进制也一样,放到不同的队列中(俗称桶)再按照先进先出的原理得到新的序列,在通过百位将其重新入桶回收等操作有获取新的序列,按此以来得到最终的序列便是排序好的序列。


三、基数排序不同于其他排序,一般我们见到的排序都是通过比较得到的,快排,归并都不例外,这个排序对于整数有特别好的效率而且也是一种稳定的排序。对于基数排序算法中要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

得到:500 841 342 134 264 45 666 006 78 429

第二次:

0 500 006
1

2 429
3 134
4 841 342 45
5

6 264 666
7 78
8

9

得到: 500 006 429 134 841 342 45 264 666 78

第三次:

0 006 45 78
1 134
2 264
3 342
4 429
5 500
6 666
7

8 841
9

得到:006 45 78 134 264 342 429 500 666 841

这就得到了排序。


排序段代码:

/**
*基数排序的操作方法实现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<<"_____________________________________________"<>>>>第"<

插入段代码:

/**
*队列的插入,即桶的数据的装桶操作
*@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-头节点和尾节点申请空间成功!"<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<<"申请空间成功!"<data = num;//这里得放其位数如个位,十位,百位
        p->next = NULL;//到此已经成功的创建了一个新的节点
		/**
	     *将新的节点插入队列的末尾 
		 *
		 */ 
		 if(Q->rear != NULL){
			    Q->rear->next = p;
				Q->rear = p;
		  }
		 if(Q->front == NULL){
			    Q->rear = p;
				Q->front = p;
		 }
		 cout<<"装桶成功!"<

回收段代码:

/**
*链式队列中的元素的删除
*@param Queue *q 用来接收要回收的元素的地址
*@param DataType *d  用来存储储存收回的元素
*@return int 
*/
 int QueueDelete(Queue	*q,DataType	*d){
 	SNode *p;
    /**
	 *判断内存中是否有数据,有就输出,没有返回0 
	 *
	 */ 
	if(q->front == NULL){
			cout<<"此时队列中无元素出列!"<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 
#include 
#include 
#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<<"成功初始化!"<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<<"申请空间成功!"<data = num;//这里得放其位数如个位,十位,百位
        p->next = NULL;//到此已经成功的创建了一个新的节点
		/**
	     *将新的节点插入队列的末尾 
		 *
		 */ 
		 if(Q->rear != NULL){
			    Q->rear->next = p;
				Q->rear = p;
		  }
		 if(Q->front == NULL){
			    Q->rear = p;
				Q->front = p;
		 }
		 cout<<"装桶成功!"<front == NULL){
			cout<<"此时队列中无元素出列!"<front->data;
		 p = q->front;
		 q->front= q->front->next;
	}
    if(q->front == NULL){
 	     q->rear = NULL;	 
 	}
	free(p);//释放节点内存空间 
    return 1; 							
} 
/**
 *输出函数
 *@param int a[]用来接收数组
 *@param int n  表示数组的长度
 *@return 无
 */
 void out_put(int a[],int n){
	 cout<<"_____________________________________________"<>>>>第"<代码经验证过!













点击复制链接 与好友分享!回本站首页
相关TAG标签 基数
上一篇:求二维数组中子数组和中最大的值,及子数组
下一篇:HDU 3037 Saving Beans (Lucas定理)
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站