资源下载合并排序算法错误 - 未分类 [英] Java Merge Sorting Algorithm Error - Not Sorting
问题描述
我不明白，为什么我的算法使用的ArrayList将无法正常工作。如果球员和加仑可以帮助一个合并排序程序我找到答案，这将是惊人的！打印所需的格式需要进行标签每个数字和地点在新行每20号。我的计划也被限制为标准的Java包。样品的输入和输出，可以发现这里。这是我的code：
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++;
}
}
}
}
}
在此先感谢！
Thanks in advance!
推荐答案
你的问题还不清楚，但因为你需要实现合并排序算法，我想这是零件坏了你。一旦你有一个正确排序列表格式打印应该是经过反复试验比较容易。
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.
我想你们都大大过分复杂的问题，在您的解决方案。归并是最简单的排序算法之一在那里，但你的code远非如此简单。
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.
想想如何合并排序的工作 - 它是递归的性质，因为它是一种分而治之的方法。它解决了大量复杂的问题，通过将其分割成小容易出问题，而且基本上只是合并来自所有这些问题的结果 - 你的归并算法只需要包含这个
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列表（如的ArrayList 的父类）提供了一个 .subList（fromIndex，则元素范围）来列表分成较小的列表。你应该用这个。对于合并部分：
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这个数据结构是链表 - 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.
所以，你应该根据你应该怎么攻击归并算法重新考虑你的实施策略，并简化您的code。如果它似乎comfusing这里是归并的样本实现在Java中仅使用标准的API（没有内置的排序方法）。
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;
}
}
这篇关于资源下载合并排序算法错误 - 未分类的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
