快速排序太慢，ArrayIndexOutOfBoundsError

Question

我應該實現快速排序賦值和我有幾個問題。我的代碼運行得比想象的慢得多，我找不到減慢的速度，因爲我嚴格按照我們的教師僞代碼。

另外，當我們提交這段代碼時，它已經過測試，但是我們看不到測試，它說我得到了一個ArrayIndexOutOfBounds錯誤，這對我來說沒有意義，因爲我已經檢查了限制是否在正確的範圍內。

任何幫助，非常感謝。

public QuickSort() { 
    rand = new Random(); 
} 

@Override 
public void sort(int[] v) { 
    sort(v, 0, v.length-1);  
} 

/** 
* Sort an array from two set points, 
* usually from first index to last. 
*/ 
private void sort(int[] v, int first, int last){ 
    if(first >= last || last <= first || first < 0 || last < 0) 
     return; 
    else if(first >= last-10){ 
     Insertionsort.sort(v, first, last); 
     return; 
    }   
    else if(first < last && first >= 0){ 
     int rnd = first+rand.nextInt(last-first+1); 
     swap(v, rnd, last); 
     int mid = partition(v, first, last); 
     sort(v, first, mid-1); 
     sort(v, mid+1, last); 
    } 
} 

/** 
* Swaps elements in array around a 
* pivot element. 
* < pivot to the left 
* > pivot to the right 
*/ 
private int partition(int[] v, int first, int last){   
    int x = v[last]; 
    int i = first-1; 

    for(int j = first; j<last; j++){ 
     if(v[j] <= x){ 
      i++; 
      swap(v, i, j); 
     } 
    } 

    swap(v, (i+1), (last)); 

    return (i+1); 
} 

/** 
* Swap two elements in a list 
*/ 
private void swap(int[] v, int a , int b){ 
    int temp = v[a]; 
    v[a] = v[b]; 
    v[b] = temp; 
} 

我插入排序類：

public class Insertionsort { 

    public Insertionsort() {} 

    public static void sort(int[] v, int first, int last){ 
     int j, toInsert; 
     for (int i = first+1; i < v[last]; i++) { 
      toInsert = v[i]; 
      j = i; 
      while (j > 0 && v[j - 1] > toInsert) { 
       v[j] = v[j - 1]; 
       j--; 
      } 
      v[j] = toInsert; 
     } 
    } 
} 

我的父（我們應該實現這個爲我們營造了不同版本的快速排序的）

public interface IntSorter { 

    /** 
    * Sorts the array into ascending numerical order. 
    */ 
    void sort(int[] v); 
} 

Answer 1

這不是你的快速排序的代碼，它是你的Insertionsort。

在for循環，你會錯誤地計算循環終止。

for (int i = first+1; i < v[last]; i++) { 

在{2,1}的情況下，我發現該循環提前終止。但想象一下，如果v[last]大於v中的元素數量。沒錯，ArrayIndexOutOfBounds。

的道德故事：數以百萬計的隨機生成ints測試是一個好主意，但小的情況下測試也可以揭露問題。

至於執行時間，嘗試添加static關鍵字Insertionsort這樣的：

public static void sort(int[] v, int first, int last){ 

並調用它像這樣：

Insertionsort.sort(v, first, last); 

這將消除需要創建Insertionsort實例只是爲了排序一小部分數組。 Insertionsort只是爲你做東西而不試圖記住任何東西（即它是無狀態的），所以可以使用靜態方法。

下面是我用的JUnit測試類：

import static org.junit.Assert.assertEquals; 

import java.util.Arrays; 

import org.junit.Test; 

public class TestQuicksort { 
    @Test 
    public void emptyArray() { 
    QuickSort q = new QuickSort(); 
    int[] a = {}; 
    q.sort(a); 
    assertEquals(0, a.length); 
    } 

    @Test 
    public void oneElement() { 
    QuickSort q = new QuickSort(); 
    int[] a = {0}; 
    q.sort(a); 
    assertEquals(1, a.length); 
    assertEquals(0, a[0]); 
    } 

    @Test 
    public void oneTwo() { 
    QuickSort q = new QuickSort(); 
    int[] a = {1, 2}; 
    q.sort(a); 
    assertEquals(2, a.length); 
    assertEquals(1, a[0]); 
    assertEquals(2, a[1]); 
    } 

    @Test 
    public void twoOne() { 
    QuickSort q = new QuickSort(); 
    int[] a = {2, 1}; 
    q.sort(a); 
    assertEquals("Array is " + Arrays.toString(a), 1, a[0]); 
    assertEquals(2, a[1]); 
    } 
}