Java自顶向下归并排序 – Stackoverflow错误

huangapple 未分类评论45阅读模式
英文:

Java Top-Down Merge Sort - Stackoverflow Error

问题

以下是你要的翻译部分:

import java.util.ArrayList;
import java.util.Random;

public class Main {
    public static void main(String[] args) {
        Random r = new Random();
        ArrayList<Integer> numbers = new ArrayList<Integer>();
        for (int i = 1; i <= 15; i++) {
            numbers.add(r.nextInt(100));
        }
        numbers = mergeSort(numbers);
        System.out.println(numbers);
    }

    public static ArrayList<Integer> mergeSort(ArrayList<Integer> m) {
        if (m.size() <= 1) {
            return m;
        }
        ArrayList<Integer> left = new ArrayList<Integer>();
        ArrayList<Integer> right = new ArrayList<Integer>();
        for (Integer x : m) {
            if (m.indexOf(x) < (m.size()) / 2)
                left.add(x);
            else {
                right.add(x);
            }
        }
        left = mergeSort(left);
        right = mergeSort(right);
        return merge(left, right);
    }

    private static ArrayList<Integer> merge(ArrayList<Integer> l, ArrayList<Integer> r) {
        ArrayList<Integer> result = new ArrayList<Integer>();
        while (l.size() > 0 && r.size() > 0) {
            if (l.get(0) <= r.get(0)) {
                result.add(l.get(0));
                l.remove(0);
            }
            else {
                result.add(r.get(0));
                r.remove(0);
            }
        }
        while (l.size() > 0) {
            result.add(l.get(0));
            l.remove(0);
        }
        while (r.size() > 0) {
            result.add(r.get(0));
            r.remove(0);
        }
        return result;
    }
}
英文:

I am trying to implement the top-down merge sort algorithm in Java, using the pseudocode from Wikipedia.

My problem is that my code sometimes throws a StackOverflowError, but not always. I have checked that my code matches the pseudocode several times and cannot find what is wrong with it.

Here is my Java code:

import java.util.ArrayList;
import java.util.Random;

public class Main {
	public static void main(String[] args) {
		Random r = new Random();
		ArrayList&lt;Integer&gt; numbers = new ArrayList&lt;Integer&gt;();
		for (int i = 1; i &lt;= 15; i++) {
			numbers.add(r.nextInt(100));
		}
		numbers = mergeSort(numbers);
		System.out.println(numbers);
	}

	public static ArrayList&lt;Integer&gt; mergeSort(ArrayList&lt;Integer&gt; m) {
		if (m.size() &lt;= 1) {
			return m;
		}
		ArrayList&lt;Integer&gt; left = new ArrayList&lt;Integer&gt;();
		ArrayList&lt;Integer&gt; right = new ArrayList&lt;Integer&gt;();
		for (Integer x : m) {
			if (m.indexOf(x) &lt; (m.size()) / 2)
				left.add(x);
			else {
				right.add(x);
			}
		}
		left = mergeSort(left);
		right = mergeSort(right);
		return merge(left, right);
	}

	private static ArrayList&lt;Integer&gt; merge(ArrayList&lt;Integer&gt; l, ArrayList&lt;Integer&gt; r) {
		ArrayList&lt;Integer&gt; result = new ArrayList&lt;Integer&gt;();
		while (l.size() &gt; 0 &amp;&amp; r.size() &gt; 0) {
			if (l.get(0) &lt;= r.get(0)) {
				result.add(l.get(0));
				l.remove(0);
			}
			else {
				result.add(r.get(0));
				r.remove(0);
			}
		}
		while (l.size() &gt; 0) {
			result.add(l.get(0));
			l.remove(0);
		}
		while (r.size() &gt; 0) {
			result.add(r.get(0));
			r.remove(0);
		}
		return result;
	}
}

答案1

得分: 2

你的算法在存在重复元素时会出问题,因为 indexOf 只会返回第一个元素的索引。改用基于索引的 for 循环。 <sup>示例</sup>

for (int i = 0; i < m.size(); i++) {
    if (i < (m.size()) / 2)
        left.add(m.get(i));
    else {
        right.add(m.get(i));
    }
}
英文:

Your algorithm encounters issues when there are duplicate elements, as indexOf will only return the index of the first one. Use a index-based for loop instead. <sup>Demo</sup>

for (int i = 0; i &lt; m.size(); i++) {
    if (i &lt; (m.size()) / 2)
        left.add(m.get(i));
    else {
        right.add(m.get(i));
    }
}

答案2

得分: 0

在mergeSort方法中,需要稍微修改for循环,然后再次尝试。

for (int i = 0; i < m.size() / 2; i++)
  left.add(m.get(i));
for (int i = m.size() / 2; i < m.size(); i++)
  right.add(m.get(i));
英文:

In the mergeSort method need to change the for loop little bit and try again.

for (int i=0;i&lt; m.size()/2;i++)
  left.add(m.get(i));
for (int i=m.size()/2;i&lt; m.size();i++)
  right.add(m.get(i));

huangapple
  • 本文由 发表于 2020年7月27日 03:36:21
  • 转载请务必保留本文链接:https://java.coder-hub.com/63104826.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定