C#使用随机枢轴实现快速排序的方法

说到排序算法，快速排序可以说是经典中的经典了。它的核心思想其实很直接：先选一个“枢轴”元素，然后通过一次遍历把数组分成两部分——左边全小于枢轴，右边全大于枢轴，接着递归地对左右两个子数组重复这个过程就行。和归并排序不同，快排不需要最后再合并两个有序数组，这个特性让它对辅助空间的需求更少，也是它常常比归并排序更受欢迎的原因。

不过，细心的读者可能已经发现了关键问题：枢轴选得好不好，直接决定了快排的性能。如果每次都能选到中位数，那效率自然没话说；但要是运气不好，每次都选到最大值或最小值，那可就退化到O(N²)了。所以，一个很自然的改进思路就来了——用随机数来决定枢轴的位置。随机枢轴虽然在理论上仍然存在最坏情况，但实际运行中，它的期望时间复杂度可以稳定在O(N log N)，这也是它被广泛采用的原因。

关于数组划分方法，我们之前已经详细聊过两种主流方案：霍尔划分（Hoare）和洛穆托划分（Lomuto）。如果读者对这两种方案还不熟悉，可以先去翻阅一下相关文章，了解一下它们各自的工作原理和适用场景。下面，我们就直接进入正题，看看如何用随机枢轴搭配这两种分区方案来实现快速排序。

基于 Lomuto 分区的随机枢轴算法

先来看洛穆托方案。在这种方法中，我们通常选择最后一个元素作为枢轴，然后通过一个指针遍历数组，把小于等于枢轴的元素放到左边。随机化的加入也很简单——在调用分区函数之前，先随机选一个位置，把它和最后一个元素交换，然后继续执行标准的洛穆托分区。

partition(arr[], lo, hi) 
    pivot = arr[hi] 
    i = lo // 用于交换的位置
    for j := lo to hi – 1 do 
        if arr[j] <= pivot then 
            swap arr[i] with arr[j] 
            i = i + 1 
    swap arr[i] with arr[hi] 
    return i 
partition_r(arr[], lo, hi) 
    r = Random Number from lo to hi 
    Swap arr[r] and arr[hi] 
    return partition(arr, lo, hi) 
quicksort(arr[], lo, hi) 
    if lo < hi 
        p = partition_r(arr, lo, hi) 
        quicksort(arr, lo , p-1) 
        quicksort(arr, p+1, hi)

使用 Lomuto 分区法实现：

// C# program to illustrate
// Randomised Quick sort 
using System;
class RandomizedQsort 
{     
  /* This function takes last element as pivot, 
    places the pivot element at its correct 
    position in sorted array, and places all 
    smaller (smaller than pivot) to left of 
    pivot and all greater elements to right 
    of pivot */
  static int partition(int[] arr, int low, int high) 
  { 
    // pivot is chosen randomly 
    random(arr, low, high);
    int pivot = arr[high];
    int i = (low-1); // index of smaller element 
    for (int j = low; j < high; j++) 
    { 
      // If current element is smaller than or 
      // equal to pivot 
      if (arr[j] < pivot) 
      { 
        i++; 
        // swap arr[i] and arr[j] 
        int tempp = arr[i]; 
        arr[i] = arr[j]; 
        arr[j] = tempp; 
      } 
    } 
    // swap arr[i+1] and arr[high] (or pivot) 
    int tempp2 = arr[i + 1]; 
    arr[i + 1] = arr[high]; 
    arr[high] = tempp2; 
    return i + 1; 
  } 
  // This Function helps in calculating
  // random numbers between low(inclusive)
  // and high(inclusive) 
  static int random(int[] arr, int low, int high) 
  { 
    Random rand = new Random(); 
    int pivot = rand.Next() % (high - low) + low; 
    int tempp1 = arr[pivot];  
    arr[pivot] = arr[high]; 
    arr[high] = tempp1; 
    return partition(arr, low, high);
  } 
  /* The main function that implements Quicksort() 
    arr[] --> Array to be sorted, 
    low --> Starting index, 
    high --> Ending index */
  static void sort(int[] arr, int low, int high) 
  { 
    if (low < high) 
    { 
      /* pi is partitioning index, arr[pi] is 
            now at right place */
      int pi = partition(arr, low, high); 
      // Recursively sort elements before 
      // partition and after partition 
      sort(arr, low, pi - 1); 
      sort(arr, pi + 1, high); 
    } 
  } 
  /* A utility function to print array of size n */
  static void printArray(int[] arr) 
  { 
    int n = arr.Length; 
    for (int i = 0; i < n; ++i) 
      Console.Write(arr[i] + " "); 
    Console.WriteLine(); 
  } 
  // Driver Code 
  static public void Main ()
  {
    int[] arr = {10, 7, 8, 9, 1, 5}; 
    int n = arr.Length; 
    sort(arr, 0, n-1); 
    Console.WriteLine("sorted array"); 
    printArray(arr); 
  } 
}
//  This code is contributed by shubhamsingh10

输出

已排序数组：
1 5 7 8 9 10

时间复杂度： O(N*N)

辅助空间： O(N) // 由于递归调用栈

使用霍尔分区法的随机枢轴算法

接下来看霍尔方案。和洛穆托不同，霍尔的思路是设置两个指针，一个从左向右，一个从右向左，寻找需要交换的元素对。这种方式通常比洛穆托更高效，尤其是对于有大量重复元素的数组。随机化在这里同样适用——在分区前随机选一个元素，然后把它和第一个元素交换，再执行标准霍尔分区。

