快速排序太慢，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]); 
    } 
}