频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
算法之旅,直奔排序 基数排序
2014-02-16 11:43:09      个评论    来源:算法之旅,直奔排序 基数排序  
收藏   我要投稿

基数排序(radix sort)

真言

宿舍很冷,但是为了将来,什么苦都得忍着,忍方可成大事。

主题

给一堆相同具有相同位数的数排序。这些数有一个共同的特点具有相同的位数。

思路

举个例子呗,例子最好理解了。

比如有如下数据,{329,457,657,839,436,720,355}.这些数字都是三位的,也就是具有相同的位数。

我们知道,对于一位数字只能是从0~9里的一个,一共有十种可能,对于单位的数字我们可以用长度为十的哈希表(开放地址的链表)去存储数据,这样我们的数据就可以存起来了。

算法演示过程

\
\
\
\


时间复杂度(n*m),n为数据量,m为数字的位数。


实验

程序结果截图 \

代码(只供参考)

代码一年前写的,很水。。。
data.txt
329/457/657/839/436/720/355/

test.cpp
#include 
#include 
#include 
using namespace std ;


int const size = 7;
int const bit = 3 ;

class radix_sort
{
	int * Aint ;

public:
	// function:构造函数;
	radix_sort(void);
	// function:get data from file;
	void dataReader();
	// function:sort the data;
	void sort();
	// function:show the data;
	void datashow();
	// line is the line num;
	void tableinert(int (&T)[10][size],int line,int data);
	// function: save data out to file;
	void datasave();
	// function:析构函数;
	~radix_sort(void);
};


// function:构造函数;
radix_sort::radix_sort(void)
{
	Aint = new int[size] ;

}

// function:get data from file;
void radix_sort::dataReader()
{
	ifstream fileReader ;
	fileReader.open("data.txt");

	int i= 0 ;
	char c;
	while(i>Aint[i]>>c;
		i++;
	}

	cout<<"read over "<tableinert(table,mod,Aint[i]);
			}

			i = 0 ;
			// use time to get space;
			// table is saved to Aint;
			for( k = 0; k<10;k++) 
			{
				num = 0;
				while(table[k][num] != -1)
				{
					Aint[i++]=table[k][num] ;
					table[k][num] = -1 ;
					num++;
				}
			}
			cout<<"the first time:"<datashow();
			if(i!= size) 
			{
				cout<<"error"<dataReader();
	RS->datashow();
	RS->sort();
	RS->datasave();

	delete RS ;
	system("pause");
	return 0;
}




点击复制链接 与好友分享!回本站首页
相关TAG标签 基数 算法 之旅
上一篇:HDU2068 RPG的错排
下一篇:HDU2067 小兔的棋盘
相关文章
图文推荐
点击排行

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

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