高频算法题型：排序与二分查找
2026/6/27大约 11 分钟
高频算法题型：排序与二分查找
高频算法题型：排序与二分查找是计算机科学的核心，它为问题解决提供了高效的计算方法。
本文介绍了高频算法题型：排序与二分查找的设计思路和实现方式，帮助你提升编程能力。
| 排序算法 | 平均时间 | 最坏时间 | 空间 | 稳定性 | 适用场景 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n²) | O(n²) | O(1) | ✅ 稳定 | 教学 |
| 选择排序 | O(n²) | O(n²) | O(1) | ❌ 不稳定 | 教学 |
| 插入排序 | O(n²) | O(n²) | O(1) | ✅ 稳定 | 小数据/近乎有序 |
| 希尔排序 | O(n^1.3) | O(n²) | O(1) | ❌ | 中等数据 |
| 归并排序 | O(n log n) | O(n log n) | O(n) | ✅ 稳定 | 大数据/外部排序 |
| 快速排序 | O(n log n) | O(n²) | O(log n) | ❌ | 通用排序首选 |
| 堆排序 | O(n log n) | O(n log n) | O(1) | ❌ | 内存受限 |
| 计数排序 | O(n+k) | O(n+k) | O(k) | ✅ | 值域小 |
| 桶排序 | O(n+k) | O(n²) | O(n+k) | ✅ | 均匀分布 |
| 基数排序 | O(d×n) | O(d×n) | O(n+d) | ✅ | 多关键字 |
稳定性：相等元素的相对顺序排序后不变。场景：先按成绩排，再按班级排，稳定的排序能保持成绩顺序。
1.2 面试常考的五个排序
面试中需要手写的排序通常有：快速排序、归并排序、堆排序、插入排序、冒泡排序。
二、五大排序实现
2.1 快速排序 ⭐
public void quickSort(int[] nums, int left, int right) {
if (left >= right) return;
int pivot = partition(nums, left, right);
quickSort(nums, left, pivot - 1);
quickSort(nums, pivot + 1, right);
}
private int partition(int[] nums, int left, int right) {
// 随机选 pivot，避免最坏情况
int randomIdx = left + (int)(Math.random() * (right - left + 1));
swap(nums, randomIdx, right);
int pivot = nums[right];
int i = left; // i 指向下一个放小元素的位置
for (int j = left; j < right; j++) {
if (nums[j] < pivot) {
swap(nums, i, j);
i++;
}
}
swap(nums, i, right);
return i;
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}关键点：
- 随机选 pivot 避免最坏 O(n²)
- Lomuto 分区法（上面的写法）或 Hoare 分区法
- 不稳定排序
2.2 归并排序
public void mergeSort(int[] nums, int left, int right) {
if (left >= right) return;
int mid = left + (right - left) / 2;
mergeSort(nums, left, mid);
mergeSort(nums, mid + 1, right);
merge(nums, left, mid, right);
}
private void merge(int[] nums, 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) {
if (nums[i] <= nums[j]) {
temp[k++] = nums[i++];
} else {
temp[k++] = nums[j++];
}
}
while (i <= mid) temp[k++] = nums[i++];
while (j <= right) temp[k++] = nums[j++];
System.arraycopy(temp, 0, nums, left, temp.length);
}优势： 稳定排序，适合链表排序、外部排序、求逆序对。
2.3 堆排序
public void heapSort(int[] nums) {
int n = nums.length;
// 建堆：从最后一个非叶子节点开始下沉
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(nums, n, i);
}
// 逐个取出堆顶（最大值）放到末尾
for (int i = n - 1; i > 0; i--) {
swap(nums, 0, i);
heapify(nums, i, 0); // 对剩余元素重新堆化
}
}
// 大顶堆下沉操作
private void heapify(int[] nums, int n, int i) {
int largest = i;
int left = 2 * i + 1, right = 2 * i + 2;
if (left < n && nums[left] > nums[largest]) largest = left;
if (right < n && nums[right] > nums[largest]) largest = right;
if (largest != i) {
swap(nums, i, largest);
heapify(nums, n, largest); // 继续下沉
}
}2.4 插入排序
public void insertionSort(int[] nums) {
for (int i = 1; i < nums.length; i++) {
int key = nums[i];
int j = i - 1;
while (j >= 0 && nums[j] > key) {
nums[j + 1] = nums[j];
j--;
}
nums[j + 1] = key;
}
}小数据量王者： 当 n < 50 时，插入排序比快排还快。Java 的
Arrays.sort()对小数组就用插入排序。
2.5 冒泡排序
public void bubbleSort(int[] nums) {
int n = nums.length;
for (int i = 0; i < n - 1; i++) {
boolean swapped = false; // 优化：没交换说明已有序
for (int j = 0; j < n - 1 - i; j++) {
if (nums[j] > nums[j + 1]) {
swap(nums, j, j + 1);
swapped = true;
}
}
if (!swapped) break;
}
}三、Java 排序 API
3.1 Arrays.sort() vs Collections.sort()
// 基本类型：双轴快速排序 (Dual-Pivot Quicksort)
int[] arr = {5, 2, 8, 1, 9};
Arrays.sort(arr);
// 对象类型：TimSort (归并排序 + 插入排序的混合)
Integer[] arr2 = {5, 2, 8, 1, 9};
Arrays.sort(arr2);
// 或
List<Integer> list = Arrays.asList(5, 2, 8, 1, 9);
Collections.sort(list);
// 自定义排序
Arrays.sort(arr2, (a, b) -> b - a); // 降序
Arrays.sort(intervals, (a, b) -> a[0] - b[0]); // 按第一个元素排序3.2 面试中的排序选择
// 按二维数组某列排序
Arrays.sort(matrix, (a, b) -> a[0] - b[0]);
// 部分排序（取前 K 个）
Arrays.sort(nums);
// 取 nums[0..k-1]
// 自定义对象排序
class Student {
int score, age;
}
students.sort(Comparator.comparingInt(Student::getScore)
.thenComparingInt(Student::getAge));四、二分查找
4.1 标准二分查找模板
// 查找目标值（存在返回索引，不存在返回 -1）
public int binarySearch(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;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}4.2 二分查找变体模板
找左边界（第一个 >= target 的位置）：
public int lowerBound(int[] nums, int target) {
int left = 0, right = nums.length;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid;
}
}
return left; // 第一个 >= target 的位置
}找右边界（最后一个 <= target 的位置）：
public int upperBound(int[] nums, int target) {
int left = 0, right = nums.length;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] <= target) {
left = mid + 1;
} else {
right = mid;
}
}
return left - 1; // 最后一个 <= target 的位置
}4.3 二分查找三大要点
mid = left + (right - left) / 2：防止(left + right)溢出- 循环条件：
left <= right（标准）或left < right（找边界） - 更新方式：
left = mid + 1或right = mid - 1（标准），left = mid + 1或right = mid（找边界）
避坑： 找边界时
right = mid（不减 1），因为 mid 可能就是答案。标准二分中right = mid - 1因为找到了就 return 了。
五、经典题详解
第 1 题：搜索旋转排序数组（LeetCode 33）
题目： 升序数组在某个点旋转后，搜索目标值。
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;
// 判断哪半部分是有序的
if (nums[left] <= nums[mid]) {
// 左半部分有序
if (nums[left] <= target && target < nums[mid]) {
right = mid - 1; // target 在左半
} else {
left = mid + 1;
}
} else {
// 右半部分有序
if (nums[mid] < target && target <= nums[right]) {
left = mid + 1; // target 在右半
} else {
right = mid - 1;
}
}
}
return -1;
}核心思路： 旋转数组中至少一半是有序的，判断 target 在不在有序的那一半即可。
第 2 题：寻找峰值（LeetCode 162）
题目： 找到任意一个峰值元素（大于左右邻居）。
public int findPeakElement(int[] nums) {
int left = 0, right = nums.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] > nums[mid + 1]) {
right = mid; // 峰值在左侧（含 mid）
} else {
left = mid + 1; // 峰值在右侧
}
}
return left;
}巧妙之处： 比较 mid 和 mid+1，如果 nums[mid] > nums[mid+1]，说明左侧有上坡，一定有峰值。
第 3 题：在排序数组中查找元素的第一个和最后一个位置（LeetCode 34）
public int[] searchRange(int[] nums, int target) {
int first = findFirst(nums, target);
int last = findLast(nums, target);
return new int[]{first, last};
}
private int findFirst(int[] nums, int target) {
int left = 0, right = nums.length - 1;
int result = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
result = mid;
right = mid - 1; // 继续往左找
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return result;
}
private int findLast(int[] nums, int target) {
int left = 0, right = nums.length - 1;
int result = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
result = mid;
left = mid + 1; // 继续往右找
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return result;
}第 4 题：合并区间（LeetCode 56）
题目： 合并所有重叠的区间。
public int[][] merge(int[][] intervals) {
// 按左端点排序
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
List<int[]> merged = new ArrayList<>();
for (int[] interval : intervals) {
if (merged.isEmpty() || merged.get(merged.size() - 1)[1] < interval[0]) {
// 不重叠，直接加入
merged.add(interval);
} else {
// 重叠，合并（取右端点最大值）
merged.get(merged.size() - 1)[1] =
Math.max(merged.get(merged.size() - 1)[1], interval[1]);
}
}
return merged.toArray(new int[0][]);
}第 5 题：颜色分类（LeetCode 75）
题目： 原地排序 0、1、2（荷兰国旗问题）。
public void sortColors(int[] nums) {
// 三指针：p0 指向 0 的右边界，p2 指向 2 的左边界
int p0 = 0, p2 = nums.length - 1;
int i = 0;
while (i <= p2) {
if (nums[i] == 0) {
swap(nums, i, p0);
p0++;
i++;
} else if (nums[i] == 2) {
swap(nums, i, p2);
p2--;
// 注意：i 不递增！因为交换过来的元素还没检查
} else {
i++;
}
}
}关键点： 遇到 2 交换后 i 不递增，因为从 p2 换过来的元素可能是 0、1 或 2，需要重新检查。
第 6 题：前 K 个高频元素（LeetCode 347）
题目： 返回数组中出现频率前 K 高的元素。
public int[] topKFrequent(int[] nums, int k) {
// 1. 统计频率
Map<Integer, Integer> freq = new HashMap<>();
for (int num : nums) {
freq.put(num, freq.getOrDefault(num, 0) + 1);
}
// 2. 桶排序（按频率分组）
List<Integer>[] buckets = new List[nums.length + 1];
for (int key : freq.keySet()) {
int f = freq.get(key);
if (buckets[f] == null) buckets[f] = new ArrayList<>();
buckets[f].add(key);
}
// 3. 从高到低取前 K 个
int[] result = new int[k];
int idx = 0;
for (int i = buckets.length - 1; i >= 0 && idx < k; i--) {
if (buckets[i] != null) {
for (int num : buckets[i]) {
if (idx < k) result[idx++] = num;
}
}
}
return result;
}也可以用优先队列（小顶堆）：
public int[] topKFrequentHeap(int[] nums, int k) {
Map<Integer, Integer> freq = new HashMap<>();
for (int num : nums) {
freq.put(num, freq.getOrDefault(num, 0) + 1);
}
// 小顶堆，堆顶是频率最小的
PriorityQueue<Integer> heap = new PriorityQueue<>(
(a, b) -> freq.get(a) - freq.get(b));
for (int num : freq.keySet()) {
heap.offer(num);
if (heap.size() > k) heap.poll(); // 踢出频率最小的
}
int[] result = new int[k];
for (int i = 0; i < k; i++) {
result[i] = heap.poll();
}
return result;
}第 7 题：寻找两个正序数组的中位数（LeetCode 4）
题目： 两个有序数组找中位数，要求 O(log(m+n))。
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
// 保证 nums1 是较短的数组
if (nums1.length > nums2.length) {
return findMedianSortedArrays(nums2, nums1);
}
int m = nums1.length, n = nums2.length;
int left = 0, right = m;
while (left <= right) {
// 在 nums1 的 i 处切一刀，nums2 的 j 处切一刀
int i = left + (right - left) / 2;
int j = (m + n + 1) / 2 - i;
int nums1LeftMax = (i == 0) ? Integer.MIN_VALUE : nums1[i - 1];
int nums1RightMin = (i == m) ? Integer.MAX_VALUE : nums1[i];
int nums2LeftMax = (j == 0) ? Integer.MIN_VALUE : nums2[j - 1];
int nums2RightMin = (j == n) ? Integer.MAX_VALUE : nums2[j];
if (nums1LeftMax <= nums2RightMin && nums2LeftMax <= nums1RightMin) {
// 找到正确的分割点
if ((m + n) % 2 == 1) {
return Math.max(nums1LeftMax, nums2LeftMax);
} else {
return (Math.max(nums1LeftMax, nums2LeftMax)
+ Math.min(nums1RightMin, nums2RightMin)) / 2.0;
}
} else if (nums1LeftMax > nums2RightMin) {
right = i - 1;
} else {
left = i + 1;
}
}
return 0.0;
}核心思路： 二分查找分割位置，使得左半部分的最大值 ≤ 右半部分的最小值。
第 8 题：x 的平方根（LeetCode 69）
public int mySqrt(int x) {
if (x <= 1) return x;
int left = 1, right = x;
while (left <= right) {
int mid = left + (right - left) / 2;
long square = (long) mid * mid;
if (square == x) return mid;
else if (square < x) left = mid + 1;
else right = mid - 1;
}
return right; // right 是最后一个平方 <= x 的数
}六、排序算法选择指南
数据量小（n < 50）→ 插入排序
通用排序 → 快速排序（或用 Arrays.sort）
需要稳定性 → 归并排序（或 TimSort）
内存受限 → 堆排序
值域小且密集 → 计数排序
需要 TopK → 快速选择 / 堆七、二分查找适用条件
- 数组有序（或具有二段性）
- 可以通过中间值判断目标在哪一边
- 需要 O(log n) 的查找效率
重要： 二分查找不一定要求数组完全有序！只要数据具有「二段性」（可以分成两部分，通过某个条件判断目标在哪部分），就能用二分。例如寻找峰值、旋转数组搜索。
八、面试要点与总结
高频面试题
Q1：快排为什么比归并快？
答：(1) 快排是原地排序，缓存友好；(2) 归并需要额外 O(n) 空间，数据搬运开销大；(3) 实际中快排的常数因子更小。但快排最坏 O(n²)，归并始终 O(n log n)。
Q2：快排最坏情况怎么避免？
答：三种方式：(1) 随机选 pivot；(2) 三数取中（左、中、右的中位数）；(3) 当子数组较小时切换到插入排序。Java 的
Arrays.sort()对基本类型用双轴快排+插入排序。
Q3：堆排序为什么不稳定？
答：堆排序在下沉过程中可能交换不相邻的相等元素。比如两个相等的元素一个在堆顶一个在叶子，下沉操作可能改变它们的相对顺序。
Q4：二分查找为什么用 left + (right - left) / 2 而不是 (left + right) / 2？
答：防止整数溢出。当 left 和 right 都很大时，
left + right可能超过Integer.MAX_VALUE导致溢出，结果为负数。
Q5：什么时候二分查找比哈希表好？
答：(1) 数据有序且需要找边界（第一个>=target）时；(2) 数据量极大时哈希表内存开销大；(3) 需要找「最接近」的值时（哈希表不支持范围查询）。
总结
排序和二分查找是算法基本功，面试中出现频率极高。
排序核心记忆：
- 快排：随机 pivot + 分区 → 最常用
- 归并：分治 + 合并 → 稳定排序
- 堆排：建堆 + 逐个取出 → O(1) 空间
二分查找核心记忆：
- 标准：
left <= right，找到返回 - 找左边界：
left < right，right = mid - 找右边界：
left < right，left = mid + 1 - 防溢出：
mid = left + (right - left) / 2
一句话总结： 排序看快排归并堆排，二分记三个模板（标准、左边界、右边界）。面试遇到有序数组/旋转数组/找峰值/TopK，第一反应想二分。