Java 合并排序算法错误 - 未排序 [英] Java Merge Sorting Algorithm Error - Not Sorting
问题描述
我不明白为什么我的使用 ArrayLists 的 Merge Sort 程序算法不起作用......如果伙计们和女孩们能帮我弄清楚那将是惊人的！！打印所需的格式需要为每个数字添加标签，并每 20 个数字换行.我的程序也仅限于标准 Java 包.可以在此处找到示例输入和输出.这是我的代码:
I can't figure out why my algorithm for a Merge Sort program using ArrayLists won't work... If guys and gals could help me figure it out that would be amazing!! The format required for printing needs to be tabbed every number and place on a new line every 20 numbers. My program has also been limited to the standard Java packages. Sample input and output can be found here. Here's my code:
import java.io.*;
import java.util.*;
public class MergeSort {
public static void main(String[] args) throws IOException{
Scanner in = new Scanner(System.in);
Random r = new Random();
int size, largestInt, holder;
System.out.println("How many integers would you like me to create?");
size = in.nextInt();
ArrayList<Integer>list = new ArrayList<Integer>(size);
System.out.println("What would the largest integer be?");
largestInt = in.nextInt();
for(int i = 0; i < size; i++){
holder = r.nextInt(largestInt + 1);
list.add(holder);
}
mergeSort(list);
for (int j = 0; j < list.size(); j++) {
if(j == 19 || j == 39 || j == 59 || j == 79 || j == 99 || j == 119 || j == 139 || j == 159 || j == 179 || j == 199){
System.out.print(list.get(j));
System.out.println();
}
else{
System.out.print(list.get(j) + "\t");
}
}
}
static void mergeSort(ArrayList<Integer> list) {
if (list.size() > 1) {
int q = list.size()/2;
ArrayList<Integer> leftList = new ArrayList<Integer>();
for(int i = 0; i >0 && i <= q; i++){
leftList.add(list.get(i));
}
ArrayList<Integer> rightList = new ArrayList<Integer>();
for(int j = 0; j > q && j < list.size(); j++){
rightList.add(list.get(j));
}
mergeSort(leftList);
mergeSort(rightList);
merge(list,leftList,rightList);
}
}
static void merge(ArrayList<Integer> a, ArrayList<Integer> l, ArrayList<Integer> r) {
int totElem = l.size() + r.size();
int i,li,ri;
i = li = ri = 0;
while ( i < totElem) {
if ((li < l.size()) && (ri<r.size())) {
if (l.get(li) < r.get(ri)) {
a.set(i, l.get(li));
i++;
li++;
}
else {
a.set(i, r.get(ri));
i++;
ri++;
}
}
else {
if (li >= l.size()) {
while (ri < r.size()) {
a.set(i, r.get(ri));
i++;
ri++;
}
}
if (ri >= r.size()) {
while (li < l.size()) {
a.set(i, l.get(li));
li++;
i++;
}
}
}
}
}
提前致谢！
推荐答案
您的问题不清楚，但由于您需要实现合并排序算法，因此我认为这是您无法解决的部分.一旦您有一个正确排序的列表，格式打印应该很容易通过反复试验.
Your question is unclear, but since you need to implement a merge sort algorithm I assume this is the part that is broken for you. Format printing should be rather easy through trial and error once you have a properly sorted list.
我认为您在解决方案中过于复杂化了问题.MergeSort 是目前最简单的排序算法之一，但您的代码远非简单.
I think you are greatly overcomplicating the problem in your solution. MergeSort is one of the simplest sorting algorithms out there, yet your code is far from simple.
想想归并排序是如何工作的——它本质上是递归的，因为它是一种分而治之的方法.它通过将一个大的复杂问题分解为小的简单问题来解决它，并且基本上只是合并所有这些问题的结果 - 您的 MergeSort 算法只需要包含这一点.
Think about how Merge Sort works - it is recursive by nature because it is a divide and conquer method. It solves a large complex problem by splitting it into small easy problems, and basically just merges the result from all of these problems - your MergeSort algorithm just needs to encompass this.
如果我们写下来，您需要执行以下步骤:
If we write it up you need to do these steps:
(1) 检查列表是否只包含一个元素——那么它已经排序了
(1) Check if the list contains only one element - then it is already sorted
(2) 将输入分成大小相等的列表并在继续之前对它们进行排序(递归步骤)
(2) Split the input into equally sized lists and sorted these before proceeding (recursive step)
(3) 合并两个已排序的列表，并返回一个已排序的列表.
(3) Merge the two sorted lists, and return a single sorted list.
我看到您对合并部分有一个复杂的方法，并为拆分部分使用了基本迭代.Java List(例如 ArrayList 的超类)提供了一个 .subList(fromIndex, toIndex) 来将列表拆分成更小的列表.你应该使用这个.对于合并部分:
I see that you have a complex method for the merge part and use basic iteration for the splitting part. Java List (superclass of e.g. ArrayList) offers a .subList(fromIndex, toIndex) to split lists into smaller lists. You should use this. For the merging part:
基于来自维基百科的动画
Based on this animation from wikipedia
您应该如何考虑合并两个列表应该很简单:
it should be rather simple how you should think about merging the two lists:
首先将两个列表维护为易于从中删除对象的列表.由于此时我们知道列表将被排序，因此我们只对每个列表中的第一个对象(最小元素)感兴趣.
First maintain both lists as lists that are easy to remove objects from. Since at this point we know that the lists are gonna be sorted, we are ever only interested in the first object in each list (the smallest element).
其次，我们只需要比较每个列表的第一个元素，从各自的列表中删除两者中最小的一个并将其添加到我们的排序列表中.我们一直这样做，直到两个列表都为空——此时我们已经合并了我们的列表.
Second, we only ever need to compare the first element of each list, remove the smallest of the two from its respective list and add it to our sorted list. We keep doing this until both lists are empty - at this point we have merged our lists.
在 Java 中，这表明我们应该为合并部分使用一个数据结构，它允许我们查看每个列表的第一个元素，并快速删除我们感兴趣的元素.在 Java 中，此数据结构是 LinkedList - ArrayList在这项任务中表现非常糟糕，并且没有提供适当的方法来完成这项工作.LinkedList 表现为一个队列，并提供方法来轻松检查和删除列表末尾的对象，例如第一个元素.
In Java this indicates that we should use a datastructure for the merge part that allows us to look at the first element of each lists, and quickly remove the one we are interested in. In Java this data structure is LinkedList - ArrayList both performs terribly at this task and does not offer proper methods for doing this. LinkedList behaves as a queue and offers methods for easily checking and removing objects at the end of the list e.g. the first element.
所以你应该重新考虑你的实现策略并根据你应该如何攻击 MergeSort 算法来简化你的代码.如果这看起来令人困惑，这里有一个仅使用标准 API(没有内置排序方法)在 Java 中实现 MergeSort 的示例.
So you should reconsider your implementation strategy and simplify your code based on how you should attack the MergeSort algorithm. If it seems comfusing here is a sample implementation of MergeSort in Java using only the standard API (no build in sorting method).
希望有帮助.
import java.util.LinkedList;
import java.util.Random;
import java.util.List;
public class Main {
public static void main(String[] args){
Random random = new Random();
LinkedList<Integer> unsorted = new LinkedList<Integer>();
for(int i = 0; i<100; i++){
unsorted.add(random.nextInt(100));
}
System.out.println("unsorted: " + unsorted.toString());
List<Integer> sorted = mergeSort(unsorted);
System.out.println("sorted: " + sorted.toString());
}
//Recursive function for sorting a LinkedList
private static LinkedList<Integer> mergeSort(LinkedList<Integer> unsorted){
//If the list only contains 1 object it is sorted
if(unsorted.size() == 1){
return unsorted;
}
//Split the list in two parts and create a new list to store our sorted list
LinkedList<Integer> left = mergeSort(new LinkedList<Integer>(unsorted.subList(0, unsorted.size()/2)));
LinkedList<Integer> right = mergeSort(new LinkedList<Integer>(unsorted.subList(unsorted.size()/2, unsorted.size())));
LinkedList<Integer> sorted = new LinkedList<Integer>();
//Actual loop for merging the two sublists. Using LinkedLists, this is efficient. (Compared to ArrayList)
while(!left.isEmpty() || !right.isEmpty()){
Integer leftInt = left.peekFirst();
Integer rightInt = right.peekFirst();
if(!(leftInt == null) && !(rightInt == null)){
if(leftInt < rightInt){
sorted.add(left.pollFirst());
}
else{
sorted.add(right.pollFirst());
}
}
else if(leftInt == null){
sorted.add(right.pollFirst());
}
else{
sorted.add(left.pollFirst());
}
}
return sorted;
}
}
这篇关于Java 合并排序算法错误 - 未排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
