【数据结构与算法】第33篇：交换排序（二）：快速排序

一、快速排序的基本思想

1.1 分治策略

1. 选择基准：从数组中选一个元素作为基准（pivot）

2. 分区：重新排列数组，比基准小的放左边，大的放右边

3. 递归：对左右两个子数组递归执行上述过程

1.2 图解示例

初始：[6, 1, 2, 7, 9, 3, 4, 5, 10, 8]，选6为基准

text

分区后：`[1, 2, 3, 4, 5, 6, 7, 9, 10, 8]` ↑ 基准归位 递归左半：`[1, 2, 3, 4, 5]` 递归右半：`[7, 9, 10, 8]`

二、三种分区方法

2.1 Hoare法（左右指针法）

思路：

1. 选最左（或最右）为基准

2. 左指针找比基准大的，右指针找比基准小的

3. 交换，直到左右指针相遇

4. 基准归位

c

int partitionHoare(int arr[], int left, int right) { int pivot = arr[left]; // 选最左为基准 int i = left, j = right; while (i < j) { // 右指针找比基准小的（注意先移动右指针） while (i < j && arr[j] >= pivot) j--; // 左指针找比基准大的 while (i < j && arr[i] <= pivot) i++; // 交换 if (i < j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } // 基准归位 arr[left] = arr[i]; arr[i] = pivot; return i; }

2.2 挖坑法

思路：

1. 选基准，挖出形成坑位

2. 右指针找比基准小的，填左坑，右坑形成

3. 左指针找比基准大的，填右坑，左坑形成

4. 重复，直到左右相遇，把基准填回

c

int partitionHole(int arr[], int left, int right) { int pivot = arr[left]; // 挖坑 int i = left, j = right; while (i < j) { while (i < j && arr[j] >= pivot) j--; arr[i] = arr[j]; // 填左坑，右坑形成 while (i < j && arr[i] <= pivot) i++; arr[j] = arr[i]; // 填右坑，左坑形成 } arr[i] = pivot; // 填回基准 return i; }

2.3 前后指针法

思路：

1. 选最右为基准

2. prev指向小于基准区域的末尾，cur遍历

3. 当cur找到比基准小的，prev++，交换arr[prev]和arr[cur]

4. 最后把基准放到prev+1位置

c

int partitionPtr(int arr[], int left, int right) { int pivot = arr[right]; // 选最右为基准 int prev = left - 1; for (int cur = left; cur < right; cur++) { if (arr[cur] < pivot) { prev++; int temp = arr[prev]; arr[prev] = arr[cur]; arr[cur] = temp; } } // 基准归位 prev++; arr[right] = arr[prev]; arr[prev] = pivot; return prev; }

三、递归实现快速排序

c

void quickSort(int arr[], int left, int right) { if (left >= right) return; int pivotIndex = partitionHole(arr, left, right); quickSort(arr, left, pivotIndex - 1); quickSort(arr, pivotIndex + 1, right); }

四、优化：三数取中法

4.1 最坏情况

当数组已有序时，每次选最左为基准，递归深度为n，时间复杂度退化为O(n²)。

text

[1, 2, 3, 4, 5] 选1为基准 → 左空，右[2,3,4,5] → 递归深度5

4.2 三数取中

取左、中、右三个位置的中位数作为基准，避免选到极端值。

c

int medianOfThree(int arr[], int left, int right) { int mid = left + (right - left) / 2; if (arr[left] > arr[mid]) { int temp = arr[left]; arr[left] = arr[mid]; arr[mid] = temp; } if (arr[left] > arr[right]) { int temp = arr[left]; arr[left] = arr[right]; arr[right] = temp; } if (arr[mid] > arr[right]) { int temp = arr[mid]; arr[mid] = arr[right]; arr[right] = temp; } // 此时mid位置的值是中位数 return mid; } int partitionOptimized(int arr[], int left, int right) { // 三数取中，并将基准换到最左 int mid = medianOfThree(arr, left, right); int temp = arr[left]; arr[left] = arr[mid]; arr[mid] = temp; // 继续用挖坑法 return partitionHole(arr, left, right); }

五、完整代码实现

c

#include <stdio.h> #include <stdlib.h> #include <time.h> // 交换 void swap(int *a, int *b) { int temp = *a; *a = *b; *b = temp; } // 三数取中 int medianOfThree(int arr[], int left, int right) { int mid = left + (right - left) / 2; if (arr[left] > arr[mid]) swap(&arr[left], &arr[mid]); if (arr[left] > arr[right]) swap(&arr[left], &arr[right]); if (arr[mid] > arr[right]) swap(&arr[mid], &arr[right]); return mid; } // 挖坑法分区 int partitionHole(int arr[], int left, int right) { int pivot = arr[left]; int i = left, j = right; while (i < j) { while (i < j && arr[j] >= pivot) j--; arr[i] = arr[j]; while (i < j && arr[i] <= pivot) i++; arr[j] = arr[i]; } arr[i] = pivot; return i; } // 优化版分区（三数取中） int partitionOptimized(int arr[], int left, int right) { int mid = medianOfThree(arr, left, right); swap(&arr[left], &arr[mid]); // 将基准换到最左 return partitionHole(arr, left, right); } // 快速排序 void quickSort(int arr[], int left, int right) { if (left >= right) return; int pivotIndex = partitionOptimized(arr, left, right); quickSort(arr, left, pivotIndex - 1); quickSort(arr, pivotIndex + 1, right); } // 打印数组 void printArray(int arr[], int n) { for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } printf("\n"); } // 测试性能 void testPerformance() { srand(time(NULL)); int sizes[] = {1000, 10000, 50000}; int nTests = sizeof(sizes) / sizeof(sizes[0]); printf("=== 性能测试 ===\n"); for (int t = 0; t < nTests; t++) { int n = sizes[t]; int *arr = (int*)malloc(n * sizeof(int)); // 随机数组 for (int i = 0; i < n; i++) { arr[i] = rand() % 10000; } clock_t start = clock(); quickSort(arr, 0, n - 1); clock_t end = clock(); double time = (double)(end - start) / CLOCKS_PER_SEC * 1000; printf("n=%d: %.2f ms\n", n, time); free(arr); } } int main() { // 基本测试 int arr[] = {6, 1, 2, 7, 9, 3, 4, 5, 10, 8}; int n = sizeof(arr) / sizeof(arr[0]); printf("原数组: "); printArray(arr, n); quickSort(arr, 0, n - 1); printf("排序后: "); printArray(arr, n); // 性能测试 testPerformance(); return 0; }

运行结果：

text

原数组: 6 1 2 7 9 3 4 5 10 8 排序后: 1 2 3 4 5 6 7 8 9 10 === 性能测试 === n=1000: 0.28 ms n=10000: 2.15 ms n=50000: 12.43 ms

六、递归深度分析

6.1 最坏情况

已有序数组，未优化时递归深度 = n，可能导致栈溢出。

6.2 最好情况

每次基准都在中间，递归深度 = log₂n

6.3 优化方案

c

// 小数组优化 void quickSortOptimized(int arr[], int left, int right) { if (right - left <= 10) { insertionSort(arr, left, right); // 小数组用插入排序 return; } // 正常快排... }

七、三种分区方法对比

推荐：挖坑法最直观，前后指针法效率略高。

八、复杂度分析

九、小结

这一篇我们学习了快速排序：

快速排序为什么快：

• 内部循环简单，常数因子小

• 数据移动少，缓存友好

• 分治策略充分利用了CPU缓存

下一篇我们讲选择排序。

十、思考题

1. 快排的三种分区方法，哪种最不容易出错？为什么？

2. 三数取中法为什么能避免最坏情况？还有更好的基准选择方法吗？

3. 如果数组中有大量重复元素，快排会有什么问题？如何优化？

4. 尝试实现非递归版本的快速排序（用栈模拟递归）。

欢迎在评论区讨论你的答案。