- 正确答案：快速排序是一种基于分治思想的高效排序算法，通过选择一个基准元素（pivot），将数组划分为左右两个子数组，左侧元素均小于等于基准，右侧元素均大于基准，然后递归地对左右子数组进行快排，最终完成整个数组的排序。 - 解答思路： 1. 从数组中选择一个元素作为基准（pivot），通常可以选择第一个、最后一个或中间元素，也可以使用随机选择以优化性能。 2. 使用双指针法（或挖坑法、前后指针法）对数组进行分区（partition），使得比基准小的元素放在左边，比基准大的放在右边。 3. 递归地对基准左侧和右侧的子数组调用快排函数。 4. 递归终止条件是子数组长度为0或1。 - 深度知识讲解：快速排序的核心在于“分治”和“原地分区”。其平均时间复杂度为 O(n log n)，最坏情况下（如每次选到最大或最小值作为基准）为 O(n²)，但通过随机化基准选择可显著降低最坏情况发生的概率。空间复杂度主要来自递归调用栈，平均为 O(log n)。分区（partition）是快排的关键步骤。常见的实现方式有： 1. **双边扫描法（双指针法）**：定义左右两个指针，分别从数组两端向中间扫描，左指针找大于 pivot 的元素，右指针找小于 pivot 的元素，找到后交换两者位置，直到指针相遇。 2. **单边扫描法（从前向后）**：维护一个边界指针，指向当前已处理部分中小于 pivot 的最后一个位置，遍历数组时若遇到小于 pivot 的元素就将其与边界下一个位置交换。 3. **挖坑法**：类似双指针，但用“坑位”概念代替直接交换，便于理解。快排是不稳定的排序算法（相同元素的相对位置可能改变），但可以通过特定实现保持稳定性。它不适合链表结构，因为无法随机访问；但在数组上表现优异，且可原地排序，节省内存。优化点包括： - 随机选择 pivot 避免最坏情况 - 小数组时切换为插入排序 - 三路快排处理重复元素多的情况（将数组分为 <, =, > 三部分） - 代码示例（C++风格原地快排，使用双边指针法）： ``` #include using namespace std; // 分区函数：返回基准元素的最终位置 int partition(int arr[], int low, int high) { int pivot = arr[low]; // 选择第一个元素作为基准 int left = low; int right = high; while (left < right) { // 从右往左找第一个小于 pivot 的元素 while (left < right && arr[right] >= pivot) right--; arr[left] = arr[right]; // 填入左边的坑 // 从左往右找第一个大于 pivot 的元素 while (left < right && arr[left] <= pivot) left++; arr[right] = arr[left]; // 填入右边的坑 } // left == right，此时位置为空，放入 pivot arr[left] = pivot; return left; // 返回基准的位置 } // 快速排序主函数 void quickSort(int arr[], int low, int high) { if (low < high) { int pivotIndex = partition(arr, low, high); quickSort(arr, low, pivotIndex - 1); // 排左半部分 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[] = {64, 34, 25, 12, 22, 11, 90}; 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; } ``` - 扩展知识点： - **三路快排（Dijkstra 三色旗问题）**：适用于大量重复元素的场景，将数组分为三段：小于 pivot、等于 pivot、大于 pivot。可以在线性时间内完成排序（当所有元素相等时）。 - **非递归实现**：使用栈模拟递归过程，避免深度递归导致栈溢出。 - **std::sort 实现**：C++ STL 中的 sort() 通常采用 introsort（内省排序），结合了快排、堆排序和插入排序，保证最坏情况下的 O(n log n) 性能。掌握快排不仅要求能手写代码，还需理解其性能边界、适用场景及优化策略，是校园招聘中高频考察的基础算法之一。

京东一面

全站热榜

创作者周榜