gpt4 book ai didi

java - 字典顺序快速排序

转载 作者:塔克拉玛干 更新时间:2023-11-03 06:32:02 24 4
gpt4 key购买 nike

我尝试使用 Java 中的快速排序算法按字典顺序对 Strings 数组进行排序。该数组使用 Scanner 通过终端读取并保存在 ArrayList 中。此 ArrayList 后来被转换为一个数组,我(尝试)在其中应用快速排序算法。我有两种方法:

private static void sortA(String[] s, int start, int end) {
if (end > start) {
int pivot = partition(s, start, end);
sortA(s, start, pivot - 1);
sortA(s, pivot + 1, end);
}
}

private static int partition(String[] s, int start, int end) {
String pivot = s[end];
int left = start;
int right = end;
String temp = "";
do {
while ((s[left].compareTo(pivot) <= 0) && (left < end))
left++;
while ((s[right].compareTo(pivot) > 0) && (right > start))
right--;
if (left < right) {
temp = s[left];
s[left] = s[end];
s[right] = temp;
printRow(s);

}
} while (left < right);
temp = s[left];
s[left] = s[end];
s[end] = temp;
return left;
}

代码似乎随机地工作正常然后突然就不行了。例如,数组 {"java", "application", "system"} 可以很好地排序为 {"application", "java", "system"}。数组{"library", "content", "bin"}排序为{"bin", "library", "contents"},不是字典序命令。当然,计算机不会随机工作,所以我的代码一定有问题。我试图在纸上找出一个例子,但后来我会发现一些完全错误的东西。但是,我的代码基于对双数组进行排序的快速排序实现,因此我认为我没有犯大的推理错误。提前致谢。

最佳答案

您以错误的方式拆分数组:正确的拆分是 "pivot-1""pivot"

sortA(s, start, pivot-1);
sortA(s, pivot, end);

关于java - 字典顺序快速排序,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/13351538/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com