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

一、快速排序的基本思想1.1 分治策略选择基准从数组中选一个元素作为基准pivot分区重新排列数组比基准小的放左边大的放右边递归对左右两个子数组递归执行上述过程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法左右指针法思路选最左或最右为基准左指针找比基准大的右指针找比基准小的交换直到左右指针相遇基准归位cint 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 挖坑法思路选基准挖出形成坑位右指针找比基准小的填左坑右坑形成左指针找比基准大的填右坑左坑形成重复直到左右相遇把基准填回cint 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 前后指针法思路选最右为基准prev指向小于基准区域的末尾cur遍历当cur找到比基准小的prev交换arr[prev]和arr[cur]最后把基准放到prev1位置cint 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; }三、递归实现快速排序cvoid 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] → 递归深度54.2 三数取中取左、中、右三个位置的中位数作为基准避免选到极端值。cint 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 性能测试 n1000: 0.28 ms n10000: 2.15 ms n50000: 12.43 ms六、递归深度分析6.1 最坏情况已有序数组未优化时递归深度 n可能导致栈溢出。6.2 最好情况每次基准都在中间递归深度 log₂n6.3 优化方案优化方法作用三数取中避免选到极端基准小数组用插入排序减少递归深度尾递归优化减少栈空间c// 小数组优化 void quickSortOptimized(int arr[], int left, int right) { if (right - left 10) { insertionSort(arr, left, right); // 小数组用插入排序 return; } // 正常快排... }七、三种分区方法对比方法思路交换次数代码复杂度稳定性Hoare法左右指针交换较多中等不稳定挖坑法填坑式移动较少简单不稳定前后指针法单次遍历交换最少中等不稳定推荐挖坑法最直观前后指针法效率略高。八、复杂度分析情况时间复杂度空间复杂度最好均匀分割O(n log n)O(log n)平均O(n log n)O(log n)最坏已有序O(n²)O(n)九、小结这一篇我们学习了快速排序要点说明核心思想分治法选基准分区递归Hoare法左右指针交换最后基准归位挖坑法填坑式移动代码简洁前后指针法单次遍历效率略高三数取中避免最坏情况提高稳定性时间复杂度平均 O(n log n)快速排序为什么快内部循环简单常数因子小数据移动少缓存友好分治策略充分利用了CPU缓存下一篇我们讲选择排序。十、思考题快排的三种分区方法哪种最不容易出错为什么三数取中法为什么能避免最坏情况还有更好的基准选择方法吗如果数组中有大量重复元素快排会有什么问题如何优化尝试实现非递归版本的快速排序用栈模拟递归。欢迎在评论区讨论你的答案。