Java面试之常用的排序算法及其复杂度分析_网络技术

Java面试之常用的排序算法及其复杂度分析

发布时间 - 2026-01-06 00:00:00 点击率：次

冒泡排序因逻辑直观、易暴露边界漏洞而常被面试考察，时间复杂度恒为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。

建堆后，每次取出最大值（arr[0]）与末尾交换，再对剩余部分 siftDown(0)，共 n-1 次，每次 O(log n)
堆排序是原地的，但不稳定——相同元素在下沉过程中可能跨过彼此改变顺序
面试若被问“什么时候选堆排序”，答：内存受限 + 要求最坏 O(n log n) + 不关心稳定性（如 Top-K 问题）

实际编码中，除非特定约束，否则直接用 Arrays.sort()。手写排序算法的价值不在替代它，而在暴露你对数据移动、比较次数、内存访问模式的直觉——这些细节，往往比背下复杂度公式更重要。

# java # 编码 # app # 排序算法 # 冒泡排序 # 为什么

相关栏目：【网站优化151355 】【网络推广146373 】【网络技术251813 】【 AI营销90571 】

上一篇：wps 表格怎么求积_WPS表格求积公式计算方法【教程】

下一篇：车厘子应该怎么清洗食用碱清洗步骤详解

相关栏目网站优化
网络推广
网络技术
AI营销

最新文章 Sublime怎么一键压缩JS代码 Su sublime如何在搜索中使用正则表达式 Sublime如何设置透明窗口效果 Su mysql如何设计商品表结构_mysql css属性背景图不显示怎么办_通过检查路如何使用Golang实现排序_Golan 农历闰月是怎么回事_为合回归年加一月调整塑造《刺客信条》艾吉奥传奇的编剧离开育碧 1英里等于多少公里 1mile和km的换 css grid布局中行和列是如何定义的 PS批量旋转和翻转图片，快速校正图片方向 C# Swagger UI自定义方法 C OPPO手机九宫格和全键盘怎么切换_OP Go语言如何实现用户登录注册_Golan 1节飞行速度多少公里每小时 1节是多少公纸嫁衣8千子树第五章庙门怎么开启庙门 Laravel 多行数据编辑表单中实现逐明日之后如何提升钓鱼等级明日之后提升钓支付宝怎样查年度账单_支付宝年度账单查看 C# 多线程UI更新Dispatcher

上一篇：wps 表格怎么求积_WPS表格求积公式计算方法【教程】

下一篇：车厘子应该怎么清洗食用碱清洗步骤详解