c# - 快速排序算法 - 三的中位数

Question

我有以下快速排序算法，它使用最左边的作为枢轴，效果很好:

public static void QuickSortLeft(int[] array, int start, int end)
{
    int left = start;
    int right = end;

    int pivot = array[start];

    while (left <= right)
    {
        while (array[left] < pivot)
        {
            left++;
        }

        while (array[right] > pivot)
        {
            right--;
        }

        if (left <= right)
        {
            swap(array,left, right);

            left++;
            right--;
        }
    }

    // Recursive calls
    if (start < right)
    {
        QuickSortLeft(array, start, right);
    }

    if (left < end)
    {
        QuickSortLeft(array, left, end);
    }
}

现在我尝试对上面的第一个、最后一个和中间位置的中位数进行中位数优化，并将中位数用作如下所示的枢轴，但是我收到 StackOverflow 异常

public static void QuickSortMedian(int[] array, int start, int end)
{
    int left = start;
    int right = end;

    int pivot = (array[start] + array[(start + (end - start)) / 2] + array[end]) / 2;

    while (left <= right)
    {
        while (array[left] < pivot)
        {
            left++;
        }

        while (array[right] > pivot)
        {
            right--;
        }

        if (left <= right)
        {
            swap(array, left, right);

            left++;
            right--;
        }
    }

    // Recursive calls
    if (start < right)
    {
        QuickSortMedian(array, start, right);
    }

    if (left < end)
    {
        QuickSortMedian(array, left, end);
    }
}

Answer 1

您正在计算平均值(但不正确 - 它应该是 /3，而不是 /2)，而不是中位数。

您应该选择三个元素中的中间元素。

类似于:(伪代码)

sort(left, mid, right)
pick mid

使用您当前的代码，它最终可能会得到一个比其他所有元素都大的值，因此您可能最终将 0 个元素划分到右侧，只是重复向左递归相同的数据。