快速排序算法-三的中值

本文关键字：算法 快速排序 | 更新日期: 2023-09-27 17:58:53

我有下面的快速排序算法，它使用最左边的作为枢轴，运行非常好：

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

快速排序算法-三的中值

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

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

类似于：（伪代码）

sort(left, mid, right)
pick mid

对于当前的代码，它最终可能会得到一个比其他任何东西都大的值，因此您可能会将0个元素向右分区，只需重复向左递归相同的数据。

这将为您提供中值：

public static class Extensions
{
    public static T Median<T>(this IEnumerable<T> source) where T:IComparable<T>
    {
        if (source == null)
        {
            throw new ArgumentException("source");
        }
        var sortedValues = source.OrderBy(v => v).ToList();
        if (sortedValues.Count == 0)
        {
            throw new InvalidOperationException("Sequence contains no elements");
        }
        var midpoint = (sortedValues.Count/2);
        return sortedValues[midpoint];
    }
}
相关文章：