SYSTEM
排序
src/content/notes/system/排序.md 1.4 排序
快排(partition + 代码)
选基准、把小于基准的放左、大于放右,再对左右子区间递归。
class Solution {
public void quickSort(int[] nums, int l, int r) {
if (l >= r) return;
int p = partition(nums, l, r);
quickSort(nums, l, p - 1);
quickSort(nums, p + 1, r);
}
private int partition(int[] nums, int l, int r) {
int pivot = nums[l];
while (l < r) {
while (l < r && nums[r] >= pivot) r--;
nums[l] = nums[r];
while (l < r && nums[l] <= pivot) l++;
nums[r] = nums[l];
}
nums[l] = pivot;
return l;
}
}
归并排序(分治 + 代码)
分到单元素再两两合并,合并时借助临时数组。
class Solution {
public void mergeSort(int[] nums, int l, int r) {
if (l >= r) return;
int mid = l + (r - l) / 2;
mergeSort(nums, l, mid);
mergeSort(nums, mid + 1, r);
merge(nums, l, mid, r);
}
private void merge(int[] nums, int l, int mid, int r) {
int[] tmp = new int[r - l + 1];
int i = l, j = mid + 1, k = 0;
while (i <= mid && j <= r) {
tmp[k++] = nums[i] <= nums[j] ? nums[i++] : nums[j++];
}
while (i <= mid) tmp[k++] = nums[i++];
while (j <= r) tmp[k++] = nums[j++];
System.arraycopy(tmp, 0, nums, l, tmp.length);
}
}
堆排(大顶堆 + 代码)
先建大顶堆,再把堆顶与末尾交换、缩小堆、下沉调整。
class Solution {
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--) {
int t = nums[0]; nums[0] = nums[i]; nums[i] = t; // 堆顶放末尾
heapify(nums, i, 0); // 缩小堆并调整
}
}
private void heapify(int[] nums, int n, int i) {
int largest = i, l = 2 * i + 1, r = 2 * i + 2;
if (l < n && nums[l] > nums[largest]) largest = l;
if (r < n && nums[r] > nums[largest]) largest = r;
if (largest != i) {
int t = nums[i]; nums[i] = nums[largest]; nums[largest] = t;
heapify(nums, n, largest);
}
}
}
复杂度与稳定性对比
| 排序 | 平均时间 | 最坏时间 | 空间 | 稳定性 |
|---|---|---|---|---|
| 快排 | O(NlogN) | O(N²) | O(logN) | 不稳定 |
| 归并 | O(NlogN) | O(NlogN) | O(N) | 稳定 |
| 堆排 | O(NlogN) | O(NlogN) | O(1) | 不稳定 |
面试题:“快排为什么比归并快?”
虽然都是 O(NlogN),但快排在工程上更快:一是常数小,partition 是原地交换、不需要额外数组;二是缓存友好,顺序访问比归并的跳跃合并更利于 CPU 缓存命中;三是空间省,归并需 O(N) 辅助数组。代价是快排最坏会退化到 O(N²),可通过随机化基准或三数取中规避。