高频基础算法 + LeetCode 经典题精讲
| 算法 | 平均时间 | 最坏时间 | 空间复杂度 | 稳定性 |
|---|---|---|---|---|
| 冒泡排序 | O(n²) | O(n²) | O(1) | 稳定 |
| 选择排序 | O(n²) | O(n²) | O(1) | 不稳定 |
| 插入排序 | O(n²) | O(n²) | O(1) | 稳定 |
| 希尔排序 | O(n^1.3~n^2) | 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(n + k) | 稳定 |
| 基数排序 | O(d·(n + k)) | O(d·(n + k)) | O(n + k) | 稳定 |
public void quickSort(int[] arr) {
if (arr == null || arr.length <= 1) return;
quickSort(arr, 0, arr.length - 1);
}
private void quickSort(int[] arr, int left, int right) {
if (left >= right) return;
int pivot = partition(arr, left, right);
quickSort(arr, left, pivot - 1);
quickSort(arr, pivot + 1, right);
}
private int partition(int[] arr, int left, int right) {
int pivot = arr[right]; // 选择右端点作为基准
int i = left; // i 指向小于 pivot 的区域的右边界
for (int j = left; j < right; j++) {
if (arr[j] <= pivot) {
swap(arr, i, j);
i++;
}
}
swap(arr, i, right);
return i;
}
private void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}| 维度 | 快速排序 | 归并排序 |
|---|---|---|
| 平均时间复杂度 | O(n log n) | O(n log n) |
| 最坏时间复杂度 | O(n²) | O(n log n) |
| 空间复杂度 | O(log n)（递归栈） | O(n)（需要临时数组） |
| 稳定性 | 不稳定 | 稳定 |
| 实现难度 | 中 | 中 |
| 缓存友好性 | 好（原地，局部性好） | 一般 |
| 适合数据结构 | 数组 | 数组、链表 |
思想与快速排序类似，每次划分后只递归一边，平均时间复杂度 O(n)。
public int findKthLargest(int[] nums, int k) {
int target = nums.length - k; // 第K大等价于下标为 n-k 的元素
int left = 0, right = nums.length - 1;
while (true) {
int pivot = partition(nums, left, right);
if (pivot == target) {
return nums[pivot];
} else if (pivot < target) {
left = pivot + 1;
} else {
right = pivot - 1;
}
}
}
private int partition(int[] arr, int left, int right) {
int pivot = arr[right];
int i = left;
for (int j = left; j < right; j++) {
if (arr[j] <= pivot) {
swap(arr, i, j);
i++;
}
}
swap(arr, i, right);
return i;
}
private void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}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;
}left < right，但更新边界不正确(left + right) / 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 的下标
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;
}数组被旋转，但仍然可以通过二分判断哪一半是有序的，然后在有序部分内判断 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;
// 左半部分有序
if (nums[left] <= nums[mid]) {
if (nums[left] <= target && target < nums[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
} else { // 右半部分有序
if (nums[mid] < target && target <= nums[right]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
}
return -1;
}
// 时间复杂度：O(log n)
// 空间复杂度：O(1)利用二分查找分别找到 target 的左边界和右边界，次数 = rightIndex - leftIndex + 1。
public int countOccurrences(int[] nums, int target) {
int left = lowerBound(nums, target);
int right = upperBound(nums, target) - 1;
if (left >= nums.length || nums[left] != target) return 0;
return right - left + 1;
}
private 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;
}
private 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;
}两个二分查找，各 O(log n)，总时间复杂度 O(log n)，空间 O(1)。
因为每个元素最多只会落在离它最终位置 k 以内的位置上，只需在窗口内维护一个最小堆即可。
public void sortNearlySorted(int[] nums, int k) {
PriorityQueue minHeap = new PriorityQueue<>();
int index = 0;
for (int num : nums) {
minHeap.offer(num);
if (minHeap.size() > k) {
nums[index++] = minHeap.poll();
}
}
while (!minHeap.isEmpty()) {
nums[index++] = minHeap.poll();
}
}
// 时间复杂度：O(n log k)
// 空间复杂度：O(k) 可以先用 QuickSelect 找到第 K 大的值，然后再一次遍历收集所有 ≥ 该值的元素（或在选择过程中直接维护）。
public int[] topK(int[] nums, int k) {
if (k <= 0 || k > nums.length) return new int[0];
int target = nums.length - k;
int left = 0, right = nums.length - 1;
while (true) {
int pivot = partition(nums, left, right);
if (pivot == target) break;
else if (pivot < target) left = pivot + 1;
else right = pivot - 1;
}
// 此时 [target..end] 都是前K大（未必有序）
return Arrays.copyOfRange(nums, target, nums.length);
}class Node {
int value;
int fileIndex;
}
PriorityQueue minHeap = new PriorityQueue<>((a, b) -> a.value - b.value);
// 初始化：从每个有序子文件读一个元素放入堆中
while (!minHeap.isEmpty()) {
Node node = minHeap.poll();
// 将 node.value 写入输出文件
// 从 node.fileIndex 对应的文件再读一个元素入堆
} 早期 JDK 的 Arrays.sort 使用双轴快速排序（Dual-Pivot QuickSort），对整数数组性能更好。
非比较排序多用于特定场景（大量整数/ID），通用库排序仍以比较排序为主。
class TopKStream {
private PriorityQueue minHeap;
private int k;
public TopKStream(int k) {
this.k = k;
this.minHeap = new PriorityQueue<>();
}
public void add(int val) {
if (minHeap.size() < k) {
minHeap.offer(val);
} else if (val > minHeap.peek()) {
minHeap.poll();
minHeap.offer(val);
}
}
public List getTopK() {
return new ArrayList<>(minHeap); // 可再排序
}
}
// 单次 add: O(log k)
// 空间复杂度：O(k)