C#实现快速排序算法详解

快速排序是一种高效的排序算法，其核心思想是通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，然后分别对这两部分记录继续进行排序，直到整个序列有序。在C#中，可以使用递归的方式实现快速排序。以下是一个详细的C#代码示例： ```csharp using System; using System.Collections.Generic; namespace ConsoleApplication16 { class MyQuickSort { ///<summary> /// 快速排序算法 ///</summary> ///<param name="arr">待排序的整数数组</param> ///<param name="low">数组的低端下标</param> ///<param name="high">数组的高端下标</param> static void QuickSort(int[] arr, int low, int high) { // 如果子数组长度大于1，执行快速排序 if (low < high - 1) { // 选择一个基准值（pivot），这里选择第一个元素作为基准 int pivot = arr[low]; // 定义两个指针，一个从低端开始扫描，一个从高端开始扫描 int i = low, j = high; // 当左侧指针小于等于右侧指针时，继续查找 while (i <= j) { // 右侧指针向左移动，寻找第一个小于等于基准的元素 while (arr[j] > pivot && i < j) --j; // 左侧指针向右移动，寻找第一个大于基准的元素 while (arr[i] < pivot && i < j) ++i; // 如果找到合适的元素交换它们 if (i < j) { Swap(ref arr[i], ref arr[j]); } } // 将基准值与找到的合适位置的元素交换，这样基准值左边的元素都小于或等于它，右边的元素都大于它 Swap(ref arr[low], ref arr[i]); // 对基准值左右两侧的子数组分别进行递归排序 QuickSort(arr, low, i - 1); QuickSort(arr, i + 1, high); } } // 用于交换两个整数的辅助方法，使用ref关键字确保原始值被改变 static void Swap(ref int i, ref int j) { int temp; temp = i; i = j; j = temp; } } } ``` 这段代码首先定义了一个`QuickSort`方法，它接受一个整数数组`arr`以及低端和高端下标。在`Partition`方法中，选择数组的第一个元素作为基准值，然后使用两个指针`i`和`j`从两端向中间扫描。当`arr[i]`大于基准值且`arr[j]`小于等于基准值时，交换这两个元素的位置。这样经过一次循环后，基准值左边的元素都小于或等于它，右边的元素都大于它。最后将基准值移动到正确的位置，并对左右两个子数组分别递归调用`QuickSort`。 这个实现的时间复杂度为O(nlog2n)，在平均情况下表现出极高的效率，但最坏情况下的时间复杂度为O(n^2)，当输入数据已经部分有序时。为了优化，可以采用随机化选择基准值或者三数取中法等方式来提高稳定性。快速排序是一种实用且高效的排序算法，适用于大规模数据的处理。