partition(arr[], lo, hi)
   pivot = arr[lo]
   i = lo - 1  // Initialize left index
   j = hi + 1  // Initialize right index
    while(True)
           // Find a value in left side greater than pivot
           do
              i = i + 1
           while arr[i] < pivot
        // Find a value in right side smaller than pivot
           do
              j = j - 1
           while arr[j] > pivot
           if i >= j then  
              return j
        else
               swap arr[i] with arr[j]
       end    while
partition_r(arr[], lo, hi)
    r = Random number from lo to hi
    Swap arr[r] and arr[lo]
    return partition(arr, lo, hi)
quicksort(arr[], lo, hi)
    if lo < hi
        p = partition_r(arr, lo, hi)
        quicksort(arr, lo, p)
        quicksort(arr, p+1, hi)

使用霍尔分区法的实现：

// C# implementation of QuickSort
// using Hoare's partition scheme
using System;
public class GFG {
    // Driver Code
    public static void Main()
    {
        int[] arr = { 10, 7, 8, 9, 1, 5 };
        int n = arr.Length;
        quickSort(arr, 0, n - 1);
        Console.WriteLine("Sorted array: ");
        printArray(arr, n);
    }
    // This function takes last element as
    // pivot, places the pivot element at
    // its correct position in sorted
    // array, and places all smaller
    // (smaller than pivot) to left of pivot
    // and all greater elements to right
    public static int partition(int[] arr, int low,
                                int high)
    {
        int pivot = arr[low];
        int i = low - 1, j = high + 1;
        // Find leftmost element greater than
        // or equal to pivot
        while (true) {
            do {
                i++;
            } while (arr[i] < pivot);
            // Find rightmost element smaller than
            // or equal to pivot
            do {
                j--;
            } while (arr[j] > pivot);
            // If two pointers met
            if (i >= j)
                return j;
            swap(arr, i, j);
        }
    }
    // Generates Random Pivot, swaps pivot with
    // end element and calls the partition function
    // In Hoare partition the low element is selected
    // as first pivot
    public static int partition_r(int[] arr, int low,
                                  int high)
    {
        // Generate a random number in between
        // low .. high
        Random rnd = new Random();
        int random = low + rnd.Next(high - low);
        // Swap A[random] with A[high]
        swap(arr, random, low);
        return partition(arr, low, high);
    }
    // The main function that implements QuickSort
    // arr[] --> Array to be sorted,
    // low  --> Starting index,
    // high  --> Ending index
    public static void quickSort(int[] arr, int low,
                                 int high)
    {
        if (low < high) {
            // pi is partitioning index,
            // arr[p] is now at right place
            int pi = partition_r(arr, low, high);
            // Separately sort elements before
            // partition and after partition
            quickSort(arr, low, pi);
            quickSort(arr, pi + 1, high);
        }
    }
    // Function to print an array
    public static void printArray(int[] arr, int n)
    {
        for (int i = 0; i < n; i++)
            Console.Write("{0} ", arr[i]);
        Console.Write("\n");
    }
    public static void swap(int[] arr, int i, int j)
    {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

输出

已排序数组：
1 5 7 8 9 10

时间复杂度： O(N*N)

辅助空间： O(N) // 由于递归调用栈

使用 generateRandomPivot 函数实现

如果不想被霍尔和洛穆托的细节束缚，其实还有一种更直接的方式：单独写一个随机生成枢轴的函数，然后手动完成分区逻辑。思路也很清晰：随机选一个位置，把它和最后一个元素交换，然后遍历数组，把小于枢轴的元素都移到左边，最后把枢轴放回正确的位置。这种方法本质上和洛穆托分区相差不大，但代码更直观，适合初学者理解随机枢轴的核心思想。

使用随机枢轴而不进行分区实现快速排序：

using System;
class Program {
  // Function to swap two elements
  static void Swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
  }
  // Function to generate a random pivot index
  static int GenerateRandomPivot(int low, int high) {
    Random random = new Random();
    return low + random.Next(high - low + 1);
  }
  // Function to perform QuickSort
  static void QuickSort(int[] arr, int low, int high) {
    if (low < high) {
      int pivotIndex = GenerateRandomPivot(low, high);
      int pivotValue = arr[pivotIndex];
      // Swap the pivot element with the last element
      Swap(arr, pivotIndex, high);
      int i = low - 1;
      for (int j = low; j < high; j++) {
        if (arr[j] < pivotValue) {
          i++;
          Swap(arr, i, j);
        }
      }
      // Swap the pivot element back to its final position
      Swap(arr, i+1, high);
      // Recursively sort the left and right subarrays
      QuickSort(arr, low, i);
      QuickSort(arr, i+2, high);
    }
  }
  static void Main() {
    int[] arr = {5, 2, 7, 3, 1, 6, 4, 8};
    int n = arr.Length;
    Console.Write("Original array: ");
    for (int i = 0; i < n; i++) {
      Console.Write(arr[i] + " ");
    }
    QuickSort(arr, 0, n-1);
    Console.Write("\nSorted array: ");
    for (int i = 0; i < n; i++) {
      Console.Write(arr[i] + " ");
    }
  }
}

输出

原始数组：5 2 7 3 1 6 4 8
排序后数组：1 2 3 4 5 6 7 8

一句话总结，随机枢轴并不能完全消除最坏情况，但它让最坏情况发生的概率变得极低。在实际应用中，它的期望时间复杂度稳稳地落在O(N log N)，这就足够了。不过，事情没那么简单——最坏情况下的复杂度仍然是O(N²)，所以当你面对极端数据（比如所有元素都相等，或者高度有序的数据）时，还需要额外注意。毕竟，随机化是改善性能的有效手段，但并不是万能的银弹。