题目 1快速排序实现与优化题目描述实现快速排序并说明常见的优化手段。解题思路核心思想分治 划分。选取一个基准值将数组划分为小于基准和大于基准两部分然后递归排序左右区间。常见优化点随机选基准 / 三数取中避免有序数组最坏情况小区间改用插入排序减少递归开销三路划分优化大量重复元素场景代码实现三数取中优化版cpp运行int median3(vectorint 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(vectorint 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(vectorint nums, vectorint 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(vectorint nums, vectorint 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(vectorint nums) { vectorint temp(nums.size()); return mergeSort(nums, temp, 0, nums.size() - 1); }复杂度分析时间复杂度O (n log n)空间复杂度O (n)辅助数组开销面试考点归并排序的经典应用考察对归并过程的理解。延伸问归并排序的稳定性外排序中的应用题目 3堆排序与 TopK 问题题目描述实现堆排序并说明如何用堆解决 TopK 问题找出数组中第 k 大的元素。解题思路堆排序两步建大顶堆不断将堆顶与末尾元素交换调整堆直到整个数组有序TopK 问题 找第 k 大用小顶堆维护一个大小为 k 的小顶堆遍历数组元素大于堆顶则入堆并弹出堆顶最终堆顶就是第 k 大元素。代码实现cpp运行// 堆排序 void adjustHeap(vectorint 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(vectorint 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(vectorint nums, int k) { priority_queueint, vectorint, greaterint 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、优先级队列堆整数、范围有限计数排序、基数排序线性时间面试考点排序算法的基础理论题考察知识体系的完整性。面试官常结合具体场景让你选择排序算法并说明理由。谢谢