我在使用递归快速排序算法时遇到了一些问题。元素未按正确顺序排序。输入数据也是具有重复条目的字符串。我使用整数来区分升序(1)和降序(-1)排序。枢轴是中间元素。每当比较重复的条目时(compareTo(String s 都将返回 0),如果要比较的字符串的索引大于 other.I 的索引,则我将比较当前索引并返回负数,我不确定到底是什么错误。下面是代码
// Quick sort Algorithm
public void sort(int left, int right)
{
int i = left, j = right;
String mid;
mid = (String)vect.elementAt((left + right)/2);
while (i <= j)
{
// Compare the elements to the left
while ((i < right) &&
(compare((String)vect.elementAt(i), mid) < 0))
i++;
// Compare the elements to the right
while ((j > left) && (compare((String)vect.elementAt(j), mid) > 0))
j--;
if (i <= j)
{
if(i!=j)
swap(i, j);
i++;
j--;
}
}
// Recursively call the sort method until indices cross.
if(left < j)
sort(left, j);
if(i < right)
sort(i, right);
}
/*
* Compare method to compare the elements.
* type = 1, for ascending sort
* type = -1, for descending sort
*/
public int compare(String firstObj, String secondObj)
{
int resCompare = firstObj.compareTo(secondObj)*type;
if(resCompare == 0)
{
int index_firstObj = vect.indexOf(firstObj);
int index_secObj = vect.indexOf(secondObj);
if(index_firstObj < index_secObj)
return -1;
else
return 1;
}
return resCompare;
}
// Swap the elements at i and j.
public void swap(int i, int j)
{
String tmp1 = (String)vect.elementAt(i);
String tmp2 = (String)vect.elementAt(j);
vect.setElementAt(tmp1, j);
vect.setElementAt(tmp2, i);
}
示例:输入= {“ AA”,“ BB”,“ zz”,“ cc”,“ aa”,“ AA”,“ PP”,“ hh”};升序排序输出= {“ AA”,“ AA”,“ BB”,“ PP”,“ aa”,“ cc”,“ hh”,“ zz”};降序排序输出= {“ zz”,“ hh”,“ cc”,“ BB”,“ aa”,“ PP”,“ AA”,“ AA”};
算法中的问题可能不适用于某些其他输入数据的升序排序。因此,在 code/logic 中查找故障的任何帮助都将提前 helpful.Thanks。
解决:无需找到 index_firstObj 和 index_SecondObj。如果 resCompare 为零,则什么也不做。 public int compare(String firstObj,String secondObj){int resCompare = firstObj.compareTo(secondObj)* type;返回 resCompare; }
1 回答
如果我或 j 成为中间人怎么办?而另一个还不是中间?难道不会出现问题吗?您可能需要检查其中之一是否成为中间位置。