【目标】掌握各种排序方法的底层逻辑时间、空间复杂度等等。1.排序的介绍1.1 排序中的概念排序所谓排序就是使一串记录按照其中的某个或某些关键字的大小递增或递减的排列起来的操作。稳定性假定在待排序的记录序列中存在多个具有相同的关键字的记录若经过排序这些记录的相对次序保持不变则称这种排序算法是稳定的即在原序列中r[i]r[j]且r[i]在r[j]之前而在排序后的序列中r[i]仍在r[j]之前否则称为不稳定的但凡有一组排序后的相对位置发生变化那么就说他是不稳定的。1.2 排序的种类按照数据所在位置进行排序内部排序数据元素全部放在内存中的排序。这类排序算法的特点是能够直接访问所有待排序数据因此通常速度较快适用于数据量不大的场景。常见的内部排序算法包括内部排序算法的时间复杂度从 O(n²) 到 O(n logn) 不等空间复杂度也各有差异需要根据具体场景选择。外部排序当数据元素太多不能同时放在内存中需要借助外部存储如磁盘进行排序。这类排序算法需要处理数据在内存和外部存储之间的移动因此设计时需重点考虑I/O效率。常见的外部排序方法包括1.3 常见的算法分类2.相关排序算法的实现本章所有的排序都以升序为示例。2.1 插入排序“插入”就是把当前这张“牌”从牌堆里抽出来塞到手里已经排好序的牌中正确的位置上。2.1.1 直接插入排序1.效果演示2.代码实现public class Sort { /** * 直接插入排序 * 时间复杂度O(n^2) * 空间复杂度O(1) * 稳定性稳定 */ public static void insertSort(int[] arr) { for (int i 1; i arr.length; i) { int tmp arr[i]; int j i - 1; for (; j 0; j--) { if(arr[j] tmp) { arr[j 1] arr[j]; }else { arr[j 1] tmp; break; } } arr[j 1] tmp; } } }3.时间、空间复杂度和稳定性综上所述时间复杂度O(n^2) -元素集合越接近有序直接插入排序算法的时间效率越高空间复杂度O(1)稳定性稳定在这里提醒一点本段代码对于相同数据的处理是不进行交换所以它是稳定的。但是如果规定在比较相同元素时也进行交换那么它就不是稳定的。所以可以得出一个结论稳定的排序可以变成不稳定的排序但不稳定的排序不可能变成稳定的排序2.1.2 希尔排序1.效果演示2.代码实现public class Sort { /** * 希尔排序 * 时间复杂度O(n^1.3) * 空间复杂度O(1) * 稳定性不稳定 */ public static void shell(int[] arr, int gap) { for (int i gap; i arr.length; i) { int tmp arr[i]; int j i - gap; for (; j 0; j - gap) { if(arr[j] tmp) { arr[j gap] arr[j]; }else { arr[j gap] tmp; break; } } arr[j gap] tmp; } } public static void shellSort(int[] arr) { int gap arr.length; while(gap 0) { gap / 2; shell(arr,gap); } } }3.时间、空间复杂度和稳定性综上所述时间复杂度O(n^1.3)空间复杂度O(1)稳定性不稳定2.2 选择排序“选择”是“从桌上剩余的牌堆里主动挑出最小的那张放到手边”。2.2.1 直接选择排序1.效果演示2.代码实现public class Sort { /** * 直接选择排序 * 时间复杂度O(n^2) * 空间复杂度O(1) * 稳定性不稳定 */ public static void swap(int[] arr, int min_index,int i) { int tmp arr[min_index]; arr[min_index] arr[i]; arr[i] tmp; } public static void selectSort(int[] arr) { for (int i 0; i arr.length; i) { int min_index i; for (int j i 1; j arr.length; j) { if(arr[j] arr[min_index]) { min_index j; } } swap(arr,min_index,i); } } }3.时间、空间复杂度和稳定性综上所述时间复杂度O(n^2)空间复杂度O(1)稳定性不稳定2.2.2 双向选择排序1.效果演示2.代码实现1.缺陷版public class Sort { /** * 双向选择排序 * 时间复杂度O(n^2) * 空间复杂度O(1) * 稳定性不稳定 */ public static void swap(int[] arr, int min_index,int i) { int tmp arr[min_index]; arr[min_index] arr[i]; arr[i] tmp; } public static void doubleSelectSort(int[] arr) { int left 0; int right arr.length - 1; while(left right) { int min_index left; int max_index left; for (int j left 1; j right; j) { if(arr[j] arr[min_index]) { min_index j; } if (arr[j] arr[max_index]) { max_index j; } } swap(arr,min_index,left); swap(arr,max_index,right); left; right--; } } }2.完美版public class Sort { /** * 双向选择排序 * 时间复杂度O(n^2) * 空间复杂度O(1) * 稳定性不稳定 */ public static void swap(int[] arr, int min_index,int i) { int tmp arr[min_index]; arr[min_index] arr[i]; arr[i] tmp; } public static void doubleSelectSort(int[] arr) { int left 0; int right arr.length - 1; while(left right) { int min_index left; int max_index left; for (int j left 1; j right; j) { if(arr[j] arr[min_index]) { min_index j; } if (arr[j] arr[max_index]) { max_index j; } } swap(arr,min_index,left); if(max_index left) { //最大值正好是left下标 max_index min_index; } swap(arr,max_index,right); left; right--; } } }那么大家考虑一个问题就是对于{12,5,2,9,10}这组数据的处理过程是什么样的当max_index left时上述代码就是错误的。所以我们要处理这种情况3.时间、空间复杂度和稳定性双向选择排序是对直接选择排序的优化但是这个优化并没有改变时间复杂度大O的量级。双向选择排序的“优化”体现在把两趟扫描合并成一趟把 n 轮循环变成 n/2 轮。虽然 O 量级没变但常数项大幅降低效率更高指的是实际的运行效率而不是估算的大O的渐进实际跑起来确实更快。时间复杂度O(n^2)空间复杂度O(1)稳定性不稳定2.2.3 堆排序1.效果演示2.代码实现public class Sort { /** * 堆排序 * 时间复杂度O(n*logn) * 空间复杂度O(1) * 稳定性不稳定 */ public static void swap(int[] arr, int min_index,int i) { int tmp arr[min_index]; arr[min_index] arr[i]; arr[i] tmp; } private static void siftDown(int[] arr,int p, int size) { //size 是长度 //保证c是根节点的左子树 int c p * 2 1; while(c size) { if(c 1 size arr[c] arr[c 1]) { //1.保证右子树存在的情况下也不越界 //2.保证c是最大子树的下标 c; } if(arr[p] arr[c]) { //交换最大子树和根节点 swap(arr,p,c); p c; c c * 2 1; }else{ break; } } } private static void creatHeap(int[] arr,int usedSize) { //创建大根堆 for (int p (usedSize - 1 - 1) / 2 ; p 0; p--) { siftDown(arr,p,usedSize); } } public static void heapSort(int[] arr) { //堆排序从小到大 —— 创建大根堆 creatHeap(arr,arr.length); //开始进行遍历调整 for(int end arr.length - 1; end 0; end--) { //把最大的换到最后 swap(arr,0,end);//end是最后一个元素的下标 //对这个堆进行再调整 siftDown(arr,0,end); } } }3.时间、空间复杂度和稳定性综上所述时间复杂度O(n*logn)空间复杂度O(1)稳定性不稳定2.3 交换排序2.3.1 冒泡排序冒泡排序是通过相邻元素的两两比较与交换将未排序序列中的最大值或最小值像气泡一样逐渐“浮”到序列的顶端或“沉”到序列的末端1.效果演示2.代码实现public class Sort { /** * 冒泡排序 * 时间复杂度O(n^2) * 空间复杂度O(1) * 稳定性稳定 */ public static void bubbleSort(int[] arr) { for (int i 0; i arr.length - 1; i) { boolean flag false; for (int j 0; j arr.length - 1 - i; j) { if(arr[j] arr[j 1]) { swap(arr,j,j 1); flag true; } } if(flag false) { break; } } } }3.时间、空间复杂度和稳定性综上所述时间复杂度O(n^2)空间复杂度O(1)稳定性稳定2.3.2 快速排序任取待排序元素序列中的某元素作为基准值按照该排序码将待排序集合分割成两子序列左子序列中所有元素均小于基准值右子序列中所有元素均大于基准值然后最左右子序列重复该过程直到所有元素都排列在相应位置上为止。快速排序的核心是选择一个基准值一般选择第一个元素为基准值然后对这个基准值进行一系列的操作。其中基准值的操作方法有多种方案比如“挖坑法”“Hoare版”“前后指针法”等等这里重点讲述“挖坑法”。1.效果演示所谓“挖坑法”就是把基准值从其所在位置上拿出来然后按照规则把相应的排序对象a放入该空位置处再对排序对象a所在空位置进行上述操作直到所有的都按照规则排好。然后依次对半分依次进行上述排序操作直到排序完。2.代码实现public class Sort { /** * 快速排序 * 时间复杂度O(N*logN) * 空间复杂度O(logN) * 稳定性不稳定 */ public static void quickSort(int[] arr) { quick(arr, 0, arr.length - 1); } public static void quick(int[] arr, int left, int right) { if(left right) { return; } int pivot partition(arr,left,right); //left和right分别标记最左边和最右边 quick(arr,left,pivot - 1); quick(arr,pivot 1,right); } public static int partition(int[] arr,int left,int right) { //让start和end走 int start left; int end right; //选最左边的为标准值 int tmp arr[left]; while(start end) { //右边先走,右找小 while(start end arr[end] tmp) { end--; } arr[start] arr[end]; //左边后走左找大 while(start end arr[start] tmp) { start; } arr[end] arr[start]; } arr[start] tmp; //走到这里表示end和start走到了同一个位置 int pivot start; return pivot; } }3.时间、空间复杂度和稳定性时间复杂度O(N*logN)空间复杂度O(logN)稳定性不稳定2.4 归并排序1.效果演示归并排序的核心思想就是拆解与组装把原来的数据拆成最小部分然后对相应组的最小部分进行重新组装。2.代码实现public class Sort { /** * 归并排序 * 时间复杂度O(N*logN) * 空间复杂度O(N) * 稳定性稳定 */ public static void mergeSort(int[] arr) { merge(arr,0,arr.length - 1); } private static void merge(int[] arr, int left, int right) { int mid (left right) / 2; if(left right) return;//表示不需要拆分了 merge(arr,left,mid); merge(arr,mid 1,right); //到这里分解完成了 merge_m(arr,left,right); //这里组合完成 } private static void merge_m(int[] arr, int left, int right) { int mid (left right) / 2; int s1 left; int e1 mid; int s2 mid 1; int e2 right; int[] tmp new int[right - left 1]; int k 0; while(s1 e1 s2 e2) { if(arr[s1] arr[s2]) { tmp[k] arr[s1]; }else { tmp[k] arr[s2]; } } //结束之后表示的是至少其中一个跑完了 //如果其中一个有剩直接全部放进去就行 while(s1 e1) { tmp[k] arr[s1]; } while (s2 e2) { tmp[k] arr[s2]; } //这样之后已经全部排好序了排好序的数组是tmp不是原来的数组 for (int i 0; i k; i) { arr[i left] tmp[i]; } } }3.时间、空间复杂度和稳定性时间复杂度O(N*logN)空间复杂度O(N)稳定性稳定3. 总结排序排序方法最好时间复杂度平均时间复杂度最坏时间复杂度空间复杂度稳定性冒泡排序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)稳定