实现快速排序算法

Question

我在本书中找到了快速排序算法

这是算法

QUICKSORT (A, p, r)
if p < r
    q = PARTITION(A, p, r)
    QUICKSORT(A, p, q-1)
    QUICKSORT(A, q+1, r)

PARTITION(A, p, r)
x=A[r]
i=p-1
for j = p to r - 1
  if A <= x
     i = i + 1
     exchange A[i] with A[j]
exchange A[i+1] with A[r]
return i + 1

我做了这个c#代码:

private void quicksort(int[] input, int low, int high)
{
    int pivot_loc = 0;

    if (low < high)
        pivot_loc = partition(input, low, high);
    quicksort(input, low, pivot_loc - 1);
    quicksort(input, pivot_loc + 1, high);
}

private int partition(int[] input, int low, int high)
{
    int pivot = input[high];
    int i = low - 1;

    for (int j = low; j < high-1; j++)
    {
        if (input[j] <= pivot)
        {
            i++;
            swap(input, i, j);
        }
    }
    swap(input, i + 1, high);
    return i + 1;
}



private void swap(int[] ar, int a, int b)
{
    temp = ar[a];
    ar[a] = ar[b];
    ar[b] = temp;
}

private void print(int[] output, TextBox tbOutput)
{
    tbOutput.Clear();
    for (int a = 0; a < output.Length; a++)
    {
        tbOutput.Text += output[a] + " ";
    }
}

当我调用这样的函数时,quicksort(arr,0,arr.Length-1);我得到这个错误An unhandled exception of type 'System.StackOverflowException' occurred它传递空数组...当这样的调用函数quicksort(arr,0,arr.Length);我Index was outside the bounds of the array.在这一行得到错误int pivot = input[high];但数组传递成功.

我也想像这样打印它,print(input,tbQuick);但放在哪里,以便在quicksort完成后打印？

Answer 1

您没有正确实现基本案例终止,这导致quicksort永远不会停止使用长度为0的子列表进行自我递归.

改变这个:

if (low < high)
    pivot_loc = partition(input, low, high);
quicksort(input, low, pivot_loc - 1);
quicksort(input, pivot_loc + 1, high);

对此:

if (low < high) {
    pivot_loc = partition(input, low, high);
    quicksort(input, low, pivot_loc - 1);
    quicksort(input, pivot_loc + 1, high);
}

Answer 2

除了Deestan的答案,你也有这个错误:

for (int j = low; j < high-1; j++)

它应该是:

for (int j = low; j < high; j++)