只是练习一些排序算法。我尝试实现递归合并排序,但为每个递归调用获取新的枢轴似乎存在问题。
我觉得我的代码应该可以工作...但我是使用 ArrayList 作为数据结构的新手...并且只有数组方面的经验。我需要一个动态大小的数组,因此我使用 ArrayList。
它只是不断地吐出pivot = 1,直到溢出:
pivot: 1
pivot: 1
pivot: 1
pivot: 1
pivot: 1
...
Exception in thread "main" java.lang.StackOverflowError
代码:
import java.util.*;
public class Sorts{
static Sorts run;
List<Integer> initialList = new ArrayList<Integer>();
public Sorts() {
//List<Integer> initialList = new ArrayList<Integer>();
initialList.add(1);
initialList.add(4);
initialList.add(8);
initialList.add(2);
initialList.add(3);
initialList.add(7);
initialList.add(9);
System.out.print("List of values: (");
for (int value: initialList) {
System.out.print(value);
}
System.out.println(")");
//output sorted array
System.out.println("Sorted list: " + mergeSort(initialList));
}
public List<Integer> mergeSort(List<Integer> list) {
if (list.size() <= 1) {
return list;
}
//after each recursion, generate two new sub lists
List<Integer> left = new ArrayList<Integer>();
List<Integer> right = new ArrayList<Integer>();
//generate new pivot for each new list
int middle = list.size()/2;
System.out.println("middle: " + middle);
int i = 0;
for (int x: list) {
if (i < middle) {
left.add(x);
}
else {
right.add(x);
}
i++;
}
//call mergeSort, passing in each new sublist (left, right)
left = mergeSort(left);
right = mergeSort(right);
return mergeLists(left, right);
}
public List<Integer> mergeLists (List<Integer> left, List<Integer> right) {
List<Integer> sortedList = new ArrayList<Integer>();
int i = 0;
while (left.size() > 0 || right.size() > 0) {
if (left.size() > 0 && right.size() > 0) {
if (left.get(i) <= right.get(i)) {
sortedList.add(left.get(i));
}
else {
sortedList.add(right.get(i));
}
}
else if (left.size() > 0) {
sortedList.add(left.get(i));
}
else if (right.size() > 0) {
sortedList.add(right.get(i));
}
}
for (int value : sortedList) {
System.out.println(value);
}
return sortedList;
}
public static void main(String []args){
run = new Sorts();
}
}
有什么想法吗?我是否错误地使用了 ArrayList?
谢谢!
最佳答案
问题是您以错误的方式拆分列表:
for (int i: initialList) {
if (i < pivot) {
left.add(i);
}
else {
right.add(i);
}
}
i
是 initialList
中的元素,而不是元素的索引。将其更改为:
int i = 0;
for (int x: initialList) {
if (i < pivot) {
left.add(x);
}
else {
right.add(x);
}
i++;
}
对于任何反对者:我已经对此进行了测试并且有效:)。
此外,您的合并
算法存在问题。您应该在对元素进行排序时合并两个列表,但您只是插入左侧的值,然后插入右侧的值(但也许可能用于测试目的)。
根据您的编辑,现在您在获取数据透视表时遇到了新问题:
int pivot = list.get(list.size()/2);
这应该与您在原始代码中发布的一样:
int pivot = initialList.size()/2;
请注意,由于 QuickSort 中使用了 pivot
,人们可能会告诉您一些奇怪的建议。您只需在 MergeSort 中使用 middle
或 mid
关于Java - 合并排序未正确选择枢轴,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/15563557/