冒泡排序因逻辑直观、易暴露边界漏洞而常被面试考察，时间复杂度恒为O(n²)，空间复杂度O(1)；关键优化是添加swapped标志实现提前终止，使最好情况达O(n)。
冒泡排序为什么在面试里总被问，但实际几乎不用
因为它的逻辑最直观，适合考察对「比较-交换」过程的理解，也容易暴露边界处理漏洞。时间复杂度固定是 O(n²)，无论最好、最坏、平均情况；空间复杂度是 O(1)（原地排序）。面试手写时，常被忽略的点是提前终止优化——如果某轮没发生任何交换，说明已有序，应直接退出。
public static void bubbleSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
boolean swapped = false;
for (int j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}
if (!swapped) break; // 关键优化，否则无法达到最好情况 O(n)
}
}- 测试用例务必包含已排序数组，验证
swapped优化是否生效 - 注意内层循环上界是
n - 1 - i，不是n - i，否则可能越界 - Java 中传入的是数组引用，无需返回值，但需明确说明这是原地修改
快速排序的 partition 实现有哪两种主流写法
面试高频考点：lomuto 和 hoare 分区方案。前者以最后一个元素为 pivot，代码简洁但对重复元素不友好；后者用首尾双指针，效率略高且天然更稳定（相同元素分布更均匀），但边界条件易错。两者平均时间复杂度都是 O(n log n)，最坏退化到 O(n²)（如已排序数组选端点作 pivot），必须强调随机化 pivot 或三数取中来缓解。
// Lomuto 风格（推荐面试写，逻辑清晰）
private static int partition(int[] arr, int low, int high) {
int pivot = arr[high]; // 取末尾为 pivot
int i = low - 1; // i 指向小于 pivot 的右边界
for (int j = low; j < high; j++) {
if (arr[j] <= pivot) {
i++;
swap(arr, i, j);
}
}
swap(arr, i + 1, high);
return i + 1;
}-
hoare版本中，两个指针从两端向中间走，首次相遇位置不一定是 pivot 最终位置，需额外判断 - 递归调用时，
lomuto的左右区间是[low, pi-1]和[pi+1, high]；hoare是[low, pi]和[pi+1, high]，容易混淆 - Java 8 的
Arrays.sort(int[])对基本类型用的是双轴快排（Dual-Pivot Quicksort），不是单 pivot，这点可作为延伸加分项
归并排序如何体现“稳定”和“非原地”的本质特征
稳定性意味着相等元素的相对顺序不变，归并排序天然满足——合并时若 left[i] == right[j]，优先取 left[i] 即可。但它需要额外 O(n) 空间存临时数组，不是原地算法。时间复杂度严格是 O(n log n)，不受输入数据影响，适合对最坏性能有要求的场景（比如实时系统）。
private static void mergeSort(int[] arr, int[] temp, int left, int right) {
if (left >= right) return;
int mid = left + (right - left) / 2;
mergeSort(arr, temp, left, mid);
mergeSort(arr, temp, mid + 1, right);
merge(arr, temp, left, mid, right);
}
private static void merge(int[] arr, int[] temp, int left, int mid, int right) {
System.arraycopy(arr, left, temp, left, right - left + 1);
int i = left, j = mid + 1, k = left;
while (i <= mid && j <= right) {
if (temp[i] <= temp[j]) { // 注意这里是 <=，保证稳定性
arr[k++] = temp[i++];
} else {
arr[k++] = temp[j++];
}
}
while (i <= mid) arr[k++] = temp[i++];
while (j <= right) arr[k++] = temp[j++];
}
- 面试手写常漏掉
System.arraycopy这一步，直接在原数组上合并会导致数据覆盖 - 递归入口需传入辅助数组
temp，避免每层都 new，否则空间复杂度变成O(n log n) - 堆排序虽也是
O(n log n)，但不稳定，且实际性能通常不如优化后的快排或归并
堆排序建堆过程为何是 O(n)，而不是直觉上的 O(n log n)
关键在自底向上调整（siftDown）的代价分析：叶子节点不用调整；倒数第二层最多下沉 1 层；倒数第三层最多下沉 2 层……数学推导可得总操作数上限是 2n。而如果用 n 次 insert（即自顶向下 siftUp），才是 O(n log n)。Java 中没有内置二叉堆类支持索引访问，手写时要注意数组下标从 0 开始时，左子节点是 2*i + 1，不是 2*i。
立即学习“Java免费学习笔记（深入）”；
- 建堆后，每次取出最大值（
arr[0]）与末尾交换，再对剩余部分siftDown(0)，共n-1次，每次O(log n) - 堆排序是原地的，但不稳定——相同元素在下沉过程中可能跨过彼此改变顺序
- 面试若被问“什么时候选堆排序”，答：内存受限 + 要求最坏
O(n log n)+ 不关心稳定性（如 Top-K 问题）
实际编码中，除非特定约束，否则直接用 Arrays.sort()。手写排序算法的价值不在替代它，而在暴露你对数据移动、比较次数、内存访问模式的直觉——这些细节，往往比背下复杂度公式更重要。
