- 正确答案：快速排序是一种基于分治思想的排序算法，通过选择一个基准元素（pivot），将数组划分为左右两个子数组，左边的元素都小于等于基准，右边的元素都大于等于基准，然后递归地对左右子数组进行快排，最终完成整个数组的排序。 - 解答思路： 1. 从数组中选择一个元素作为基准（pivot），通常可以选择第一个、最后一个或中间位置的元素，也可以使用随机选择来优化性能。 2. 使用双指针技术（left 和 right）对当前数组区间进行划分：left 指针从左向右移动，寻找大于 pivot 的元素；right 指针从右向左移动，寻找小于 pivot 的元素。当两个指针都停下时，如果 left ≤ right，则交换这两个元素。 3. 重复步骤2，直到 left > right。此时将 pivot 放到正确的位置（即 right 所在位置），使得左侧所有元素 ≤ pivot，右侧所有元素 ≥ pivot。 4. 递归地对 pivot 左右两个子区间调用快排函数，直到子区间长度为0或1为止。 - 深度知识讲解：快速排序的核心是“分治法”（Divide and Conquer）。它将大规模问题分解成小规模子问题处理。其时间复杂度分析如下： - 最好情况：每次划分都能将数组均分为两部分，递归深度为 O(log n)，每层总操作数为 O(n)，所以最好时间复杂度为 O(n log n)。 - 平均情况：仍然是 O(n log n)，即使划分不完全均匀，只要不是极端偏斜，期望性能仍然很好。 - 最坏情况：每次选的 pivot 都是最大或最小值（如已排序数组且选首/尾为 pivot），导致一端为空，另一端有 n-1 个元素，递归深度变为 O(n)，总时间复杂度退化为 O(n²)。空间复杂度主要来自递归调用栈。最好情况下栈深度为 O(log n)，最坏为 O(n)。快排是原地排序算法（in-place），不需要额外存储空间（除了递归栈）。不稳定性说明：由于元素可能跨区域交换，相同值的相对顺序可能改变，因此快排是**不稳定排序**。优化策略包括： - 随机化选择 pivot 可避免最坏情况出现在特定输入上； - 三数取中法（median-of-three）选择首、中、尾三个元素的中位数作为 pivot； - 当子数组较小时（如 < 10），切换到插入排序以减少递归开销； - 使用双路快排或三路快排（Dutch National Flag）处理大量重复元素。特别地，三路快排将数组分为三部分：< pivot、= pivot、> pivot，适合含大量重复元素的数据，在 Java 的 `Arrays.sort()` 中对基本类型就采用了类似方法。 - 代码示例（C++风格原地快排，经典双指针版本）： ``` #include using namespace std; void quickSort(int arr[], int low, int high) { if (low >= high) return; // 终止条件 int pivot = arr[low]; // 选择第一个元素为基准 int left = low; int right = high; while (left < right) { // 先从右往左找小于pivot的数 while (left < right && arr[right] >= pivot) right--; // 再从左往右找大于pivot的数 while (left < right && arr[left] <= pivot) left++; // 交换 if (left < right) { swap(arr[left], arr[right]); } } // 将pivot放到最终位置 arr[low] = arr[left]; arr[left] = pivot; // 递归左右区间 quickSort(arr, low, left - 1); quickSort(arr, left + 1, high); } // 调用示例 int main() { int arr[] = {64, 34, 25, 12, 22, 11, 90}; int n = sizeof(arr)/sizeof(arr[0]); quickSort(arr, 0, n - 1); for (int i = 0; i < n; ++i) cout << arr[i] << " "; cout << endl; return 0; } ``` 另一种更清晰的写法是采用 Hoare 分区（原始版）或 Lomuto 分区（简化版）。上面实现的是Hoare变种，但最后把 pivot 归位的方式稍作调整。 Lomuto分区伪代码（更易理解）： ``` function partition(arr, low, high): pivot = arr[high] // 以最后一个为基准 i = low - 1 // 小于区间的右边界 for j = low to high - 1: if arr[j] <= pivot: i = i + 1 swap(arr[i], arr[j]) swap(arr[i+1], arr[high]) return i + 1 function quickSort(arr, low, high): if low < high: pi = partition(arr, low, high) quickSort(arr, low, pi - 1) quickSort(arr, pi + 1, high) ``` 总结：手撕快排不仅要能写出代码，还要清楚其分区逻辑、边界控制、递归结构和潜在陷阱（如死循环、越界、错误归位等）。建议多练习不同分区方式，并理解其适用场景与优化手段。

荣耀10.10号一面

全站热榜

创作者周榜