快速排序是一种基于分治思想的高效排序算法，平均时间复杂度为O(n log n)，在很多场景下比冒泡排序、插入排序等基础排序算法性能更好。它的核心逻辑是选择一个基准元素，将数组分为两部分，一部分元素都小于基准，另一部分都大于基准，之后对两部分分别递归执行相同操作，直到整个数组有序。
快速排序的核心步骤
实现快速排序主要包含三个核心步骤：
- 选择基准元素：通常可以选择数组的第一个元素、最后一个元素或者中间元素作为基准，本文选择数组最后一个元素作为基准。
- 分区操作：遍历数组，将小于基准的元素移到基准左侧，大于基准的元素移到基准右侧，最后将基准放到正确的位置。
- 递归排序：对基准左侧和右侧的子数组分别递归执行快速排序，直到子数组长度小于等于1时停止递归。
C#实现快速排序的完整代码
下面是使用C#编写的快速排序完整实现，包含分区方法和递归排序方法：
using System;
namespace QuickSortDemo
{
class Program
{
static void Main(string[] args)
{
int[] arr = { 3, 6, 8, 2, 1, 9, 4, 5, 7 };
Console.WriteLine("排序前的数组：");
PrintArray(arr);
QuickSort(arr, 0, arr.Length - 1);
Console.WriteLine("排序后的数组：");
PrintArray(arr);
}
// 快速排序主方法，left为左边界索引，right为右边界索引
static void QuickSort(int[] arr, int left, int right)
{
if (left < right)
{
// 获取分区后基准元素的索引
int pivotIndex = Partition(arr, left, right);
// 递归排序基准左侧子数组
QuickSort(arr, left, pivotIndex - 1);
// 递归排序基准右侧子数组
QuickSort(arr, pivotIndex + 1, right);
}
}
// 分区方法，返回基准元素的最终索引
static int Partition(int[] arr, int left, int right)
{
// 选择最右侧元素作为基准
int pivot = arr[right];
// i表示小于基准的元素的边界索引，初始为left-1
int i = left - 1;
// 遍历left到right-1的元素
for (int j = left; j < right; j++)
{
// 如果当前元素小于基准，将其交换到i的下一个位置
if (arr[j] < pivot)
{
i++;
Swap(arr, i, j);
}
}
// 将基准元素放到正确的位置，即i的下一个位置
Swap(arr, i + 1, right);
// 返回基准元素的索引
return i + 1;
}
// 交换数组中两个元素的方法
static void Swap(int[] arr, int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// 打印数组的方法
static void PrintArray(int[] arr)
{
Console.WriteLine(string.Join(", ", arr));
}
}
}
代码逻辑说明
上述代码中，QuickSort方法是快速排序的入口，首先判断左边界是否小于右边界，如果是则调用Partition方法完成分区，得到基准元素的正确索引后，再对左右两个子数组递归调用QuickSort。
Partition方法实现了核心的分区逻辑，首先选择最右侧的元素作为基准，然后用变量i记录小于基准的元素的边界，遍历数组时遇到小于基准的元素就将其交换到i的下一个位置，遍历完成后将基准元素交换到i+1的位置，这个位置就是基准元素的最终正确位置。
Swap方法用于交换数组中两个指定索引的元素，是分区过程中用到的基础辅助方法。
算法特点与注意事项
快速排序的平均时间复杂度是O(n log n)，但是最坏情况下（比如数组已经有序且每次选择最后一个元素作为基准）时间复杂度会退化为O(n²)，如果需要避免最坏情况，可以随机选择基准元素，或者选择左、中、右三个元素的中间值作为基准。
快速排序是一种原地排序算法，不需要额外的数组空间，空间复杂度主要来自递归调用栈，平均递归深度为O(log n)，最坏情况下递归深度为O(n)。
如果需要排序的是引用类型对象，只需要修改比较的逻辑，将arr[j] < pivot替换为对应属性的比较即可，核心的排序逻辑不需要改动。