測試排序數組方法

Question

我正在編寫一個程序，測試一個排序函數是否正確排序程序。我必須讓它測試快速排序和合並排序方法。它也必須詢問用戶想要測試哪種方法並製作一組隨機對象。爲什麼我的程序不能正常運行？它只是爲了快速排序而吐出相同的數組，並且它隨機地重新排列它們以進行合併排序。問題是我的排序方法還是我的測試方法？有人請幫忙。

import java.util.Random; 
import java.util.Scanner; 

public class sortArrays { 
    public static void main (String[] args) 
    { 
     Random gen = new Random(); 
     int[] a = new int[20]; 
     Scanner reader = new Scanner(System.in); 
     String choice; 
     int left = a[0]; 
     int right = a[19]; 
     int[] buffer = new int [a.length]; 

     for (int i = 0; i < a.length; i++) 
      a[i] = gen.nextInt(100); 

     printArray(a); 

     System.out.println("Type quick to test the quick sort method."); 
     System.out.println("Type merge to test the merge sort method."); 
     choice = reader.nextLine(); 

     if (choice.equals("quick")) 
      quickSort(a, left, right); 
     else if (choice.equals("merge")) 
      mergeSort(a, buffer, 0, 9, 19); 

     printArray(a); 

    } 


    private static void printArray(int[] a) 
    { 
     for(int i : a) 
      System.out.print(i + " "); 
     System.out.println(""); 
    } 


    private static void quickSort (int[] a, int left, int right) 
    { 
     if (left >= right) return; 

     int i = left; 
     int j = right; 
     int pivotValue = a[(left + right)/2]; 

     while (i < j) 
     { 
      while (a[i] < pivotValue) i++; 
      while (pivotValue < a[j]) j--; 
      if (i <= j) 
      { 
       int temp = a[i]; 
       a[i] = a[j]; 
       a[j] = temp; 
       i++; 
       j--; 
      } 
     } 
     quickSort(a, left, j); 
     quickSort(a, i, right); 
    } 


    private static void mergeSort(int[] a, int[] copyBuffer, int low, int middle, int high) 
    { 
     int i1 = low, i2 = middle + 1; 

     for(int i = low; i <= high; i++) 
     { 
      if(i1 > middle) 
       copyBuffer [i] = a[i2++]; 
      else if(i2 > high) 
       copyBuffer[i] = a[i1++]; 
      else if(a[i1] < a[i2]) 
       copyBuffer[i] = a[i1++]; 
      else 
       copyBuffer[i] = a[i2++]; 
     } 

     for(int i = low; i <= high; i++) 
      a[i] = copyBuffer[i]; 
    } 


} 

Answer 1

那麼，你的printArray()看起來不錯，但有一點站出來的時候了：

要傳遞到quickSort()初始參數是不正確的。您有：

int[] a = new int[20]; 
... 
int left = a[0]; 
int right = a[19]; 
... 
quickSort(a, left, right); 

要初始化left和right到0，這樣的話你最終調用​​（不是你想要的）。你可能意味着要做到這一點，而不是作爲left和right保持指數：

int left = 0; 
int right = 19; 

或者乾脆：

quickSort(a, 0, 19); 

至於你mergeSort()，實施簡直是不完整的。看起來你已經實現了「合併」操作（該算法的基本件），但不是「合併排序」整體算法。您可能想要查看Mergesort in Java（舉例）或Merge Sort（用於總體概述）。

順便說一句，你可能希望指定a.length - 1而不是19，這樣你可以改變a大小，而無需修改其他代碼（同樣會去爲你傳遞給mergeSort()的9，但是這是沒有實際意義的一旦你完全實現算法，你會發現它是不必要的）。