C# 实现快速排序算法的递归实例与解析

咖啡半糖

发布时间：2026-10-13 | 2人浏览过

原创

快速排序（Quick Sort）是一种高效的排序算法，采用分治法策略。本文将展示如何在 C# 中使用递归方法实现该算法，通过选取基准值将数组分为两部分进行处理。

结果与目标

本示例旨在将一个无序的整型数组转换为升序排列。算法的核心在于每次迭代中确定一个基准元素（Pivot），将小于等于它的元素放在左侧，大于它的元素放在右侧，然后对左右子数组重复此过程。

准备条件

开发环境需支持 C# 语法规范。
理解基本的数组操作与递归概念。
确保已引用必要的命名空间以使用 List<T> 集合类型。

真实操作顺序

第 1 步：定义快速排序主函数

目的：设定递归终止条件并处理初始分区。

动作：创建一个静态方法，接收整型数组参数。首先检查数组长度，若小于等于 1 则直接返回（无需排序）。接着选取最后一个元素作为基准值索引，调用辅助函数获取小于等于和大于基准值的子数组，最后合并递归结果。

public static int[] QuickSort(int[] arr)
{
    if (arr.Length <= 1)
        return arr;

    // 选取最后一个元素作为基准
    int pivot = arr.Length - 1;
    
    // 获取小于等于基准的子数组
    int[] less = GetLessThanEqualToPivot(arr, pivot);
    // 获取大于基准的子数组
    int[] greater = GetGreaterThanPivot(arr, pivot);
    
    // 递归排序并拼接结果
    return Concatenate(QuickSort(less), arr[pivot], QuickSort(greater));
}

第 2 步：实现数据拼接辅助方法

目的：将左子数组、基准元素和右子数组合并为一个完整的有序数组。

动作：使用 List<int> 临时存储结果，依次添加左部分、中间基准值、右部分，最后转为数组返回。

public static int[] Concatenate(int[] less, int pivotElement, int[] greater)
{
    List<int> _result = new List<int>();
    _result.AddRange(less);
    _result.Add(pivotElement);
    _result.AddRange(greater);
    return _result.ToArray();
}

第 3 步：实现小于等于基准值的筛选逻辑

目的：从原数组中提取所有小于或等于基准值的元素（不包括基准值本身，因为它已被单独处理）。

动作：遍历数组直到倒数第二个元素，比较当前元素与基准值，符合条件的加入列表。

public static int[] GetLessThanEqualToPivot(int[] arr, int pivot)
{
    List<int> _result = new List<int>();
    for (int i = 0; i < arr.Length - 1; i++)
    {
        if (arr[i] <= arr[pivot])
        {
            _result.Add(arr[i]);
        }
    }
    return _result.ToArray();
}

第 4 步：实现大于基准值的筛选逻辑

目的：从原数组中提取所有严格大于基准值的元素。

动作：同样遍历排除基准值的位置，判断并收集较大值。

public static int[] GetGreaterThanPivot(int[] arr, int pivot)
{
    List<int> _result = new List<int>();
    for (int i = 0; i < arr.Length - 1; i++)
    {
        if (arr[i] > arr[pivot])
        {
            _result.Add(arr[i]);
        }
    }
    return _result.ToArray();
}