c# - 3 种快速排序算法

Question

这是三向快速排序...

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

Answer 1

您的赋值是在检查边界条件之前执行的。所以你应该把pivot = input[high]在行 if (high <= low) return; 之后.