1. 排序的概念及引用1.1 排序的概念排序所谓排序就是使一串记录按照其中的某个或某些关键字的大小递增或递减的排列起来的操作。稳定性假定在待排序的记录序列中存在多个具有相同的关键字的记录若经过排序这些记录的相对次序保持不变即在原序列中r[i]r[j]且r[i]在r[j]之前而在排序后的序列中r[i]仍在r[j]之前则称这种排序算法是稳定的否则称为不稳定的。1.2 常见的排序算法2. 常见排序算法的实现2.1 插入排序2.1.1基本思想直接插入排序是一种简单的插入排序法其基本思想是把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中直到所有的记录插入完为止得到一个新的有序序列 。实际中我们玩扑克牌时就用了插入排序的思想。2.1.2 直接插入排序// 插入排序 //**************************************** // 时间复杂度 ON*N //最坏情况是逆序最好请情况是顺序 //空间复杂度 O(1) //稳定性:稳定的排序 //**************************************** public class test { /** * 直接插入排序 * 思想 * 1. 把数组分为【已排序部分】和【未排序部分】 * 2. 每次取未排序的第一个数往前插入到合适位置 * 3. 前面比它大的元素统一后移 */ public static void insertSort(int[] arr) { // 1. 边界情况处理 if (arr null || arr.length 1) { return; } int n arr.length; // 2. 从第二个元素开始i从1开始依次往前插入 for (int i 1; i n; i) { // 把当前要插入的数拿出来避免被覆盖 int tmp arr[i]; // j 从 i-1 开始往前找 int j i - 1; // 3. 前面的数比 tmp 大就往后挪 while (j 0 arr[j] tmp) { arr[j 1] arr[j]; // 元素后移 j--; } // 4. 退出循环时j1 就是插入位置 arr[j 1] tmp; } } // 测试主方法 public static void main(String[] args) { // 待排序数组 int[] arr {3, 1, 5, 2, 4, 6}; System.out.println(排序前 Arrays.toString(arr)); // 调用直接插入排序 insertSort(arr); System.out.println(排序后 Arrays.toString(arr)); } }直接插入排序的特性总结元素集合越接近有序直接插入排序算法的时间效率越高时间复杂度O(N2N^2N2)空间复杂度O(1)它是一种稳定的排序算法稳定性稳定2.1.3 希尔排序( 缩小增量排序 )希尔排序法的基本思想是先选定一个整数把待排序文件中所有记录分成多个组所有距离为的记录分在同一组内并对每一组内的记录进行排序。然后取重复上述分组和排序的工作。当到达1时所有记录在统一组内排好序。// 希尔排序 是直接排序的优化 //**************************************** // 时间复杂度 ON^1.3 -- N^1.5 //空间复杂度 O(1) //稳定性:不稳定的排序 //**************************************** public class test { public static void shellSort(int[] arr) { int n arr.length; // 控制间隔 gap每次除以 2 for (int gap n / 2; gap 0; gap / 2) { // 对每一组做插入排序 for (int i gap; i n; i) { int tmp arr[i]; int j; // 每组内部往前插 for (j i; j gap arr[j - gap] tmp; j - gap) { arr[j] arr[j - gap]; } arr[j] tmp; } } } public static void main(String[] args) { int[] arr {9,5,1,4,3,8,2,6,7}; System.out.println(排序前 Arrays.toString(arr)); shellSort(arr); System.out.println(排序后 Arrays.toString(arr)); } }2.2 选择排序2.2.1基本思想每一次从待排序的数据元素中选出最小或最大的一个元素存放在序列的起始位置直到全部待排序的数据元素排完 。2.2.2 直接选择排序:在元素集合array[i]–array[n-1]中选择关键码最大(小)的数据元素若它不是这组元素中的最后一个(第一个)元素则将它与这组元素中的最后一个第一个元素交换在剩余的array[i]–array[n-2]array[i1]–array[n-1]集合中重复上述步骤直到集合剩余1个元素// 选择排序 // 时间复杂度 ON^2 //空间复杂度 O(1) //稳定性:不稳定的排序 public class test { public static void selectSort(int[] array) { for (int i 0; i array.length; i) { int mindIndex i; for (int j i 1; j array.length; j) { if (array[j] array[mindIndex]) { mindIndex j; } } swap(array, i, mindIndex); } } private static void swap(int[] array, int i, int j) { int tmp array[i]; array[i] array[j]; array[j] tmp; } public static void main(String[] args) { int[] array {9,1,2,5,7,4,8,6,3,5}; System.out.println(排序前 Arrays.toString(array)); selectSort(array); System.out.println(排序后 Arrays.toString(array)); } }2.2.3 堆排序堆排序(Heapsort)是指利用堆积树堆这种数据结构所设计的一种排序算法它是选择排序的一种。它是通过堆进行选择数据。需要注意的是排升序要建大堆排降序建小堆。//********************************************* //************* 堆排序 ******************** // 时间复杂度 ON * log N) //空间复杂度 O(1) //稳定性:不稳定的排序 public class test { public static void heapSort(int[] array) { creatHeap(array); int end array.length - 1; while (end 0) { swap(array, 0, end); siftDown(array, 0, end); end--; } } // 创建大根堆 private static void creatHeap(int[] array) { for (int parent (array.length - 1 - 1) / 2; parent 0; parent--) { siftDown(array, parent, array.length); } } // 向下调整 private static void siftDown(int[] array, int parent, int length) { int child 2 * parent 1; while (child length) { // 找最大的孩子 if (child 1 length array[child] array[child 1]) { child; } // 父节点 孩子则交换 if (array[child] array[parent]) { swap(array, parent, child); parent child; child 2 * parent 1; } else { break; } } } private static void swap(int[] array, int parent, int child) { int tmp array[parent]; array[parent] array[child]; array[child] tmp; } public static void main(String[] args) { int[] array {9,1,2,5,7,4,8,6,3,5}; System.out.println(排序前 Arrays.toString(array)); heapSort(array); System.out.println(排序后 Arrays.toString(array)); } }2.3 交换排序2.3.1基本思想所谓交换就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置交换排序的特点是将键值较大的记录向序列的尾部移动键值较小的记录向序列的前部移动。2.3.2冒泡排序//********************************************* //************* 冒泡排序 ****************** // 时间复杂度 ON^2)---不优化 优化之后O(N) //空间复杂度 O(1) //稳定性:稳定的排序 public class test { public static void bubbleSort(int[] array) { for (int i 0; i array.length - 1; i) { boolean flg false; for (int j 0; j array.length - 1 - i; j) { if (array[j] array[j 1]) { swap(array, j, j 1); flg true; } } if (flg false) { break; } } } private static void swap(int[] array, int j, int i) { int tmp array[j]; array[j] array[i]; array[i] tmp; } public static void main(String[] args) { int[] array {9,1,2,5,7,4,8,6,3,5}; System.out.println(排序前 Arrays.toString(array)); bubbleSort(array); System.out.println(排序后 Arrays.toString(array)); } } 一句话总结冒泡排序无法在所有场景下优化到 O (n)但通过交换标记 记录最后交换位置可以让它在数组有序 / 接近有序时时间复杂度降到O(n)这是冒泡排序的最优优化方案。2.3.3 快速排序基本思想为任取待排序元素序列中的某元素作为基准值按照该排序码将待排序集合分割成两子序列左子序列中所有元素均小于基准值右子序列中所有元素均大于基准值然后最左右子序列重复该过程直到所有元素都排列在相应位置上为止。快速排序1 Hoare法//********************************************* //************* 快速排序1 Hoare法 ******** // 时间复杂度 ON^2)有顺序的情况下是这个---最坏情况 // O(N* logN) ---最好情况 //空间复杂度 ---最坏情况O(N)|||最好情况 ---O(logN) //稳定性:不稳定的排序 public class test { public static void quickSort(int[] array) { quick(array, 0, array.length - 1); } private static void quick(int[] array, int start, int end) { if (start end) return; int pivot partition(array, start, end); quick(array, start, pivot - 1); quick(array, pivot 1, end); } private static int partition(int[] array, int left, int right) { int tmp array[left]; int tmpLeft left; while (left right) { while (left right array[right] tmp) { right--; } while (left right array[left] tmp) { left; } swap(array, left, right); } swap(array, left, tmpLeft); return left; } private static void swap(int[] array, int j, int i) { int tmp array[j]; array[j] array[i]; array[i] tmp; } public static void main(String[] args) { int[] array {9,1,2,5,7,4,8,6,3,5}; System.out.println(排序前 Arrays.toString(array)); quickSort(array); System.out.println(排序后 Arrays.toString(array)); } }快速排序2 挖坑法//********************************************* //************* 快速排序2 挖坑法 *********** public class test { public static void quickSort(int[] array) { quick(array, 0, array.length - 1); } private static void quick(int[] array, int start, int end) { if (start end) return; int pivot partition(array, start, end); quick(array, start, pivot - 1); quick(array, pivot 1, end); } private static int partition(int[] array, int left, int right) { int tmp array[left]; //int tmpLeft left; while (left right) { while (left right array[right] tmp) { right--; } array[left] array[right]; while (left right array[left] tmp) { left; } swap(array, left, right); } //swap(array,left,tmpLeft); array[left] tmp; return left; } private static void swap(int[] array, int j, int i) { int tmp array[j]; array[j] array[i]; array[i] tmp; } public static void main(String[] args) { int[] array {9,1,2,5,7,4,8,6,3,5}; System.out.println(排序前 Arrays.toString(array)); quickSort(array); System.out.println(排序后 Arrays.toString(array)); } }快速排序3 前后指针法public class test { //********************************************* //************* 快速排序3 前后指针法 ******************** public static void quickSort(int[] array){ quick(array,0,array.length - 1); } private static void quick(int[] array, int start, int end) { if(start end) return; int pivot partition(array, start, end); quick(array, start, pivot-1); quick(array, pivot1, end); } private static int partition(int[] array, int left, int right) { int prev left; int cur left 1; while (cur right){ if(array[cur] array[left] array[prev] ! array[cur]){ swap(array,cur,prev); } cur; } swap(array,prev,left); return prev; } private static void swap(int[] array, int j, int i) { int tmp array[j]; array[j] array[i]; array[i] tmp; } public static void main(String[] args) { int[] array {9,1,2,5,7,4,8,6,3,5}; System.out.println(排序前 Arrays.toString(array)); quickSort(array); System.out.println(排序后 Arrays.toString(array)); } }2.4 归并排序2.4.1 基本思想归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并得到完全有序的序列即先使每个子序列有序再使子序列段间有序。若将两个有序表合并成一个有序表称为二路归并。 归并排序核心步骤public class test { //********************************************* //************* 归并排序 ****************** // 时间复杂度 O(N*logN) //空间复杂度 O(N) //稳定性:稳定的排序 public static void mergeSort(int[] array){ mergeSortTmp(array,0,array.length - 1); } //分解 private static void mergeSortTmp(int[] array, int left, int right) { if(left right){ return; } int mid (right left) / 2; mergeSortTmp(array,left,mid); mergeSortTmp(array,mid 1,right); merge(array, left, mid, right); } //合并 private static void merge(int[]array, int left, int mid, int right){ int[] tmp new int[right - left 1]; int k 0; int s1 left; int s2 mid 1; while (s1 mid s2 right){ if(array[s1] array[s2]){ tmp[k] array[s1]; }else { tmp[k] array[s2]; } } while (s1 mid){ tmp[k] array[s1]; } while (s2 right){ tmp[k] array[s2]; } for (int i 0; i k; i) { array[i left] tmp[i]; } } public static void main(String[] args) { int[] array {9,1,2,5,7,4,8,6,3,5}; System.out.println(排序前 Arrays.toString(array)); mergeSort(array); System.out.println(排序后 Arrays.toString(array)); } }排序方法最好时间复杂度平均时间复杂度最坏时间复杂度空间复杂度稳定性冒泡排序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(n)O(n^1.3)O(n²)O(1)不稳定堆排序O(n log n)O(n log n)O(n log n)O(1)不稳定快速排序O(n log n)O(n log n)O(n²)O(log n) ~ O(n)不稳定归并排序O(n log n)O(n log n)O(n log n)O(n)稳定1. 计数排序思想计数排序又称为鸽巢原理是对哈希直接定址法的变形应用。 操作步骤统计相同元素出现次数根据统计的结果将序列回收到原来的序列中public class test { public static void countSort(int[] arr) { if (arr null || arr.length 1) { return; } // 1. 找最大值 int max arr[0]; for (int num : arr) { if (num max) max num; } // 2. 开辟计数数组 int[] count new int[max 1]; // 3. 统计每个数字出现次数 for (int num : arr) { count[num]; } // 4. 按计数重新填回原数组 int index 0; for (int i 0; i max; i) { while (count[i] 0) { arr[index] i; count[i]--; } } } public static void main(String[] args) { int[] arr {9,1,2,5,7,4,8,6,3,5}; System.out.println(排序前 Arrays.toString(arr)); countSort(arr); System.out.println(排序后 Arrays.toString(arr)); } }计数排序在数据范围集中时效率很高但是适用范围及场景有限。时间复杂度O(MAX(N,范围))空间复杂度O(范围)稳定性稳定2.基数排序从最低位到最高位一轮一轮排每一轮都是一次计数排序排完最高位就整体有序public class test {public static void radixSort(int[] arr) {if (arr null || arr.length 1) return;// 1. 找最大值确定最大位数 int max arr[0]; for (int num : arr) { if (num max) max num; } // 2. 对每一位个位、十位、百位...分别计数排序 for (int exp 1; max / exp 0; exp * 10) { countSortByExp(arr, exp); } } // 按某一位exp1 个位, exp10 十位...进行计数排序 private static void countSortByExp(int[] arr, int exp) { int n arr.length; int[] tmp new int[n]; // 临时数组 int[] count new int[10];// 0~9 共10个数字 // 统计当前位出现次数 for (int num : arr) { int digit (num / exp) % 10; count[digit]; } // 前缀和确定位置 for (int i 1; i 10; i) { count[i] count[i - 1]; } // 从后往前遍历保证稳定性 for (int i n - 1; i 0; i--) { int num arr[i]; int digit (num / exp) % 10; tmp[--count[digit]] num; } // 拷贝回原数组 System.arraycopy(tmp, 0, arr, 0, n); } public static void main(String[] args) { int[] arr {12, 32, 11, 35, 22, 31}; System.out.println(排序前 Arrays.toString(arr)); radixSort(arr); System.out.println(排序后 Arrays.toString(arr)); }时间复杂度O (n × d)n数组长度d最大数字的位数如 9999 → d4空间复杂度O (n)稳定性稳定3.桶排序import java.util.*; public class test { /** * 桶排序适用于 [0, 1) 区间的浮点数 * param arr 待排序数组 */ public static void bucketSort(double[] arr) { // 边界判断 if (arr null || arr.length 1) { return; } int n arr.length; // 1. 创建桶这里用 ArrayList 存每个桶的元素 ListDouble[] buckets new ArrayList[n]; for (int i 0; i n; i) { buckets[i] new ArrayList(); } // 2. 将元素放入对应桶 for (double num : arr) { // 映射到桶索引[0,1) → 0~n-1 int bucketIdx (int) (num * n); buckets[bucketIdx].add(num); } // 3. 对每个桶内部排序这里用 Java 内置的排序本质是 TimSort for (ListDouble bucket : buckets) { Collections.sort(bucket); } // 4. 按桶顺序合并结果 int idx 0; for (ListDouble bucket : buckets) { for (double num : bucket) { arr[idx] num; } } } // 测试 public static void main(String[] args) { double[] arr {0.42, 0.32, 0.33, 0.52, 0.37, 0.47, 0.51}; System.out.println(排序前 Arrays.toString(arr)); bucketSort(arr); System.out.println(排序后 Arrays.toString(arr)); } }创建桶用数组ListType[]存储每个桶是一个列表。映射入桶根据数值范围计算桶索引将元素放入对应桶。浮点数bucketIdx (int)(num * n)整数bucketIdx num - min桶内排序对每个桶单独排序小数据量用插入排序也可以。合并结果按桶的顺序遍历把所有元素依次放回原数组。时间复杂度平均O(n)最坏O(n²)数据分布极不均匀时空间复杂度O(n k)k为桶数量稳定性稳定桶内用稳定排序时