快速排序算法-中位数三

debugcn 发表于 Dev

富有的

我有以下快速排序算法，该算法使用最左边的数据作为枢纽，效果很好：

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

伯恩哈德·巴克（Bernhard Barker）

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

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

类似于：（伪代码）