排序算法
问题
常见的排序算法有哪些？时间复杂度和稳定性怎么分析？
答案
排序算法对比
| 算法 | 平均时间 | 最坏时间 | 空间 | 稳定性 |
|---|---|---|---|---|
| 冒泡排序 | ✅ | |||
| 选择排序 | ❌ | |||
| 插入排序 | ✅ | |||
| 快速排序 | ❌ | |||
| 归并排序 | ✅ | |||
| 堆排序 | ❌ |
稳定性
相等的元素排序后保持原来的相对顺序。数据库排序、多关键字排序需要稳定排序。
快速排序（重点）
快速排序
public 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;
}
快排最坏 出现在数组已有序且选第一个/最后一个做基准的情况。优化：随机选基准或三数取中。
归并排序
归并排序
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);
}
堆排序
堆排序
public void heapSort(int[] arr) {
int n = arr.length;
// 建大顶堆：从最后一个非叶子节点开始下沉
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
// 逐个取出堆顶（最大值）放到末尾
for (int i = n - 1; i > 0; i--) {
swap(arr, 0, i); // 堆顶与末尾交换
heapify(arr, i, 0); // 对剩余元素重新堆化
}
}
private void heapify(int[] arr, int n, int i) {
int largest = i;
int left = 2 * i + 1, right = 2 * i + 2;
if (left < n && arr[left] > arr[largest]) largest = left;
if (right < n && arr[right] > arr[largest]) largest = right;
if (largest != i) {
swap(arr, i, largest);
heapify(arr, n, largest);
}
}
常见面试问题
Q1: Arrays.sort() 底层用什么排序？
答案：
- 基本类型（int[] 等）：双轴快速排序（Dual-Pivot QuickSort）
- 对象类型（Object[]）：TimSort（归并排序的优化变体，稳定排序）
- 小数组（< 47）：插入排序
Q2: 什么时候用什么排序？
答案：
| 场景 | 推荐 |
|---|---|
| 通用排序 | 快排（平均最快） |
| 稳定排序 | 归并排序 |
| 基本有序 | 插入排序（） |
| 内存受限 | 堆排序（ 空间） |
| 大数据排序 | 外部排序（归并） |
| 实际项目 | Arrays.sort() / Collections.sort() |
Q3: 如何找数组中第 K 大的元素？
答案：
用快速选择算法（QuickSelect），基于快排的 partition：
// 平均 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 (left < right) {
int pivot = partition(nums, left, right);
if (pivot == target) return nums[pivot];
else if (pivot < target) left = pivot + 1;
else right = pivot - 1;
}
return nums[left];
}
也可以用最小堆（PriorityQueue），维护 K 个元素，。