排序与搜索算法

介绍

排序和搜索是算法面试的”地基”。很多复杂问题的第一步就是”先排个序”，然后用二分查找或其他技巧求解。

模式识别：看到”已排序数组”→ 立刻想二分查找；看到”需要排序 + 搜索”→ 先排再搜（排序 O(n log n) + 每次搜索 O(log n)）。

时间复杂度概述

算法	平均	最坏	空间	稳定性
二分查找	O(log n)	O(log n)	O(1)	—
快速排序	O(n log n)	O(n²)	O(log n)	不稳定
归并排序	O(n log n)	O(n log n)	O(n)	稳定
冒泡排序	O(n²)	O(n²)	O(1)	稳定

排序算法选择指南

• 快排：实际应用中最快（常数因子小），适合内存内排序，但不稳定
• 归并排序：稳定，适合链表排序和外部排序，需要额外 O(n) 空间
• 冒泡排序：简单但慢，仅适合教学和小规模数据

---

Binary Search

二分查找是最基础的搜索算法，也是很多高级算法（快排、归并排序）的思想来源。

前提：数据已排序。

核心思想：每次取中间元素，和目标值比较，决定在左半区还是右半区继续查找。每次排除一半数据。

关键点1 — mid 的选取：

• 靠左：mid = (left + right) / 2（偶数个时取左边）
• 靠右：mid = (left + right + 1) / 2（偶数个时取右边）
• 防溢出写法：mid = left + (right - left) / 2

关键点2 — 循环退出条件：

• 找到 target：直接返回
• 左右指针交叉（left > right）：未找到
• 左右指针相遇（left == right）：视具体问题处理

Code Challenge: First Bad Version

问题：产品有 n 个版本 1-n，某个版本开始出问题，之后所有版本都有问题。用最少的 API 调用找出第一个出问题的版本。

public int firstBadVersion(int n) {
    int left = 1, right = n;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (isBadVersion(mid)) {
            right = mid;        // mid is bad, first bad is at or before mid
        } else {
            left = mid + 1;     // mid is good, first bad is after mid
        }
    }
    return left;
}

Code Challenge: Search in Rotated Sorted Array

问题：一个原本升序的数组在某个未知 pivot 处旋转，在该数组中搜索目标值。O(log n)。

核心思路：二分后，mid 一定落在左半有序段或右半有序段中。判断 target 在哪个有序段内，收缩搜索范围。

public int search(int[] nums, int target) {
    int left = 0, right = nums.length - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) return mid;

        // left half is sorted
        if (nums[left] <= nums[mid]) {
            if (nums[left] <= target && target < nums[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        // right half is sorted
        } else {
            if (nums[mid] < target && target <= nums[right]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
    }
    return -1;
}

---

Quick Sort

核心思想：选一个 pivot，把小于 pivot 的放左边，大于 pivot 的放右边，然后递归处理左右两部分。

步骤：

1. 选择一个 pivot（通常取中间元素）
2. 分区 (Partition)：重新排列，使左边全比 pivot 小，右边全比 pivot 大
3. 递归排序左右子数组

复杂度：

• 平均 O(n log n)：二分 O(log n) 层 × 每层遍历 O(n)
• 最坏 O(n²)：每次 pivot 都是极值，退化为冒泡（可通过随机选 pivot 优化）

Code Challenge: Sort an Array

public void quickSort(int[] arr, int left, int right) {
    if (left >= right) return;

    int pivotIndex = partition(arr, left, right);
    quickSort(arr, left, pivotIndex - 1);
    quickSort(arr, pivotIndex, right);
}

private int partition(int[] arr, int left, int right) {
    int pivot = arr[left + (right - left) / 2];
    int i = left, j = right;

    while (i <= j) {
        while (arr[i] < pivot) i++;
        while (arr[j] > pivot) j--;
        if (i <= j) {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            i++;
            j--;
        }
    }
    return i; // index for next split
}

---

Merge Sort

核心思想：分治的经典应用 — 将数组递归地分成两半，分别排序，然后合并两个有序子数组。

优势：

• 稳定排序（保持相等元素的相对顺序）
• 适合排序链表（不需要随机访问）
• 适合外部排序（数据量超过内存）

Code Challenge: Sort an Array

public void mergeSort(int[] arr, int left, int right) {
    if (left >= right) return;

    int mid = left + (right - left) / 2;
    mergeSort(arr, left, mid);
    mergeSort(arr, mid + 1, right);
    merge(arr, left, mid, right);
}

private void merge(int[] arr, int left, int mid, int right) {
    int[] temp = new int[right - left + 1];
    int i = left, j = mid + 1, k = 0;

    while (i <= mid && j <= right) {
        temp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
    }
    while (i <= mid) temp[k++] = arr[i++];
    while (j <= right) temp[k++] = arr[j++];

    System.arraycopy(temp, 0, arr, left, temp.length);
}

Code Challenge: Merge Two Sorted Lists

归并排序的核心就是”合并两个有序序列”，这个子操作经常单独作为面试题出现。

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0);
    ListNode curr = dummy;

    while (l1 != null && l2 != null) {
        if (l1.val <= l2.val) {
            curr.next = l1;
            l1 = l1.next;
        } else {
            curr.next = l2;
            l2 = l2.next;
        }
        curr = curr.next;
    }

    curr.next = (l1 != null) ? l1 : l2; // attach the rest
    return dummy.next;
}

---

Bubble Sort

核心思想：重复比较相邻元素，顺序错误则交换。每轮遍历让最大的元素”冒泡”到最后。

虽然时间复杂度 O(n²) 不适合实际使用，但它的思路简单直观，常用于教学和启发其他算法（比如堆的构造也是类似的冒泡过程）。

---

关键技巧

• 看到”已排序” → 立刻想二分查找 — O(log n) 是有序数据的最强武器
• 快排是实际最快的通用排序 — 常数因子小，cache 友好，但不稳定。需要稳定用归并
• 归并排序 = 分治模板 — 分解→解决→合并，这个思路也适用于非排序问题
• 冒泡排序不用背代码 — 理解其”冒泡交换”思想即可，堆的维护用的就是同一套逻辑
• mid 防溢出是细节分 — left + (right - left) / 2 比 (left + right) / 2 安全，面试官会注意
• 二分不一定找 exact match — First Bad Version 找的是边界条件，理解 left < right vs left <= right 的区别

参考资料

• Quick Sort — AlgoList
• Merge Sort — AlgoList