企业官网建设流程全解析

引言

前面我们学习了冒泡、选择、插入、基数四种排序。今天要讲的快速排序，是二十世纪十大算法之一，也是实际工程中最常用的排序算法。C 语言的qsort、C++ 的std::sort、Java 的Arrays.sort，底层都是快速排序或其变体。

快速排序的核心是分治思想：选一个基准值，把数组分成"比基准小"和"比基准大"两半，然后递归处理两半。这种"大事化小"的策略，让它的平均时间复杂度达到了 O(n log n)，而且常数因子比归并排序和堆排序都小。

第一部分：算法思想

一、核心原理

快速排序的三步：

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

2. 划分：把小于基准的放左边，大于基准的放右边

3. 递归：对左右两部分分别重复这个过程

二、挖坑法划分过程

挖坑法口诀：左边挖坑右边填，右边挖坑左边填，左右相遇放基准。

第二部分：代码实现

一、挖坑法划分函数

int Partition(int arr[], int left, int right) { int tmp = arr[left]; // 基准值，左边留下第一个坑 while (left != right) { // 从右向左找比基准小的，填左坑 while (left < right && arr[right] > tmp) { right--; } if (left == right) break; arr[left] = arr[right]; // 小的放左边，右边留下坑 // 从左向右找比基准大的，填右坑 while (left < right && arr[left] < tmp) { left++; } if (left == right) break; arr[right] = arr[left]; // 大的放右边，左边留下坑 } arr[left] = tmp; // 基准值归位 return left; // 返回基准位置 }

二、递归版本

void Quick_Recursion(int arr[], int left, int right) { // 区间不合法或只有一个元素 → 终止 if (left >= right) return; // 划分，得到基准位置 int par = Partition(arr, left, right); // 递归处理左右两部分 Quick_Recursion(arr, left, par - 1); Quick_Recursion(arr, par + 1, right); } void Quick_Sort(int arr[], int len) { Quick_Recursion(arr, 0, len - 1); }

三、非递归版本（用栈模拟递归）

#include <stack> void Quick_Sort_No_Recursion(int arr[], int len) { std::stack<int> s; s.push(0); // 先压左边界 s.push(len - 1); // 再压右边界 while (!s.empty()) { int right = s.top(); s.pop(); // 先取右边界 int left = s.top(); s.pop(); // 再取左边界 int par = Partition(arr, left, right); // 左半部分还有多个元素 → 压栈 if (left < par - 1) { s.push(left); s.push(par - 1); } // 右半部分还有多个元素 → 压栈 if (right > par + 1) { s.push(par + 1); s.push(right); } } }

递归 vs 非递归：

第三部分：完整测试代码

#include <stdio.h> #include <stack> int Partition(int arr[], int left, int right) { int tmp = arr[left]; while (left != right) { while (left < right && arr[right] > tmp) right--; if (left == right) break; arr[left] = arr[right]; while (left < right && arr[left] < tmp) left++; if (left == right) break; arr[right] = arr[left]; } arr[left] = tmp; return left; } void Quick_Recursion(int arr[], int left, int right) { if (left >= right) return; int par = Partition(arr, left, right); Quick_Recursion(arr, left, par - 1); Quick_Recursion(arr, par + 1, right); } void Quick_Sort(int arr[], int len) { Quick_Recursion(arr, 0, len - 1); } void printArray(int arr[], int len, const char* msg) { printf("%s", msg); for (int i = 0; i < len; i++) printf("%d ", arr[i]); printf("\n"); } int main() { int arr1[] = {5, 3, 8, 1, 2, 7, 6, 4}; int len1 = sizeof(arr1) / sizeof(arr1[0]); printArray(arr1, len1, "排序前："); Quick_Sort(arr1, len1); printArray(arr1, len1, "排序后："); int arr2[] = {1, 2, 3, 4, 5, 6, 7, 8}; int len2 = sizeof(arr2) / sizeof(arr2[0]); printf("\n已有序测试：\n"); printArray(arr2, len2, "排序前："); Quick_Sort(arr2, len2); printArray(arr2, len2, "排序后："); int arr3[] = {8, 7, 6, 5, 4, 3, 2, 1}; int len3 = sizeof(arr3) / sizeof(arr3[0]); printf("\n逆序测试：\n"); printArray(arr3, len3, "排序前："); Quick_Sort(arr3, len3); printArray(arr3, len3, "排序后："); return 0; }

第四部分：算法分析

一、时间复杂度

最坏情况演示：

二、空间复杂度

三、稳定性

快速排序是不稳定的。因为划分时的跳跃式填坑会破坏相等元素的相对顺序。

第五部分：优化策略

一、三数取中法（避免最坏情况）

// 取 left、mid、right 三者的中间值作为基准 int GetMidIndex(int arr[], int left, int right) { int mid = left + (right - left) / 2; if (arr[left] < arr[mid]) { if (arr[mid] < arr[right]) return mid; else if (arr[left] < arr[right]) return right; else return left; } else { if (arr[left] < arr[right]) return left; else if (arr[mid] < arr[right]) return right; else return mid; } } int Partition_Optimized(int arr[], int left, int right) { // 三数取中，交换到 left 位置 int mid = GetMidIndex(arr, left, right); int tmp = arr[left]; arr[left] = arr[mid]; arr[mid] = tmp; // 后面和普通 Partition 一样 tmp = arr[left]; while (left != right) { while (left < right && arr[right] > tmp) right--; if (left == right) break; arr[left] = arr[right]; while (left < right && arr[left] < tmp) left++; if (left == right) break; arr[right] = arr[left]; } arr[left] = tmp; return left; }

二、小数据量切换插入排序

当区间小于一定阈值（如 16）时，插入排序比快速排序更快：

void Quick_Recursion_Optimized(int arr[], int left, int right) { if (left >= right) return; // 小数据量直接用插入排序 if (right - left + 1 <= 16) { // 插入排序... return; } int par = Partition_Optimized(arr, left, right); Quick_Recursion_Optimized(arr, left, par - 1); Quick_Recursion_Optimized(arr, par + 1, right); }

第六部分：与各排序算法对比

总结

一、核心要点

二、代码框架记忆

三、一句话记忆

快速排序选基准，小的放左大的放右，递归处理两边。平均 O(n log n) 且常数因子最小，是最快的通用排序算法。但最坏会退化到 O(n²)，需要用三数取中优化。