时间戳

首页 > 解决方案 > 快速排序实现的堆栈溢出

c# - 快速排序实现的堆栈溢出

问题描述

我正在尝试实现快速排序算法（在 C# 中），这是我的代码：

public static void sort(ref int[] A)
{
    if (A.Length==0 || A.Length==1) 
    { 
        return; 
    }
    quickSort(ref A,0,A.Length-1);
}

private static void quickSort(ref int[] A, int left, int right)
{
    if (left >= right || left < 0 || right < 0) 
        return;

    int pivot = A[left];

    int i = left - 1;
    int j = right + 1;

    while (true) 
    {
        do 
        { 
            i++; 
        } 
        while (A[i] < pivot);

        do 
        { 
            j--; 
        } 
        while (A[j] > pivot);

        if (i >= j) 
            break;

        int temp = A[i];
        A[i] = A[j];
        A[j] = temp;
    }

    quickSort(ref A,left,j);
    quickSort(ref A, j + 1, right);
}

这个算法工作得很好，但是有些东西似乎不合逻辑，我在我写的循环中选择pivot了等于A[left]then ，我现在注意到它第一次会增加所以将等于哪个是枢轴值，所以这应该意味着这个循环将在 i 的第一个增量后停止，因此当我尝试将运算符添加到第一个增量后它不会停止时：我得到了堆栈溢出异常（当我添加等于时也得到了堆栈溢出异常操作员到第二个:) ，我不明白为什么会这样，谁能解释一下吗？while(true)do{i++}while(A[i]<pivot)iA[i]A[left]do while=whilewhile(A[i]<=)do whilewhile(A[j]>=pivot)

标签： c#algorithmstack-overflowquicksort

解决方案

这是霍尔分区方案。do while 循环需要使用 < 或 >，而不是 <= 或 >=，因为它们依赖于找到等于中枢的枢轴或元素来停止循环并防止循环超出范围 [lo,你好]。通常将中间元素用作枢轴，例如

    int pivot = A[(left+right)/2];   // or A[left + (right-left)/2]

使用当前代码，唯一不能用于枢轴的元素是 A[right]，因为这会导致堆栈溢出（快速排序调用最终会卡在 high = low + 1）。

所以使用 pivot = A[left]，第一个 do while 以 i == left 停止，第二个 do while 以 j <= right 停止。如果 i < j，则发生交换，将主元交换为 A[j]，将元素 <= 主元交换为 A[i == left]。每次交换都会防止下一对 do while 运行超出界限 [low, high]，因此在这对 do while 之后只需要检查 i >= j 以检查分区步骤是否完成。

为枢轴选择中间元素有助于某些数据模式，例如已排序的数据或反向排序的数据。尽管如此，如果左元素 == 枢轴，第一个 do while 将在第一个循环上停止。

请注意，Hoare 分区方案仅将分区拆分为元素 <= 枢轴和元素 >= 枢轴。枢轴或任何等于枢轴的元素可以在分区步骤之后的任何位置结束。这不是问题，因为最终枢轴或等于枢轴的元素最终将位于正确的位置（这可能不会发生，直到达到低 == 高的递归级别）。

推荐阅读