Java算法 - 使用ArrayList進行合併排序

我是一名AP計算機科學專業的學生，我目前的任務是必須製作一個程序，該程序需要一個數字ArrayList，並且只使用標準Java API，使用合併分類。沒有任何編譯錯誤，但在運行時它甚至不返回ArrayList！經過一些調試，我發現它沒有填充原始列表。請幫忙！代碼：Java算法 - 使用ArrayList進行合併排序

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 < list.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.println(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++; 
       } 
      } 
     } 
    } 
}

來源

2014-02-14 Rekless_Zombie

不必要的循環會損害性能。嘗試使用ArrayList.subList（int fromIndex，int toIndex），在ArrayList的情況下應該更快。 –

啊，是的。我忘了ArrayList繼承了這個。我一定會改變這一點。謝謝。 –

這是因爲list.size()爲空列表返回0。在填充列表的循環中，將list.size()替換爲size。

我還沒有檢查過程中的實際mergeSort部分，但我建議的更改至少會使列表的初始人羣工作。

來源

2014-02-14 03:38:10

真棒打印！但是現在它不允許正確的輸出。我試圖格式化它從左到右的位置，並使用「\ t」隔開並轉到下一行。我可能會改變這個「如果（j％20 == 0）{」只是使它的每增加20（即20,40,60,80等最多200）。 –

我建議'java.util.Arrays.toString（T []數組）'從'youList.toArray（〜）'打印數組...'並且看看'Arrays.sort（〜）'它。由於您的分配僅限於Java標準API –

現在確定排序算法需要工作。它似乎沒有正確計算......：我 –

Java算法 - 使用ArrayList進行合併排序

回答

相關問題