java常见排序算法

文章目录一、冒泡排序算法描述代码复杂度二、选择排序算法描述代码复杂度三、插入排序算法描述代码复杂度分析四、希尔排序算法步骤代码复杂度分析五、归并排序算法描述代码复杂度分析六、快速排序算法描述代码复杂度分析七、堆排序八、计数排序——非比较排序算法描述代码复杂度分析九、基数排序——非比较排序十、桶排序——非比较排序零、总览 / 前言复杂度和稳定性表格一览排序算法平均时间最好时间最坏时间空间稳定性冒泡排序O(n²)O(n)O(n²)O(1)稳定选择排序O(n²)O(n²)O(n²)O(1)不稳定插入排序O(n²)O(n)O(n²)O(1)稳定希尔排序---O(1)不稳定归并排序O(n log n)O(n log n)O(n log n)O(n)稳定快速排序O(n log n)O(n log n)O(n²)O(log n)不稳定堆排序O(n log n)O(n log n)O(n log n)O(1)不稳定计数排序O(n k)O(n k)O(n k)O(n k)稳定基数排序----稳定桶排序O(n)O(n)-O(1)稳定稳定性解释对于存在相等元素的序列排序后原相等元素在排序结果中的相对位置相比原输入序列不变。例如输入序列nums {3, 1, 2₁, 2₂}数字 2 出现两次下标表示出现次序。不稳定排序结果{1, 2₂, 2₁, 3}改变了 2 的相对位置。稳定排序结果{1, 2₁, 2₂, 3}保持原相对位置。如果排序对象仅为数值稳定性无区别但对引用类型排序时若需保持相同字段元素的相对位置需使用稳定排序。不稳定排序算法堆排序、快速排序、希尔排序、直接选择排序。稳定排序算法基数排序、冒泡排序、插入排序、归并排序。一、冒泡排序算法描述对于要排序的数组从第一位开始从前往后比较相邻两个数字若前者大则交换两数字位置然后比较位向右移动一位。第 1 轮从前到后的比较将使得最大的数字“冒泡”到最后。第 2 轮同样操作只需比到倒数第二个倒数第一已最大。重复以上操作直至排序完成。代码复杂度// 冒泡排序从小到大排序 static void bubbleSort3(int[] arr) { for (int i arr.length - 1; i 0; i--) { for (int j 0; j i; j) { if (arr[j] arr[j 1]) { int tmp arr[j]; arr[j] arr[j 1]; arr[j 1] tmp; } } } }时间复杂度O(n²)空间复杂度O(1)二、选择排序算法描述长度为 n 的数组中第一次遍历 n-1 个数找到最小的数值与第一个元素交换。第二次遍历 n-2 个数找到最小的数值与第二个元素交换。重复操作直至第 n-1 次遍历完成排序。代码复杂度public void selectSort3(int[] arr) { for (int i 0; i arr.length; i) { int minTmp Integer.MAX_VALUE; int index 0; // 寻找本轮最小的数字 for (int j i; j arr.length; j) { if (minTmp arr[j]) { minTmp arr[j]; index j; } } // 将最小值交换到数组前方 int temp arr[i]; arr[i] minTmp; arr[index] temp; } }时间复杂度O(n²)空间复杂度O(1)三、插入排序算法描述将第一个元素视为有序序列其余元素为未排序序列。依次扫描未排序序列将每个元素插入有序序列的适当位置。若待插入元素与有序序列中某元素相等插入到其后方。代码复杂度分析/* 插入排序从小到大排序 */ static void insertSort(int[] arr) { for (int i 1; i arr.length; i) { int now arr[i]; // 当前待插入元素 int j i - 1; // 有序序列的末尾索引 while (j 0 now arr[j]) { arr[j 1] arr[j]; j--; } arr[j 1] now; } }时间复杂度O(n²)空间复杂度O(1)四、希尔排序算法步骤将整个序列分割为若干子序列分别进行直接插入排序。待序列基本有序后再对全体记录进行一次直接插入排序。代码复杂度分析// 希尔排序从小到大 static void shellSort(int[] arr) { for (int interval arr.length / 2; interval 0; interval / 2) { for (int i interval; i arr.length; i) { int temp arr[i]; int j i - interval; while (j 0 temp arr[j]) { arr[j interval] arr[j]; j - interval; } arr[j interval] temp; } } }时间复杂度O(n log n)平均空间复杂度O(1)五、归并排序算法描述分治法先递归分解数组再合并排序。代码复杂度分析public static void mergeSort(int[] arr, int left, int right) { if (left right) { int mid (left right) / 2; mergeSort(arr, left, mid); mergeSort(arr, mid 1, right); merge(arr, left, mid, right); } } private static void merge(int[] arr, int left, int mid, int right) { // 合并逻辑略 }时间复杂度O(n log n)空间复杂度O(n)