我有以下快速排序算法，它使用最左边的作为支点，工作得很好：
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];
}
}
