深入解析C语言三路快速排序算法

快速排序(Quick Sort)是计算机科学中最经典的排序算法之一，平均时间复杂度为O(nlogn)。但当数组中存在大量重复元素时，传统快速排序效率会显著下降。本文将详细介绍一种优化版本——三路快速排序(3-Way Quick Sort)，它能够高效处理重复元素，是实际应用中更优的选择。

一、传统快速排序的局限性

传统快速排序采用二路划分：

1. 选择一个基准值(pivot)

2. 将数组分为两部分：小于等于基准值的元素和大于基准值的元素

c

// 传统二路快排分区函数int partition(int* arr, int low, int high) { int pivot = arr[high]; int i = low; for (int j = low; j < high; j++) { if (arr[j] <= pivot) { swap(&arr[i], &arr[j]); i++; } } swap(&arr[i], &arr[high]); return i;}

问题：当数组包含大量重复元素时，会导致分区不平衡，递归深度增加，性能退化到O(n²)。

二、三路快速排序原理

三路快速排序由Dijkstra提出，核心思想是将数组划分为三部分：

1. 小于基准值的元素

2. 等于基准值的元素

3. 大于基准值的元素

这种划分方式能有效处理重复元素，减少不必要的递归调用。

三、算法实现

c

void swap(int* a, int* b) { int temp = *a; *a = *b; *b = temp;}void threeWayQuickSort(int* arr, int low, int high) { if (low >= high) return; // 初始化指针 int lt = low; // 小于区的右边界 int gt = high; // 大于区的左边界 int i = low + 1; // 当前元素指针 int pivot = arr[low]; // 选择第一个元素作为基准值 while (i <= gt) { if (arr[i]  pivot) { swap(&arr[i], &arr[gt]); gt--; // 注意：这里不增加i，因为交换来的新元素需要重新检查 } else { i++; } } // 递归排序小于区和大于区 threeWayQuickSort(arr, low, lt - 1); threeWayQuickSort(arr, gt + 1, high);}

四、算法步骤详解

1. 初始化指针：

   • lt(less than)指向小于区的末尾

   • gt(greater than)指向大于区的开头

   • i是当前遍历指针

2. 元素分类处理：

   • 当前元素 < 基准值：交换到lt位置，lt和i都右移

   • 当前元素 > 基准值：交换到gt位置，gt左移

   • 当前元素 = 基准值：直接跳过(i右移)

3. 终止条件：当i超过gt时结束

4. 递归排序：只对小于区和大于区进行递归，等于区已有序

五、示例演示

以数组 [3, 1, 4, 1, 5, 9, 2, 6, 5, 3] 为例：

1. 第一次分区(pivot=3)：

   • 小于区：[1, 1, 2]

   • 等于区：[3, 3]

   • 大于区：[4, 5, 9, 6, 5]

2. 递归处理小于区和大于区

3. 最终结果：[1, 1, 2, 3, 3, 4, 5, 5, 6, 9]

六、性能分析

1. 时间复杂度：

   • 最佳/平均情况：O(nlogn)

   • 最坏情况：O(n²)（但概率极低）

   • 含大量重复元素时接近O(n)

2. 空间复杂度：

   • 递归栈空间：O(logn)

3. 与传统快排对比：

   • 重复元素越多，优势越明显

   • 普通快排可能退化为O(n²)，三路快排仍保持高效

七、优化技巧

1. 随机化基准值：

c

// 在分区前添加：int random = low + rand() % (high - low + 1);swap(&arr[low], &arr[random]);pivot = arr[low];

1. 小数组改用插入排序：

c

if (high - low + 1 <= 16) { insertionSort(arr, low, high); return;}

1. 三数取中法选择基准值

八、应用场景

1. 需要处理大量重复元素的数据集

2. 需要稳定排序的场合

3. 作为系统排序算法的优化版本