中国开发网: 论坛: 程序员情感CBD: 贴子 347882
haitao
算法问题:字符串数组的快速排序问题,排序算法本身不是问题了,快速排序即可
算法问题:字符串数组的快速排序问题,排序算法本身不是问题了,快速排序即可
问题是字符串的元素的交互是开销比较大的,
所以,排序时,实际上先建一个个数(n)相同的整数数组,里面的元素就是各个字符串的序号
开始时,分别是从1..n,排序时交互的是这个整数数组的元素
排完序,字符串数组还没任何变化,只是整数数组里的值好像乱了,
实际上按它们的值作编号找对应的字符串,就得到一个排序了的字符串数组

现在的问题是,有了这个“乱”的整数数组后,要求以最小的开销重排字符串数组,
使得它们是排序的。。。
如果允许拷贝一个字符串数组,那是很简单,如果不允许呢--因为这个字符串数组比较大,空间限制不允许?

前面说的是需求的来源,实际上,需求可以简化为:
有字符串数组和整数数组,
char s[0..1000][100000]
int p[0...1000]
整数数组的初始值为0至1000的顺序值,然后随机进行了n次的任意2个元素的互相交互其值
要求按整数数组的元素值作字符串数组的序号,重新排序字符串数组
如:
s[]='a','b','c','d','e','f'
p[]=3,0,5,2,4,1
要求处理后:
s[]==d,a,f,c,d,b

我原来的做法是,先定义一个string t
pp=p[0]
t=s[pp]
for i=1 to 元素个数-1 do
{
s[pp]=s[p[pp]]
pp=p[pp]
}
s[pp]=t
但是好像有漏洞。。。。
因为可能存在多个这样的“闭包”
我的blog:http://szhaitao.blog.hexun.com & http://www.hoolee.com/user/haitao
--以上均为泛泛之谈--
不尽牛人滚滚来,无边硬伤纷纷现 人在江湖(出来的),哪能不挨刀(总归是要的)
网络对话,歧义纷生;你以为明白了对方的话,其实呢?

您所在的IP暂时不能使用低版本的QQ,请到:http://im.qq.com/下载安装最新版的QQ,感谢您对QQ的支持和使用

相关信息:


欢迎光临本社区,您还没有登录,不能发贴子。请在 这里登录