在 C# 中实现快速排序(具有重复项)时出现堆栈溢出错误

public static int Partition(int[] a, int left, int right, int pivotIndex) {
   int temp;
   int pivotValue = a[pivotIndex];
   a[pivotIndex] = a[right];
   a[right] = pivotValue;
   int store = left;
   for (int i = left; i < right; i++) {
      if (a[i] < pivotValue) {
         temp = a[store];
         a[store] = a[i];
         a[i] = temp;
         store++;
      }
   }
   temp = a[right];
   a[right] = a[store];
   a[store] = temp;
   return store;
}
public static void Quicksort(int[] a, int left, int right) {
   if ((right - left) <= 5)
      InsertionSort(a);
   else if (left < right) {
      int mid = ((right - left) / 2) + left;
      int pivot = Math.Max(Math.Min(a[left], a[right]), Math.Min(Math.Max(a[left], a[right]), a[mid]));
      int pivotIndex = Array.IndexOf(a, pivot);
      Partition(a, left, right, pivotIndex);
      Quicksort(a, left, (pivotIndex - 1));
      Quicksort(a, (pivotIndex + 1), right);
   }
}

您的问题在于选择数据透视索引的方式。

尽管您正确选择了三个值的中位数，但无法正确找到该中位数的索引。

首先，这是不正确的：

int pivotIndex = Array.IndexOf(a, pivot);

这将找到整个a[]数组中第一次出现的中值的索引。

至少应该是这样的：

int pivotIndex = Array.IndexOf(a, pivot, left, right-left+1);

但是，这仍然存在几个问题：

1. 您将对整个分区的透视值进行线性搜索。这是非常低效的。
2. 它将找到中值的第一次出现，而不管实际指数是多少。
3. 如果左、右或中间值相同，它应该选择中间索引，但线性搜索会选择左索引。

解决方案是改变计算中位数 3 的方式，以便计算实际索引，而不仅仅是值。这更繁琐！

首先，我建议您在排序之前对数组进行洗牌，或者至少检查中值（或第九个）并在分区期间使用它，它将在概率上保证 O（NLogN）。

此外，如果您有重复项，最好使用 3 路分区。下面是具有三向分区和随机排序的快速排序实现。

public static void Quicksort(int[] a) {
    if (a == null) throw new ArgumentNullException("Array is null");
    Shuffle(a);
    Quicksort(a, 0, a.Length - 1);
}
private static void Quicksort(int[] a, int left, int right) {
    if ((right - left) <= 5)
        InsertionSort(a);
    else if (left <= right) {
        int lt = left, gt = right;
        int v = a[left];
        int i = left;
        while (i <= gt) {
            if      (a[i] < v) Swap(a, lt++, i++);
            else if (a[i] > v) Swap(a, i, gt--);
            else              i++;
        }
        // a[lo..lt-1] < v = a[lt..gt] < a[gt+1..hi]. 
        Quicksort(a, left, lt - 1);
        Quicksort(a, gt + 1, right);
    }
}
public static void Shuffle(int[] a) {
    if (a == null) throw new ArgumentNullException("Array is null");
    int n = a.Length;
    var theRandom = new Random();
    for (int i = 0; i < n; i++) {
        int r = i + theRandom.Next(n-i);     // between i and n-1
        int temp = a[i];
        a[i] = a[r];
        a[r] = temp;
    }
}
private  static void InsertionSort<T>(T[] array) where T:IComparable<T>
{
    for (var i = 1; i < array.Length; i++)
    {
        var value = array[i];
        var j = i - 1;
        while ((j >= 0) && (array[j].CompareTo(value) > 0))
        {
            array[j + 1] = array[j--];
        }
        array[j + 1] = value;
    }
}
private static void Swap(int[] a, int i, int j) {
    int tmp = a[i];
    a[i] = a[j];
    a[j] = tmp;
}

class QuickSortExample
{
    static int Partition(int[] arr, int left, int right)
    {
        int pivot = arr[left + ((right - left) / 2)]; // use a midpoint pivot to prevent worst case O(n log n), although pivot = arr[left] is fine
        while (left < right)
        {
            while (arr[left] < pivot)
                left++;
            while (arr[right] > pivot)
                right--;
            // handle duplicate entries
            if (arr[right] == pivot && arr[left] == pivot)
                left++;
            if (left < right)
            {
                int tmp = arr[right];
                arr[right] = arr[left];
                arr[left] = tmp;
            }
        }
        return right;
    }
    static void QuickSort(int[] arr, int left, int right)
    {
        if(left < right)
        {
            int pivot = Partition(arr, left, right);
            if (pivot > 1)
                QuickSort(arr, left, pivot - 1);
            if(pivot + 1 < right)
                QuickSort(arr, pivot + 1, right);
        }
    }
    static void TestQuickSort(int[] arr)
    {
        Console.WriteLine("Initial array[" + arr.Length + "] = { " + string.Join<int>(", ", arr) + " }");
        QuickSort(arr, 0, arr.Length - 1);
        Console.WriteLine("Sorted  array[" + arr.Length + "] = { " + string.Join<int>(", ", arr) + " }'n");
    }
    static void QuicksortTestRandom(int maxSize)
    {
        Random r = new Random();
        int[] randomValues = new int[r.Next(maxSize)];
        for (int i = 0; i < randomValues.Length; i++)
        {
            randomValues[i] = r.Next(-999, 999);
        }
        TestQuickSort(randomValues);
    }
    static void Main(string[] args)
    {
        Console.WriteLine("QuickSort (Recursive), complexity = O(n log n)'n");
        int[][] TestArrays = new int[][] {
            new int[] { 6, 2, 5, 8, 1, 10, 0, 3, 7, 9, 4 },
            new int[] { 3, 5, 4, 2, 5, 3, 5, 2, 4, 3, 5, 5, 4, 1, 4 },
            new int[] { 67, 12, 95, 56, 1, 85, 85, 1, 100, 23, 60, 9, 0, 85, 0, 85, 85, 90, 85, 85 },
            new int[] { 1 },
            new int[] { 0, 0 },
            new int[] { 1, 0 },
            new int[] { 0, 1 },
            new int[] { 1, 0, 2 },
            new int[] { 1, 0, 1, 0 },
            new int[]  {2, 1, 2, 1, 2, 1, 2, 1 },
            new int[] { 1, 0, -1 },
            new int[] { },
            new int[] { 1, 3, 6, 2, 7, 5, -1, 4, 8, 9, 0 },
        };
        foreach(int[] arr in TestArrays)
        {
            TestQuickSort(arr);
        }
        QuicksortTestRandom(16);
        Console.WriteLine("done... press enter to end.'n");
        Console.ReadLine();
    }
}