[数据结构与算法] 排序算法
最编程
2024-10-08 07:02:46
...
3.7 排序算法
概述
比较排序算法
| 算法 | 最好 | 最坏 | 平均 | 空间 | 稳定 | 思想 | 注意事项 |
|---|---|---|---|---|---|---|---|
| 冒泡 | O(n) | O( n 2 n^2 n2) | O( n 2 n^2 n2) | O(1) | Y | 比较 | 最好情况需要额外判断 |
| 选择 | O( n 2 n^2 n2) | O( n 2 n^2 n2) | O( n 2 n^2 n2) | O(1) | N | 比较 | 交换次数一般少于冒泡 |
| 堆 | O( n l o g n nlogn nlogn) | O( n l o g n nlogn nlogn) | O( n l o g n nlogn nlogn) | O(1) | N | 选择 | 堆排序的辅助性较强，理解前先理解堆的数据结构 |
| 插入 | O(n) | O( n 2 n^2 n2) | O( n 2 n^2 n2) | O(1) | Y | 比较 | 插入排序对于近乎有序的数据处理速度比较快，复杂度有所下降，可以提前结束 |
| 希尔 | O(nlogn) | O( n 2 n^2 n2) | O( n l o g n nlogn nlogn) | O(1) | N | 插入 | gap序列的构造有多种方式，不同方式处理的数据复杂度可能不同 |
| 归并 | O( n l o g n nlogn nlogn) | O( n l o g n nlogn nlogn) | O( n l o g n nlogn nlogn) | O(n) | Y | 分治 | 需要额外的O(n)的存储空间 |
| 快速 | O( n l o g n nlogn nlogn) | O( n 2 n^2 n2) | O( n l o g n nlogn nlogn) | O(logn) | N | 分治 | 快排可能存在最坏情况，需要把枢轴值选取得尽量随机化来缓解最坏情况下的时间复杂度 |
非比较排序算法
| 非比较排序算法 | 时间复杂度 | 空间复杂度 | 稳定性 |
|---|---|---|---|
| 计数排序 | O(n+k) | O(n+k) | 稳定 |
| 桶排序 | O(n+k) | O(n+k) | 稳定 |
| 基数排序 | O(d*(n+k)) | O(n+k) | 稳定 |
其中
- n 是数组长度
- k 是桶长度
- d 是基数位数
稳定 vs 不稳定
Java 中的排序
Arrays.sort
JDK 7~13 中的排序实现
| 排序目标 | 条件 | 采用算法 |
|---|---|---|
| int[] long[] float[] double[] | size < 47 | 混合插入排序 (pair) |
| size < 286 | 双基准点快排 | |
| 有序度低 | 双基准点快排 | |
| 有序度高 | 归并排序 | |
| byte[] | size <= 29 | 插入排序 |
| size > 29 | 计数排序 | |
| char[] short[] | size < 47 | 插入排序 |
| size < 286 | 双基准点快排 | |
| 有序度低 | 双基准点快排 | |
| 有序度高 | 归并排序 | |
| size > 3200 | 计数排序 | |
| Object[] | -Djava.util.Arrays.useLegacyMergeSort=true | 传统归并排序 |
| TimSort |
JDK 14~20 中的排序实现
| 排序目标 | 条件 | 采用算法 |
|---|---|---|
| int[] long[] float[] double[] | size < 44 并位于最左侧 | 插入排序 |
| size < 65 并不是最左侧 | 混合插入排序 (pin) | |
| 有序度低 | 双基准点快排 | |
| 递归次数超过 384 | 堆排序 | |
| 对于整个数组或非最左侧 size > 4096，有序度高 | 归并排序 | |
| byte[] | size <= 64 | 插入排序 |
| size > 64 | 计数排序 | |
| char[] short[] | size < 44 | 插入排序 |
| 再大 | 双基准点快排 | |
| 递归次数超过 384 | 计数排序 | |
| size > 1750 | 计数排序 | |
| Object[] | -Djava.util.Arrays.useLegacyMergeSort=true | 传统归并排序 |
| TimSort |
- 其中 TimSort 是用归并+二分插入排序的混合排序算法
- 值得注意的是从 JDK 8 开始支持 Arrays.parallelSort 并行排序
- 根据最新的提交记录来看 JDK 21 可能会引入基数排序等优化
外部排序
1) 冒泡排序
要点
- 每轮冒泡不断地比较相邻的两个元素，如果它们是逆序的，则交换它们的位置
- 下一轮冒泡，可以调整未排序的右边界，减少不必要比较
以数组 3、2、1 的冒泡排序为例，第一轮冒泡
第二轮冒泡
未排序区域内就剩一个元素，结束
优化手段：每次循环时，若能确定更合适的右边界，则可以减少冒泡轮数
以数组 3、2、1、4、5 为例，第一轮结束后记录的 x，即为右边界
非递归版代码
public class BubbleSort {
private static void bubble(int[] a) {
int j = a.length - 1;
while (true) {
int x = 0;
for (int i = 0; i < j; i++) {
if (a[i] > a[i + 1]) {
int t = a[i];
a[i] = a[i + 1];
a[i + 1] = t;
x = i;
}
}
j = x;
if (j == 0) {
break;
}
}
}
public static void main(String[] args) {
int[] a = {6, 5, 4, 3, 2, 1};
System.out.println(Arrays.toString(a));
bubble(a);
System.out.println(Arrays.toString(a));
}
}
2) 选择排序
要点
- 每一轮选择，找出最大（最小）的元素，并把它交换到合适的位置
以下面的数组选择最大值为例
非递归实现
public class SelectionSort {
public static void sort(int[] a) {
// 1. 选择轮数 a.length - 1
// 2. 交换的索引位置(right) 初始 a.length - 1, 每次递减
for (int right = a.length - 1; right > 0 ; right--) {
int max = right;
for (int i = 0; i < right; i++) {
if (a[i] > a[max]) {
max = i;
}
}
if(max != right) {
swap(a, max, right);
}
}
}
private static void swap(int[] a, int i, int j) {
int t = a[i];
a[i] = a[j];
a[j] = t;
}
public static void main(String[] args) {
int[] a = {6, 5, 4, 3, 2, 1};
System.out.println(Arrays.toString(a));
sort(a);
System.out.println(Arrays.toString(a));
}
}
3) 堆排序
要点：
- 建立大顶堆
- 每次将堆顶元素（最大值）交换到末尾，调整堆顶元素，让它重新符合大顶堆特性
建堆
交换，下潜调整
代码
public class HeapSort {
public static void sort(int[] a) {
heapify(a, a.length);
for (int right = a.length - 1; right > 0; right--) {
swap(a, 0, right);
down(a, 0, right);
}
}
// 建堆 O(n)
private static void heapify(int[] array, int size) {
for (int i = size / 2 - 1; i >= 0; i--) {
down(array, i, size);
}
}
// 下潜
// leetcode 上数组排序题目用堆排序求解，非递归实现比递归实现大约快 6ms
private static void down(int[] array, int parent, int size) {
while (true) {
int left = parent * 2 + 1;
int right = left + 1;
int max = parent;
if (left < size && array[left] > array[max]) {
max = left;
}
if (right < size && array[right] > array[max]) {
max = right;
}
if (max == parent) { // 没找到更大的孩子
break;
}
swap(array, max, parent);
parent = max;
}
}
// 交换
private static void swap(int[] a, int i, int j) {
int t = a[i];
a[i] = a[j];
a[j] = t;
}
public static void main(String[] args) {
int[] a = {2, 3, 1, 7, 6, 4, 5};
System.out.println(Arrays.toString(a));
sort(a);
System.out.println(Arrays.toString(a));
}
}
4) 插入排序
要点
-
将数组分为两部分 [0 … low-1] [low … a.length-1]
- 左边 [0 … low-1] 是已排序部分
- 右边 [low … a.length-1] 是未排序部分
- 每次从未排序区域取出 low 位置的元素, 插入到已排序区域
例
代码
public class InsertionSort {
public static void sort(int[] a) {
for (int low = 1; low < a.length; low++) {
// 将 low 位置的元素插入至 [0..low-1] 的已排序区域
int t = a[low];
int i = low - 1; // 已排序区域指针
while (i >= 0 && t < a[i]) { // 没有找到插入位置
a[i + 1] = a[i]; // 空出插入位置
i--;
}
// 找到插入位置
if (i != low - 1) {
a[i + 1] = t;
}
}
}
public static void main(String[] args) {
int[] a = {9, 3, 7, 2, 5, 8, 1, 4};
System.out.println(Arrays.toString(a));
sort(a);
System.out.println(Arrays.toString(a));
}
}
5) 希尔排序
要点
- 简单的说，就是分组实现插入，每组元素间隙称为 gap
- 每轮排序后 gap 逐渐变小，直至 gap 为 1 完成排序
- 对插入排序的优化，让元素更快速地交换到最终位置
下图演示了 gap = 4，gap = 2，gap = 1 的三轮排序前后比较
代码
public class ShellSort {
public static void sort(int[] a) {
for (int gap = a.length>>1; gap >0 ; gap=gap>>1) {
for (int low = gap; low < a.length; low ++) {
// 将 low 位置的元素插入至 [0..low-1] 的已排序区域
int t = a[low];
int i = low - gap; // 已排序区域指针
while (i >= 0 && t < a[i]) { // 没有找到插入位置
a[i + gap] = a[i]; // 空出插入位置
i -= gap;
}
// 找到插入位置
if (i != low - gap) {
a[i + gap] = t;
}
}
}
}
public static void main(String[] args) {
int[] a = {9, 3, 7, 2, 5, 8, 1, 4};
System.out.println(Arrays.toString(a));
sort(a);
System.out.println(Arrays.toString(a));
}
}
6) 归并排序
递归实现
要点
- 分 - 每次从中间切一刀，处理的数据少一半
- 治 - 当数据仅剩一个时可以认为有序
- 合 - 两个有序的结果，可以进行合并排序（参见数组练习 E01. 合并有序数组）
代码
public class MergeSortTopDown {
/*
a1 原始数组
i~iEnd 第一个有序范围
j~jEnd 第二个有序范围
a2 临时数组
*/
public static void merge(int[] a1, int i, int iEnd, int j, int jEnd, int[] a2) {
int k = i;
while (i <= iEnd && j <= jEnd) {
if (a1[i] < a1[j]) {
a2[k] = a1[i];
i++;
}