haitao:
算法问题:字符串数组的快速排序问题,排序算法本身不是问题了,快速排序即可
[阅读: 700] 2006-06-23 03:15:38
算法问题:字符串数组的快速排序问题,排序算法本身不是问题了,快速排序即可
问题是字符串的元素的交互是开销比较大的,
所以,排序时,实际上先建一个个数(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
但是好像有漏洞。。。。
因为可能存在多个这样的“闭包”