企业官网建设流程全解析

题目 1：快速排序实现与优化

题目描述

实现快速排序，并说明常见的优化手段。

解题思路

核心思想：分治 + 划分。选取一个基准值，将数组划分为小于基准和大于基准两部分，然后递归排序左右区间。

常见优化点：

1. 随机选基准 / 三数取中，避免有序数组最坏情况
2. 小区间改用插入排序，减少递归开销
3. 三路划分，优化大量重复元素场景

代码实现（三数取中优化版）

cpp

运行

int median3(vector<int>& arr, int lo, int hi) { int mid = lo + (hi - lo) / 2; if (arr[lo] > arr[mid]) swap(arr[lo], arr[mid]); if (arr[lo] > arr[hi]) swap(arr[lo], arr[hi]); if (arr[mid] > arr[hi]) swap(arr[mid], arr[hi]); swap(arr[mid], arr[hi - 1]); return arr[hi - 1]; } void quickSort(vector<int>& arr, int lo, int hi) { if (hi - lo + 1 <= 16) { // 小区间用插入排序优化 for (int i = lo + 1; i <= hi; i++) { int temp = arr[i]; int j = i - 1; while (j >= lo && arr[j] > temp) { arr[j + 1] = arr[j]; j--; } arr[j + 1] = temp; } return; } int pivot = median3(arr, lo, hi); int i = lo, j = hi - 1; while (true) { while (arr[++i] < pivot); while (arr[--j] > pivot); if (i < j) swap(arr[i], arr[j]); else break; } swap(arr[i], arr[hi - 1]); quickSort(arr, lo, i - 1); quickSort(arr, i + 1, hi); }

复杂度分析

• 平均时间复杂度：O (n log n)
• 最坏时间复杂度：O (n²)，优化后概率极低
• 空间复杂度：O (log n)，递归栈开销

面试考点

排序算法核心题。面试官常问：快排为什么快？（缓存友好、常数小）快排的稳定性？和归并排序的对比？

题目 2：归并排序与逆序对问题

题目描述

实现归并排序，并求解数组中的逆序对总数。逆序对指数组中满足i < j且nums[i] > nums[j]的数对。

解题思路

归并排序分「分」和「治」两步：将数组一分为二，递归排序左右子数组，再合并两个有序数组。

求逆序对：在合并两个有序数组时，如果右数组元素小于左数组当前元素，说明左数组剩余所有元素都与该右元素构成逆序对，累加计数即可。

代码实现

cpp

运行

int merge(vector<int>& nums, vector<int>& temp, int left, int mid, int right) { int i = left, j = mid + 1, k = left; int count = 0; while (i <= mid && j <= right) { if (nums[i] <= nums[j]) { temp[k++] = nums[i++]; } else { temp[k++] = nums[j++]; count += mid - i + 1; // 累加逆序对 } } while (i <= mid) temp[k++] = nums[i++]; while (j <= right) temp[k++] = nums[j++]; for (int p = left; p <= right; p++) { nums[p] = temp[p]; } return count; } int mergeSort(vector<int>& nums, vector<int>& temp, int left, int right) { if (left >= right) return 0; int mid = left + (right - left) / 2; int count = 0; count += mergeSort(nums, temp, left, mid); count += mergeSort(nums, temp, mid + 1, right); count += merge(nums, temp, left, mid, right); return count; } int reversePairs(vector<int>& nums) { vector<int> temp(nums.size()); return mergeSort(nums, temp, 0, nums.size() - 1); }

复杂度分析

• 时间复杂度：O (n log n)
• 空间复杂度：O (n)，辅助数组开销

面试考点

归并排序的经典应用，考察对归并过程的理解。延伸问：归并排序的稳定性？外排序中的应用？

题目 3：堆排序与 TopK 问题

题目描述

实现堆排序，并说明如何用堆解决 TopK 问题（找出数组中第 k 大的元素）。

解题思路

堆排序两步：

1. 建大顶堆
2. 不断将堆顶与末尾元素交换，调整堆，直到整个数组有序

TopK 问题： 找第 k 大用小顶堆：维护一个大小为 k 的小顶堆，遍历数组，元素大于堆顶则入堆并弹出堆顶，最终堆顶就是第 k 大元素。

代码实现

cpp

运行

// 堆排序 void adjustHeap(vector<int>& arr, int i, int len) { int temp = arr[i]; for (int child = 2 * i + 1; child < len; child = 2 * child + 1) { if (child + 1 < len && arr[child + 1] > arr[child]) { child++; } if (temp >= arr[child]) break; arr[i] = arr[child]; i = child; } arr[i] = temp; } void heapSort(vector<int>& arr) { int n = arr.size(); // 建堆 for (int i = n / 2 - 1; i >= 0; i--) { adjustHeap(arr, i, n); } // 排序 for (int i = n - 1; i > 0; i--) { swap(arr[0], arr[i]); adjustHeap(arr, 0, i); } } // TopK：第k大元素 int findKthLargest(vector<int>& nums, int k) { priority_queue<int, vector<int>, greater<int>> minHeap; // 小顶堆 for (int num : nums) { if (minHeap.size() < k) { minHeap.push(num); } else if (num > minHeap.top()) { minHeap.pop(); minHeap.push(num); } } return minHeap.top(); }

复杂度分析

• 堆排序：时间 O (n log n)，空间 O (1)
• TopK 小顶堆法：时间 O (n log k)，空间 O (k)

面试考点

堆的核心应用。面试官常对比：快排选择法 vs 堆解法，各自的适用场景（海量数据、流数据）。

题目 4：排序算法稳定性与选型

题目描述

什么是排序算法的稳定性？常见排序算法哪些是稳定的？实际开发中如何选型？

详细讲解

1. 稳定性定义

如果排序后，两个相等元素的相对位置保持不变，则该排序算法是稳定的；反之则不稳定。 例如原数组[2a, 1, 2b]（两个 2 位置不同），稳定排序后 2a 仍在 2b 前面，不稳定排序则可能交换。

2. 常见算法稳定性分类

表格

3. 实际选型原则

• 追求平均速度：优先快排，工程中一般用优化版快排（自省排序）
• 要求稳定排序：选归并排序，数据量小时可选插入排序
• 海量数据、内存不足：归并排序（外排序）
• TopK、优先级队列：堆
• 整数、范围有限：计数排序、基数排序（线性时间）

面试考点

排序算法的基础理论题，考察知识体系的完整性。面试官常结合具体场景让你选择排序算法并说明理由。