| 排序算法 | 时间复杂度 | 空间复杂度 | 稳定性 | 排序策略 | 递归性 | 适应性 |
|---|
| 直接插入排序 | O(n²) | O(1) | 稳定 | 插入类 | 非递归 | 自适应 |
| 二分插入排序 | O(n²) | O(1) | 稳定 | 插入类 | 非递归 | 自适应 |
| 希尔排序 | O(n^1.3)~O(n²) | O(1) | 不稳定 | 插入类 | 非递归 | 部分自适应 |
| 冒泡排序 | O(n²) | O(1) | 稳定 | 交换类 | 非递归 | 自适应 |
| 快速排序 | O(n log n) | O(log n) | 不稳定 | 交换类 | 递归 | 非自适应 |
| 归并排序 | O(n log n) | O(n) | 稳定 | 归并类 | 递归 | 非自适应 |
直插排序
public static void straight_insert_sort(int[] r, int n) {// 直接插入排序：将未排序元素逐个插入到已排序序列的适当位置// 假设数组索引从1开始，r[0]作为哨兵，不参与排序int i, j;// 从第2个元素开始，逐个插入到前面已排序部分for (i = 2; i <= n; i++) {r[0] = r[i]; // 将当前待插入元素暂存到哨兵位置j = i - 1; // 已排序部分的最后一个元素// 从后向前查找插入位置，同时移动元素while (r[0] < r[j]) {r[j + 1] = r[j]; // 元素后移一位j--; // 继续向前比较}// 找到插入位置，将暂存的元素插入r[j + 1] = r[0];}
}
二分插入排序
public static void binary_insert_sort(int[] r) {// 二分插入排序：结合二分查找优化的插入排序// 假设数组索引从1开始，r[0]作为哨兵，不参与排序int i, j, low, high, mid;// 从第2个元素开始，逐个插入到前面已排序部分for (i = 2; i < r.length; i++) {r[0] = r[i]; // 将当前待插入元素暂存到哨兵位置low = 1; // 已排序部分的起始位置high = i - 1; // 已排序部分的结束位置// 二分查找插入位置while (low <= high) {mid = (low + high) / 2; // 计算中间位置if (r[0] < r[mid]) { // 插入位置在左半部分high = mid - 1;} else { // 插入位置在右半部分low = mid + 1;}}// 找到插入位置后，将元素后移for (j = i - 1; j >= high + 1; j--) {r[j + 1] = r[j]; // 元素后移一位}// 在找到的位置插入元素r[high + 1] = r[0];}
}
希尔排序
public static void shell_sort(int[] r) {// 希尔排序：基于插入排序的改进算法// 通过设置不同的间隔(d)，将数组分成多个子序列进行排序// 随着间隔逐渐减小，数组逐渐接近有序，最终间隔为1时完成排序int d, i, j;// 初始间隔为数组长度的一半，然后每次减半for (d = r.length / 2; d >= 1; d = d / 2) {// 对每个子序列进行插入排序for (i = d + 1; i < r.length; i++) {r[0] = r[i]; // 暂存当前元素j = i - d; // 子序列的前一个元素// 在子序列中向前查找插入位置while (j > 0 && r[0] < r[j]) {r[j + d] = r[j]; // 元素后移d个位置j = j - d; // 继续向前查找}// 插入元素r[j + d] = r[0];}}
}
冒泡排序
public static void bubbleSort(int[] r, int n) {int exchange, bound;// exchange: 记录最后一次交换的位置// bound: 每轮比较的右边界exchange = n; // 初始时，整个数组都需要排序while (exchange != 0) { // 只要还有交换发生，就继续排序bound = exchange; // 上一轮最后一次交换的位置，作为本轮的右边界exchange = 0; // 重置交换位置，准备记录本轮的最后一次交换for (int j = 1; j < bound; j++) { // 只需要比较到上一轮最后交换的位置if (r[j] > r[j + 1]) { // 如果前一个元素比后一个大，就交换r[0] = r[j]; // 交换元素r[j] = r[j + 1];r[j + 1] = r[0];exchange = j; // 记录最后一次交换的位置}}// 循环结束后，bound之后的元素已经有序，下一轮只需比较到bound位置}
}
快速排序
public static void quickSort(int[] r, int first, int end) {// 快速排序的递归实现// 参数：// r: 待排序数组// first: 当前子数组的起始索引// end: 当前子数组的结束索引if (first < end) { // 递归终止条件：子数组长度大于1// 分区操作：将数组分为两部分// 左边部分 <= 基准，右边部分 >= 基准// pivot 是基准元素最终所在的位置int pivot = partition(r, first, end);// 递归排序左半部分quickSort(r, first, pivot - 1);// 递归排序右半部分quickSort(r, pivot + 1, end);}// 当 first >= end 时，子数组长度为0或1，已经有序，直接返回
}public static int partition(int[] r, int first, int end) {// 以第一个元素为基准，将数组分为两部分// 左边部分 <= 基准，右边部分 >= 基准// 返回基准元素最终所在的位置int i = first, j = end, temp; // i: 左指针，j: 右指针while (i < j) { // 当左右指针未相遇时，继续分区// 从右向左找第一个小于基准的元素while (i < j && r[i] <= r[j]) j--;if (i < j) { // 如果找到，交换左右指针所指元素temp = r[i];r[i] = r[j];r[j] = temp;i++; // 左指针右移}// 从左向右找第一个大于基准的元素while (i < j && r[i] <= r[j]) i++;if (i < j) { // 如果找到，交换左右指针所指元素temp = r[i];r[i] = r[j];r[j] = temp;j--; // 右指针左移}}// 当i=j时，分区完成，返回基准元素的位置return i;
}
归并排序
public static void mergesort(int[] r, int s, int t) {// 参数：// r: 待排序数组// s: 当前子数组的起始索引// t: 当前子数组的结束索引int i, m;// 递归终止条件：当子数组只有一个元素时，直接返回if (s == t) return;// 计算中间位置，将数组分成两部分m = (s + t) / 2;// 递归排序左半部分mergesort(r, s, m);// 递归排序右半部分mergesort(r, m + 1, t);// 合并已排序的两部分merge(r, s, m, t);
}public static void merge(int[] r, int s, int m, int t) {// 参数：// r: 待合并数组// s: 左子数组的起始索引// m: 左子数组的结束索引（也是中间位置）// t: 右子数组的结束索引// 创建辅助数组，用于临时存储合并结果int[] r1 = new int[t + 1];// i: 左子数组的当前索引// j: 右子数组的当前索引// k: 辅助数组的当前索引int i = s, j = m + 1, k = s;// 同时遍历左右子数组，将较小的元素放入辅助数组while (i <= m && j <= t) {if (r[i] <= r[j]) {r1[k++] = r[i++]; // 左子数组元素较小，放入辅助数组} else {r1[k++] = r[j++]; // 右子数组元素较小，放入辅助数组}}// 处理左子数组剩余元素while (i <= m) {r1[k++] = r[i++];}// 处理右子数组剩余元素while (j <= t) {r1[k++] = r[j++];}// 将辅助数组中的元素复制回原数组for (i = s; i <= t; i++) {r[i] = r1[i];}
}
