QuickSort 太慢和 ArrayIndexOutOfBoundsError

Question

我应该为作业实现 QuickSort，但遇到了几个问题。我的代码运行速度比预期的要慢得多，而且我找不到导致它变慢的原因，因为我严格遵循了我们老师的伪代码。

此外，当我们提交此代码时，它已经过测试，但我们看不到测试，它说我收到 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;
}

我的插入排序class:

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;
        }
    }
}

我的超级class（我们应该在创建不同版本的 QuickSort 时实现它）

public interface IntSorter {

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

Answer 1

这不是您的快速排序代码，而是您的插入排序代码。

在 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 测试 class：

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]);
  }
}

QuickSort 太慢和 ArrayIndexOutOfBoundsError

QuickSort too slow and ArrayIndexOutOfBoundsError

java

quicksort

indexoutofboundsexception