实现快速排序算法 [英] Implementing quicksort algorithm

问题描述

我发现快速排序算法从这本书

I found quicksort algorithm from this book

这是算法

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＃code：

And I made this c# code:

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] + " ";
    }
}

当我这样调用函数快速排序（ARR，0，arr.Length-1）; 我得到这个错误类型的未处理的异常System.StackOverflowException发生将它传递空数组......当这样的快速排序（ARR，0，arr.Length）通话功能; 我得到错误索引是该数组的边界之外在这一行 INT支点=输入[高]; 但是数组顺利通过。

When I call function like this quicksort(arr,0,arr.Length-1); I get this error An unhandled exception of type 'System.StackOverflowException' occurred it pass empty array... when call function like this quicksort(arr,0,arr.Length); I get error Index was outside the bounds of the array. on this line int pivot = input[high]; but array passed successfully.

我也想打印它像这样打印（输入，tbQuick）; ，但在何处放置它，所以它会打印时，快速排序完成

I also want to print it like this print(input,tbQuick); but where to place it so it would print when quicksort finished?

推荐答案

您没有正确实施基本情况终止，这将导致快速排序永远不要停止递归到本身长度为0的子列表。

You did not properly implement the base case termination, which causes quicksort to never stop recursing into itself with sublists of length 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);
}

这篇关于实现快速排序算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！