2

これが 3 方向のクイックソートです...

private void quicksort3(int[] input, int low, int high)
{
    int i = low - 1, j = high, left = low - 1, right = high, pivot = input[high], k;

    if (high <= low) return;
    while (true)
    {
        while (input[++i] < pivot) ;
        while (pivot < input[--j])
            if (j == low) break;
        if (i >= j) break;
        swap(input, i, j);
        if (input[i] == pivot) 
        {
            left++; 
            swap(input, left, i); 
        }
        if (pivot == input[j]) {
            right--;
            swap(input, j, right);
        }
    }
    swap(input, i, high); j = i - 1; i++;
    for (k = low; k < left; k++, j--) 
        swap(input, k, j);
    for (k = high - 1; k > right; k--, i++) 
        swap(input, i, k);
    quicksort3(input, low, j);
    quicksort3(input, i, high);
}

入力の場合、9 5 3例外エラーIndex was outside the bounds of the array.が発生しますpivot = input[high]が、high の値が -1 の場合に例外が発生します (したがって、エラーが発生する理由は理解できます) が、どうすれば修正できますか?

私はそのような関数を呼び出しますquicksort3(arr,0,arr.Length-1);

4

4 に答える 4

3

少し話題から外れているかもしれませんが、Robert Sedgewick と Kevin Wayne の著書 "Algorithms"には素晴らしい 3 方向のクイックソートがあります。
ここで見ることができます - Quick3way.java

private static void sort(Comparable[] a, int lo, int hi) { 
    if (hi <= lo) return;
    int lt = lo, gt = hi;
    Comparable v = a[lo];
    int i = lo;
    while (i <= gt) {
        int cmp = a[i].compareTo(v);
        if      (cmp < 0) exch(a, lt++, i++);
        else if (cmp > 0) exch(a, i, gt--);
        else              i++;
    }

    sort(a, lo, lt-1);
    sort(a, gt+1, hi);
}
于 2012-12-02T17:59:12.823 に答える
3

しかし、どうすれば修正できますか？

このエッジ条件に達したときに、より早く救済することによって。

 //int i = low - 1, j = high, left = low - 1, right = high, pivot = input[high], k;
 //if (high <= low) return;

 if (high <= low) return;
 int i = low - 1, j = high, left = low - 1, right = high, pivot = input[high], k;
于 2012-12-02T17:47:56.310 に答える
3

境界条件がチェックされる前に、値の割り当てが実行されます。pivot = input[high]したがって、行の後に置く必要がありますif (high <= low) return;。

于 2012-12-02T17:50:02.743 に答える