做yy头像的网站,阿里wordpress 安装,一个网站可以做多少地区词,大连零基础网站建设教学培训七大排序算法完整对比#xff08;含时间/空间/稳定性#xff09; #x1f4ca; 七大排序算法性能对比表 xychart-betatitle 七大排序算法性能对比x-axis [插入排序, 希尔排序, 选择排序, 堆排序, 冒泡排序, 快速排序, 归并排序]y-axis 时间复杂度…七大排序算法完整对比含时间/空间/稳定性 七大排序算法性能对比表xychart-beta title 七大排序算法性能对比 x-axis [插入排序, 希尔排序, 选择排序, 堆排序, 冒泡排序, 快速排序, 归并排序] y-axis 时间复杂度 0 -- 7 y-axis 空间复杂度 0 -- 7 y-axis 稳定性 0 -- 2 bar [6, 4, 6, 2, 6, 2, 2] line [1, 1, 1, 1, 1, 3, 5] line [1, 0, 0, 0, 1, 0, 1]quadrantChart title 排序算法适用场景四象限图 x-axis 时间复杂度差 -- 时间复杂度好 y-axis 空间复杂度高 -- 空间复杂度低 quadrant-1 小数据量/稳定 quadrant-2 大数据量/稳定 quadrant-3 一般不使用 quadrant-4 大数据量/不稳定 插入排序: [0.2, 0.8] 冒泡排序: [0.2, 0.7] 选择排序: [0.2, 0.6] 希尔排序: [0.6, 0.8] 堆排序: [0.8, 0.9] 快速排序: [0.9, 0.7] 归并排序: [0.8, 0.3]1. 直接插入排序/** * 直接插入排序 * 时间复杂度O(n²) 最好O(n) 最坏O(n²) 平均O(n²) * 空间复杂度O(1) 原地排序 * 稳定性稳定 * 适用场景小数据量、基本有序的数据 */ public class InsertionSort { public static void insertionSort(int[] arr) { if (arr null || arr.length 1) { return; } for (int i 1; i arr.length; i) { int key arr[i]; // 当前要插入的元素 int j i - 1; // 从后往前找到插入位置 while (j 0 arr[j] key) { arr[j 1] arr[j]; // 元素后移 j--; } arr[j 1] key; // 插入到正确位置 } } public static void main(String[] args) { int[] arr {64, 34, 25, 12, 22, 11, 90}; System.out.println( 直接插入排序 ); System.out.println(时间复杂度: O(n²) 最好O(n) 最坏O(n²)); System.out.println(空间复杂度: O(1)); System.out.println(稳定性: 稳定); System.out.println(原始数组: java.util.Arrays.toString(arr)); insertionSort(arr); System.out.println(排序后: java.util.Arrays.toString(arr)); // 稳定性测试 testStability(); } public static void testStability() { System.out.println(\n 稳定性测试 ); int[] arr {3, 1, 2, 1, 4}; // 有两个1 System.out.println(原始数组: java.util.Arrays.toString(arr)); insertionSort(arr); System.out.println(排序后: java.util.Arrays.toString(arr)); System.out.println(两个1的相对位置保持不变 → 稳定排序); } }2. 希尔排序/** * 希尔排序 * 时间复杂度O(n^1.3) ~ O(n^2) 取决于增量序列 * 空间复杂度O(1) 原地排序 * 稳定性不稳定 * 适用场景中等数据量是插入排序的优化 */ public class ShellSort { public static void shellSort(int[] arr) { int n arr.length; // 增量序列gap n/2, n/4, ..., 1 for (int gap n / 2; gap 0; gap / 2) { // 对每个分组进行插入排序 for (int i gap; i n; i) { int temp arr[i]; int j i; // 对当前分组进行插入排序 while (j gap arr[j - gap] temp) { arr[j] arr[j - gap]; j - gap; } arr[j] temp; } } } public static void main(String[] args) { int[] arr {64, 34, 25, 12, 22, 11, 90, 8, 7, 6, 5, 4, 3, 2, 1}; System.out.println( 希尔排序 ); System.out.println(时间复杂度: O(n^1.3) ~ O(n^2)); System.out.println(空间复杂度: O(1)); System.out.println(稳定性: 不稳定); System.out.println(原始数组: java.util.Arrays.toString(arr)); shellSort(arr); System.out.println(排序后: java.util.Arrays.toString(arr)); // 不稳定性测试 testInstability(); } public static void testInstability() { System.out.println(\n 不稳定性测试 ); int[] arr {5, 8, 5, 2, 9}; // 有两个5 System.out.println(原始数组: java.util.Arrays.toString(arr)); System.out.println(第一个5在索引0第二个5在索引2); shellSort(arr); System.out.println(排序后: java.util.Arrays.toString(arr)); System.out.println(两个5的相对位置可能改变 → 不稳定排序); } }3. 直接选择排序/** * 直接选择排序 * 时间复杂度O(n²) 最好O(n²) 最坏O(n²) 平均O(n²) * 空间复杂度O(1) 原地排序 * 稳定性不稳定 * 适用场景小数据量简单实现 */ public class SelectionSort { public static void selectionSort(int[] arr) { int n arr.length; for (int i 0; i n - 1; i) { // 找到未排序部分的最小元素索引 int minIndex i; for (int j i 1; j n; j) { if (arr[j] arr[minIndex]) { minIndex j; } } // 将最小元素交换到已排序部分的末尾 if (minIndex ! i) { swap(arr, i, minIndex); } } } private static void swap(int[] arr, int i, int j) { int temp arr[i]; arr[i] arr[j]; arr[j] temp; } public static void main(String[] args) { int[] arr {64, 25, 12, 22, 11}; System.out.println( 直接选择排序 ); System.out.println(时间复杂度: O(n²)); System.out.println(空间复杂度: O(1)); System.out.println(稳定性: 不稳定); System.out.println(原始数组: java.util.Arrays.toString(arr)); selectionSort(arr); System.out.println(排序后: java.util.Arrays.toString(arr)); // 演示不稳定性 demonstrateInstability(); } public static void demonstrateInstability() { System.out.println(\n 不稳定性演示 ); Student[] students { new Student(张三, 85, 1), new Student(李四, 92, 2), new Student(王五, 85, 3) // 与张三分数相同 }; System.out.println(原始顺序:); for (Student s : students) { System.out.println( s); } // 模拟选择排序过程 for (int i 0; i students.length - 1; i) { int minIndex i; for (int j i 1; j students.length; j) { if (students[j].score students[minIndex].score) { minIndex j; } } if (minIndex ! i) { Student temp students[i]; students[i] students[minIndex]; students[minIndex] temp; } } System.out.println(排序后:); for (Student s : students) { System.out.println( s); } System.out.println(两个85分的学生相对位置改变 → 不稳定); } static class Student { String name; int score; int id; Student(String name, int score, int id) { this.name name; this.score score; this.id id; } Override public String toString() { return name ( score , id: id ); } } }4. 堆排序/** * 堆排序 * 时间复杂度O(nlogn) 最好O(nlogn) 最坏O(nlogn) 平均O(nlogn) * 空间复杂度O(1) 原地排序 * 稳定性不稳定 * 适用场景大数据量需要保证最坏情况O(nlogn) */ public class HeapSort { public static void heapSort(int[] arr) { int n arr.length; // 1. 建堆从最后一个非叶子节点开始 for (int i n / 2 - 1; i 0; i--) { heapify(arr, n, i); } // 2. 一个个从堆顶取出元素 for (int i n - 1; i 0; i--) { // 将当前最大元素堆顶与末尾元素交换 swap(arr, 0, i); // 调整剩下的堆 heapify(arr, i, 0); } } // 调整堆大根堆 private static void heapify(int[] arr, int n, int i) { int largest i; // 初始化最大元素为根节点 int left 2 * i 1; // 左孩子 int 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); } } private static void swap(int[] arr, int i, int j) { int temp arr[i]; arr[i] arr[j]; arr[j] temp; } public static void main(String[] args) { int[] arr {4, 10, 3, 5, 1}; System.out.println( 堆排序 ); System.out.println(时间复杂度: O(nlogn)); System.out.println(空间复杂度: O(1)); System.out.println(稳定性: 不稳定); System.out.println(原始数组: java.util.Arrays.toString(arr)); heapSort(arr); System.out.println(排序后: java.util.Arrays.toString(arr)); // 演示不稳定性 demonstrateInstability(); } public static void demonstrateInstability() { System.out.println(\n 不稳定性演示 ); int[] arr {3, 3, 2, 1}; // 有两个3 System.out.println(原始数组: java.util.Arrays.toString(arr)); System.out.println(第一个3在索引0第二个3在索引1); heapSort(arr); System.out.println(排序后: java.util.Arrays.toString(arr)); System.out.println(建堆和调整过程可能改变相同元素的相对位置 → 不稳定); } }5. 冒泡排序/** * 冒泡排序 * 时间复杂度O(n²) 最好O(n) 最坏O(n²) 平均O(n²) * 空间复杂度O(1) 原地排序 * 稳定性稳定 * 适用场景教学演示小数据量 */ public class BubbleSort { public static void bubbleSort(int[] arr) { int n arr.length; for (int i 0; i n - 1; i) { for (int j 0; j n - 1 - i; j) { if (arr[j] arr[j 1]) { swap(arr, j, j 1); } } } } // 优化版本添加标志位 public static void bubbleSortOptimized(int[] arr) { int n arr.length; for (int i 0; i n - 1; i) { boolean swapped false; for (int j 0; j n - 1 - i; j) { if (arr[j] arr[j 1]) { swap(arr, j, j 1); swapped true; } } // 如果这一轮没有交换说明已经有序 if (!swapped) { break; } } } private static void swap(int[] arr, int i, int j) { int temp arr[i]; arr[i] arr[j]; arr[j] temp; } public static void main(String[] args) { int[] arr {64, 34, 25, 12, 22, 11, 90}; System.out.println( 冒泡排序 ); System.out.println(时间复杂度: O(n²) 最好O(n) 最坏O(n²)); System.out.println(空间复杂度: O(1)); System.out.println(稳定性: 稳定); System.out.println(原始数组: java.util.Arrays.toString(arr)); bubbleSortOptimized(arr); System.out.println(排序后: java.util.Arrays.toString(arr)); // 稳定性测试 testStability(); } public static void testStability() { System.out.println(\n 稳定性测试 ); int[] arr {5, 2, 8, 2, 3}; // 有两个2 System.out.println(原始数组: java.util.Arrays.toString(arr)); System.out.println(第一个2在索引1第二个2在索引3); bubbleSortOptimized(arr); System.out.println(排序后: java.util.Arrays.toString(arr)); System.out.println(两个2的相对位置保持不变 → 稳定排序); // 详细演示稳定原因 System.out.println(\n稳定性原理); System.out.println(冒泡排序只在前一个元素 后一个元素时才交换); System.out.println(对于相等的元素 (arr[j] arr[j1]) 不会交换); System.out.println(因此相等元素的相对位置不会改变); } }6. 快速排序/** * 快速排序 * 时间复杂度O(nlogn) 最好O(nlogn) 最坏O(n²) 平均O(nlogn) * 空间复杂度O(logn) 递归栈空间 * 稳定性不稳定 * 适用场景大数据量通用场景平均性能最好 */ public class QuickSort { // 前后指针法 public static void quickSort(int[] arr, int low, int high) { if (low high) { int pi partition(arr, low, high); quickSort(arr, low, pi - 1); quickSort(arr, pi 1, high); } } private static int partition(int[] arr, int low, int high) { int pivot arr[high]; int i low - 1; for (int j low; j high; j) { if (arr[j] pivot) { i; swap(arr, i, j); } } swap(arr, i 1, high); return i 1; } // 三数取中优化 public static void quickSortOptimized(int[] arr, int low, int high) { if (low high) { // 三数取中选择基准 int mid low (high - low) / 2; medianOfThree(arr, low, mid, high); int pi partition(arr, low, high); quickSortOptimized(arr, low, pi - 1); quickSortOptimized(arr, pi 1, high); } } private static void medianOfThree(int[] arr, int a, int b, int c) { if (arr[a] arr[b]) swap(arr, a, b); if (arr[a] arr[c]) swap(arr, a, c); if (arr[b] arr[c]) swap(arr, b, c); // 将中位数放到high位置 swap(arr, b, c); } private static void swap(int[] arr, int i, int j) { int temp arr[i]; arr[i] arr[j]; arr[j] temp; } public static void main(String[] args) { int[] arr {10, 7, 8, 9, 1, 5}; System.out.println( 快速排序 ); System.out.println(时间复杂度: O(nlogn) 最好O(nlogn) 最坏O(n²)); System.out.println(空间复杂度: O(logn) 递归栈空间); System.out.println(稳定性: 不稳定); System.out.println(原始数组: java.util.Arrays.toString(arr)); quickSortOptimized(arr, 0, arr.length - 1); System.out.println(排序后: java.util.Arrays.toString(arr)); // 演示不稳定性 demonstrateInstability(); // 空间复杂度演示 demonstrateSpaceComplexity(); } public static void demonstrateInstability() { System.out.println(\n 不稳定性演示 ); int[] arr {3, 3, 1, 2}; // 有两个3 System.out.println(原始数组: java.util.Arrays.toString(arr)); System.out.println(第一个3在索引0第二个3在索引1); quickSort(arr, 0, arr.length - 1); System.out.println(排序后: java.util.Arrays.toString(arr)); System.out.println(分区过程中相同元素的相对位置可能改变 → 不稳定); } public static void demonstrateSpaceComplexity() { System.out.println(\n 空间复杂度分析 ); System.out.println(递归调用栈深度: O(logn)); System.out.println(最好情况平衡划分: 递归深度 log₂n); System.out.println(最坏情况已排序: 递归深度 n); System.out.println(平均情况: 递归深度 ≈ log₂n); int n 1000000; double avgDepth Math.log(n) / Math.log(2); System.out.printf(\n数据量 n%,d 时:\n, n); System.out.printf(平均递归深度: %.0f\n, avgDepth); System.out.printf(平均空间占用: %.0f * 8字节 ≈ %.0f字节\n, avgDepth, avgDepth * 8); } }7. 归并排序/** * 归并排序 * 时间复杂度O(nlogn) 最好O(nlogn) 最坏O(nlogn) 平均O(nlogn) * 空间复杂度O(n) 需要额外数组 * 稳定性稳定 * 适用场景大数据量需要稳定性外部排序 */ public class MergeSort { // 递归实现 public static void mergeSort(int[] arr) { if (arr null || arr.length 1) { return; } int[] temp new int[arr.length]; mergeSort(arr, 0, arr.length - 1, temp); } private static void mergeSort(int[] arr, int left, int right, int[] temp) { if (left right) { int mid left (right - left) / 2; // 分治 mergeSort(arr, left, mid, temp); mergeSort(arr, mid 1, right, temp); // 合并 merge(arr, left, mid, right, temp); } } // 合并两个有序数组 private static void merge(int[] arr, int left, int mid, int right, int[] temp) { int i left; // 左数组起始索引 int j mid 1; // 右数组起始索引 int k 0; // 临时数组索引 // 合并两个有序数组 while (i mid j right) { if (arr[i] arr[j]) { // 注意使用 保持稳定性 temp[k] arr[i]; } else { temp[k] arr[j]; } } // 复制左边剩余元素 while (i mid) { temp[k] arr[i]; } // 复制右边剩余元素 while (j right) { temp[k] arr[j]; } // 复制回原数组 System.arraycopy(temp, 0, arr, left, k); } // 迭代实现 public static void mergeSortIterative(int[] arr) { int n arr.length; int[] temp new int[n]; // 子数组大小从1开始每次翻倍 for (int size 1; size n; size * 2) { for (int left 0; left n; left 2 * size) { int mid Math.min(left size - 1, n - 1); int right Math.min(left 2 * size - 1, n - 1); // 合并 int i left, j mid 1, k 0; int[] mergeTemp new int[right - left 1]; while (i mid j right) { if (arr[i] arr[j]) { mergeTemp[k] arr[i]; } else { mergeTemp[k] arr[j]; } } while (i mid) mergeTemp[k] arr[i]; while (j right) mergeTemp[k] arr[j]; System.arraycopy(mergeTemp, 0, arr, left, mergeTemp.length); } } } public static void main(String[] args) { int[] arr {12, 11, 13, 5, 6, 7}; System.out.println( 归并排序 ); System.out.println(时间复杂度: O(nlogn)); System.out.println(空间复杂度: O(n) 需要额外数组); System.out.println(稳定性: 稳定); System.out.println(原始数组: java.util.Arrays.toString(arr)); mergeSort(arr); System.out.println(排序后: java.util.Arrays.toString(arr)); // 稳定性测试 testStability(); // 空间复杂度分析 analyzeSpaceComplexity(); } public static void testStability() { System.out.println(\n 稳定性测试 ); int[] arr {5, 2, 8, 2, 3}; // 有两个2 System.out.println(原始数组: java.util.Arrays.toString(arr)); System.out.println(第一个2在索引1第二个2在索引3); mergeSort(arr); System.out.println(排序后: java.util.Arrays.toString(arr)); System.out.println(两个2的相对位置保持不变 → 稳定排序); System.out.println(\n稳定性原理); System.out.println(合并时使用 arr[i] arr[j]相等时优先取左边的); System.out.println(这样可以保持相等元素的原始相对顺序); } public static void analyzeSpaceComplexity() { System.out.println(\n 空间复杂度分析 ); System.out.println(需要额外数组存储中间结果: O(n)); System.out.println(递归栈深度: O(logn)); System.out.println(总空间复杂度: O(n logn) O(n)); int n 1000000; long arrayMemory n * 4L; // 4字节每个int long stackMemory (long)(Math.log(n) / Math.log(2)) * 8L; // 8字节每个栈帧 System.out.printf(\n数据量 n%,d 时:\n, n); System.out.printf(额外数组占用: %,d 字节\n, arrayMemory); System.out.printf(递归栈占用: ~%,d 字节\n, stackMemory); System.out.printf(总额外空间: ~%,d 字节\n, arrayMemory stackMemory); } } 完整对比表格public class SortingComparison { public static void main(String[] args) { System.out.println( 七大排序算法完整对比 ); System.out.println(); System.out.println(算法名称 | 最好时间复杂度 | 平均时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 稳定性 | 适用场景); System.out.println(); System.out.println(直接插入排序 | O(n) | O(n²) | O(n²) | O(1) | 稳定 | 小数据/基本有序); System.out.println(希尔排序 | O(n^1.3) | 依赖增量序列 | O(n²) | O(1) | 不稳定 | 中等数据量); System.out.println(直接选择排序 | O(n²) | O(n²) | O(n²) | O(1) | 不稳定 | 教学演示); System.out.println(堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | 不稳定 | 大数据/需要最坏O(nlogn)); System.out.println(冒泡排序 | O(n) | O(n²) | O(n²) | O(1) | 稳定 | 教学演示/小数据); System.out.println(快速排序 | O(nlogn) | O(nlogn) | O(n²) | O(logn) | 不稳定 | 通用场景/平均性能最好); System.out.println(归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | 稳定 | 大数据/需要稳定/外部排序); System.out.println(); // 性能测试 performanceTest(); } public static void performanceTest() { System.out.println(\n 性能测试数据量10,000); int size 10000; int[] randomArr generateRandom