C# 实现快速排序：原理、代码与性能优化

阿澈

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

原创

快速排序是一种基于分治思想的高效排序算法。本文通过 C# 代码演示如何实现标准快速排序，深入解析分区（Partition）机制，并针对实际开发中的性能痛点，介绍三向切分及混合插入排序等优化手段，以应对包含大量重复元素的数组场景。

1. 快速排序核心原理

快速排序的核心在于“切分”（Partition）。它将一个数组划分为两个子数组：左侧子数组的所有元素均小于等于某个基准值，右侧子数组的所有元素均大于等于该基准值。随后，算法对这两个子数组独立进行递归排序。与归并排序不同，快速排序是原地排序，仅需极小的辅助栈空间。

第1步：实现标准快速排序

目的： 构建基础的快排框架，理解索引扫描与交换逻辑。

入口： Quick.Sort(IComparable[] a)

动作：

调用 Sort(a, 0, a.Length - 1) 启动递归。
在 Partition 方法中，选取左端点 a[lo] 作为基准值 v。
使用双指针 i（从左向右）和 j（从右向左）扫描数组：
- i 寻找第一个大于等于 v 的元素。
- j 寻找第一个小于等于 v 的元素。
若 i < j，交换两元素；若 i >= j，停止扫描并将基准值 a[lo] 与 a[j] 交换，返回 j 作为分割点。
递归处理 [lo, j-1] 和 [j+1, hi] 区域。

    public class Quick: BaseSort
    {
        public new static long usedTimes = 0;
        public static void Sort(IComparable[] a)
        {
            usedTimes = 0;
            Stopwatch timer = new Stopwatch();
            timer.Start();
            Sort(a,0,a.Length-1);
            timer.Stop();
            usedTimes = timer.ElapsedMilliseconds;
        }

        public static void Sort(IComparable[] a, int lo, int hi)
        {
            if (hi <= lo)
                return;

            //切分
            int j = Partition(a,lo,hi);
            Sort(a,lo,j-1); // 排序左半部分
            Sort(a,j+1,hi); // 排序右半部分
        }
        
        public static int CompareCount = 0;
        public static int Partition(IComparable[] a, int lo, int hi)
        {
            int i = lo;
            int j = hi + 1;
            var v = a[lo]; // 选定基准值

            while (true)
            {
                // 从左往右扫描，找到 >= v 的元素
                while (Less(a[++i], v))
                {
                    CompareCount++;
                    if (i == hi)
                        break;
                }

                // 从右往左扫描，找到 <= v 的元素
                while (Less(v, a[--j]))
                {
                    CompareCount++;
                    if (j == lo)
                        break;
                }

                // 指针相遇，退出内循环
                if (i >= j)
                    break;
                
                // 交换越界元素
                Exch(a,i,j);
            }

            // 将基准值放到正确位置 j
            Exch(a,lo,j);
            return j;
        }

        // 辅助方法省略：Less, Exch 等
    }

在该实现中，Partition 是关键。切分完成后，a[lo]...a[j-1] 不大于 a[j]，a[j+1]...a[hi] 不小于 a[j]。当子数组长度为 1 时自然有序，所有子数组有序后，整个数组即有序。

注意点

边界检查： 扫描指针 i 和 j 必须防止跑出数组边界（如代码中对 hi 和 lo 的判断）。
终止条件： 递归必须在 hi <= lo 时终止，否则会导致栈溢出。
重复元素处理： 当前版本在遇到等于基准值的元素时会停止扫描。虽然这会导致一些不必要的交换，但在某些情况下能避免性能退化为平方级。

2. 性能分析与潜在问题

快速排序的平均时间复杂度为 N log N，这得益于其简洁的内循环和较少的内存移动次数。然而，其性能高度依赖于数据的分布：

最佳情况： 每次切分都将数组对半分开，比较次数约为 N log N。
最坏情况： 如果每次切分都极度不平衡（例如数组已逆序且未做随机化处理），比较次数可能退化为 N² / 2。此时性能远低于预期。
重复元素影响： 当数组中包含大量相同元素时，标准快排的左右指针会在相等处停下并继续交换，导致效率下降。

3. 快速排序的优化策略

为了提升在实际应用场景中的表现，通常采用以下两种改进措施。

第2步：小数组切换插入排序

目的： 减少递归调用的开销，利用插入排序在小规模数据上的低常数因子优势。

操作： 当子数组长度小于一定阈值（通常为 5~15）时，不再递归调用快排，而是直接调用插入排序。

代码修改：

将递归终止条件 if (hi <= lo) return; 修改为：

 if (hi <= lo + M) { Insertion.Sort(a, lo, hi); return; }

其中 M 为阈值参数，最佳值视系统而定，一般在 5 到 15 之间。

第3步：三向切分快速排序（3-Way Quicksort）

目的： 解决存在大量重复元素时的性能瓶颈，将时间复杂度从线性对数级降低至线性级。

原理： 将数组分为三部分：小于基准值、等于基准值、大于基准值。维护三个指针 lt、i、gt：

a[lo ... lt-1] : 小于 v
a[lt ... i-1] : 等于 v
a[i ... gt] : 尚未确定
a[gt+1 ... hi] : 大于 v

执行逻辑： 遍历 i：

若 a[i] < v：交换 a[lt] 与 a[i]，lt 和 i 同时递增。
若 a[i] > v：交换 a[i] 与 a[gt]，仅 gt 递减（i 不变，因为交换过来的元素尚未检查）。
若 a[i] == v：i 递增。

经过一轮扫描，所有等于基准值的元素被聚集在中间，无需参与后续递归。对于有大量重复键值的数组，这种方法极其高效。

    public class Quick: BaseSort
    {
        public new static long usedTimes = 0;

        // 三向切分入口
        public static void Sort3Way(IComparable[] a)
        {
            usedTimes = 0;
            Stopwatch timer = new Stopwatch();
            timer.Start();
            Sort3Way(a, 0, a.Length - 1);
            timer.Stop();
            usedTimes = timer.ElapsedMilliseconds;
        }

        public static void Sort3Way(IComparable[] a, int lo, int hi)
        {
            if (hi < lo)
                return;
            
            int lt = lo, i = lo + 1, gt = hi;
            IComparable v = a[lo]; // 基准值
            
            while (i <= gt)
            {
                int cmp = a[i].CompareTo(v);
                if (cmp < 0)
                    // a[i] 小于 v，交换到左侧，指针右移
                    Exch(a, lt++, i++);
                else if (cmp > 0)
                    // a[i] 大于 v，交换到右侧，右侧指针左移
                    Exch(a, i, gt--);
                else
                    // a[i] 等于 v，跳过，右移指针
                    i++;
            }

            // 递归排序小于和大于的部分，等于的部分已就位
            Sort3Way(a, lo, lt - 1);
            Sort3Way(a, gt + 1, hi);
        }
    }