- 正确答案：快速排序是一种基于分治策略的高效排序算法，其核心思想是选择一个基准元素（pivot），将数组划分为两个子数组，其中一个子数组的所有元素都小于等于基准值，另一个子数组的所有元素都大于基准值，然后递归地对这两个子数组进行快速排序。 - 解答思路： 1. 从数组中选择一个元素作为基准（pivot），通常可以选择第一个、最后一个或中间元素，也可以使用随机选择以优化性能。 2. 使用双指针技术（左右指针）对数组进行分区（partition）操作：左指针从起始位置向右移动，寻找大于等于 pivot 的元素；右指针从末尾向左移动，寻找小于等于 pivot 的元素。当两个指针都停下时，若左指针仍在右指针左侧，则交换两元素。 3. 当左右指针相遇后，将基准元素与右指针所指元素交换（此时右指针指向的位置是 pivot 应在的正确位置）。 4. 递归地对基准左侧和右侧的子数组进行快速排序。 5. 递归终止条件是子数组长度小于等于1。 - 深度知识讲解：快速排序属于典型的分治算法（Divide and Conquer）。它的时间复杂度依赖于分区的平衡性： - 最好情况：每次划分都能将数组等分为两部分，时间复杂度为 O(n log n)。 - 平均情况：期望时间复杂度也为 O(n log n)，适用于大多数随机数据。 - 最坏情况：每次选择的 pivot 都是最大或最小值（如已排序数组且选首/尾为 pivot），导致划分极度不平衡，退化为 O(n^2)。空间复杂度主要来自递归调用栈： - 最好情况：递归深度为 O(log n)，空间复杂度为 O(log n)。 - 最坏情况：递归深度为 O(n)，空间复杂度为 O(n)。快速排序是不稳定的排序算法，因为在交换过程中可能改变相同元素的相对顺序。为了提升性能，常见的优化手段包括： 1. 随机化选择 pivot（Randomized Quick Sort） 2. 三数取中法（median-of-three）选择 pivot 3. 对小规模子数组使用插入排序 4. 尾递归优化减少栈空间使用 5. 三路快排（Dutch National Flag Partition）处理重复元素多的情况分区方式有多种实现，常见的是 Lomuto 分区和 Hoare 分区： - Lomuto：代码简洁，但效率略低，容易理解。 - Hoare：原始版本，使用双向扫描，效率更高，但边界处理稍复杂。 - 代码示例（使用 Hoare 分区 + 递归实现）： ``` #include using namespace std; // 交换两个元素 void swap(int &a, int &b) { int temp = a; a = b; b = temp; } // Hoare 分区方法 int partition(int arr[], int low, int high) { int pivot = arr[low]; // 选择第一个元素作为基准 int i = low - 1; int j = high + 1; while (true) { // 从左往右找第一个大于等于 pivot 的元素 do { i++; } while (arr[i] < pivot); // 从右往左找第一个小于等于 pivot 的元素 do { j--; } while (arr[j] > pivot); // 如果指针相遇，则完成分区 if (i >= j) return j; // 否则交换元素 swap(arr[i], arr[j]); } } // 快速排序主函数 void quicksort(int arr[], int low, int high) { if (low < high) { // 获取分区点 int pivotIndex = partition(arr, low, high); // 递归排序左右两部分 quicksort(arr, low, pivotIndex); // 注意：Hoare 分区返回的是右子数组的起始前一位 quicksort(arr, pivotIndex + 1, high); } } // 打印数组 void printArray(int arr[], int size) { for (int i = 0; i < size; i++) cout << arr[i] << " "; cout << endl; } ``` - 使用示例： ``` int main() { int arr[] = {10, 7, 8, 9, 1, 5}; int n = sizeof(arr) / sizeof(arr[0]); cout << "Original array: "; printArray(arr, n); quicksort(arr, 0, n - 1); cout << "Sorted array: "; printArray(arr, n); return 0; } ``` - 补充说明：若采用 Lomuto 分区，代码如下： ``` int lomuto_partition(int arr[], int low, int high) { int pivot = arr[high]; // 选择最后一个元素为基准 int i = low - 1; // 小于 pivot 的区域的右边界 for (int j = low; j < high; j++) { if (arr[j] <= pivot) { i++; swap(arr[i], arr[j]); } } swap(arr[i + 1], arr[high]); return i + 1; } ``` 该版本更直观，但比 Hoare 多做很多无效交换（比如所有元素都小于 pivot 时仍会频繁交换）。总结：手撕快排时推荐使用 Hoare 分区或 Lomuto 分区均可，关键在于逻辑清晰、边界正确。面试中应主动说明时间复杂度、稳定性、优化方式等扩展内容，体现深度理解。

京东科技 搜推广开发岗

全站热榜

创作者周榜

京东科技搜推广开发岗