C# 排序算法之快速排序

快速排序（Quick Sort）是一种高效的排序算法，由C. A. R. Hoare在1960年提出。它的基本思想是：通过一趟排序将待排记录分隔成独立的两部分，其中一部分的所有记录均比另一部分的所有记录小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。这个过程可以递归进行，以达到整个序列变为有序序列。

以下是快速排序算法的C#实现：

using System;class Program
{static void Main(string[] args){int[] arr = { 10, 7, 8, 9, 1, 5 };QuickSort(arr, 0, arr.Length - 1);Console.WriteLine("Sorted array: ");PrintArray(arr);}// 快速排序算法static void QuickSort(int[] arr, int low, int high){if (low < high){// 划分操作，返回划分后基准值的索引int pi = Partition(arr, low, high);// 递归地对基准值左边的子数组进行快速排序QuickSort(arr, low, pi - 1);// 递归地对基准值右边的子数组进行快速排序QuickSort(arr, pi + 1, high);}}// 划分操作static int Partition(int[] arr, int low, int high){// 选择最右边的元素作为基准值int pivot = arr[high];int i = (low - 1); // 较小元素的索引for (int j = low; j < high; j++){// 如果当前元素小于或等于基准值if (arr[j] <= pivot){i++;    // 移动较小元素的索引// 交换arr[i]和arr[j]int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}}// 将基准值交换到其最终位置int temp = arr[i + 1];arr[i + 1] = arr[high];arr[high] = temp;// 返回基准值的索引return i + 1;}// 打印数组的方法static void PrintArray(int[] arr){foreach (int i in arr){Console.Write(i + " ");}Console.WriteLine();}
}

在这个实现中，QuickSort 方法是快速排序的递归实现。它接受一个数组和两个整数作为参数，分别表示要排序的数组段落的起始和结束索引。如果起始索引小于结束索引，说明数组段落中有多个元素，需要进行排序。方法首先调用 Partition 方法来选择一个基准值，并重新排列数组，使得所有小于基准值的元素都移到基准值的左边，所有大于基准值的元素都移到基准值的右边。然后，递归地对基准值左右两边的子数组进行相同的操作。

Partition 方法实现了划分操作，它选择一个基准值（这里选择的是子数组的最后一个元素），并通过遍历子数组，将所有小于或等于基准值的元素移动到基准值的左边，所有大于基准值的元素移动到基准值的右边。最后，将基准值交换到它的最终位置，即小于它的所有元素的右边，大于它的所有元素的左边，并返回这个位置的索引。

PrintArray 方法与之前一样，用于打印排序后的数组。

快速排序的平均时间复杂度为O(n log n)，但在最坏情况下（如数组已经是有序的）时间复杂度会退化到O(n^2)。不过，通过随机选择基准值或使用其他策略（如三数取中法），可以大大降低最坏情况发生的概率。