七大算法完整总结：冒泡 / 插入 / 选择 / 快排 / 归并 / 堆排 + 二分查找

一、基础三大简单排序稳定 / 不稳定、时间空间1. 冒泡排序 BubbleSort思路相邻元素两两比较大值往后冒泡每轮把最大值沉到末尾。时间复杂度 最好有序(O(n))最坏 / 平均 (O(n^2))空间复杂度(O(1)) 原地排序稳定性稳定相等元素不交换缺点大量无效交换大数据完全不适用void bubble(int[] arr){ for(int i0;iarr.length;i){ boolean flag true; for(int j0;jarr.length-1-i;j){ if(arr[j]arr[j1]){ int tarr[j];arr[j]arr[j1];arr[j1]t; flagfalse; } } if(flag) break; } }2. 插入排序 InsertSort思路把数组分为有序前缀 无序后缀逐个取出无序元素向前插入到有序区对应位置。时间复杂度 最好有序(O(n))最坏 / 平均 (O(n^2))空间(O(1))稳定性稳定优点数据接近有序时极快小数据场景优秀void insert(int[] arr){ for(int i1;iarr.length;i){ int curarr[i]; int ji-1; for(;j0arr[j]cur;j--) arr[j1]arr[j]; arr[j1]cur; } }3. 选择排序 SelectSort思路每轮遍历无序区间找到最小值和无序区间首元素交换。时间复杂度无论有序与否恒 (O(n^2))空间(O(1))稳定性不稳定交换会打乱相等元素相对位置缺点无论数据是否有序都要完整遍历性能差void select(int[] arr){ for(int i0;iarr.length;i){ int minIdxi; for(int ji1;jarr.length;j) if(arr[j]arr[minIdx]) minIdxj; int tarr[i];arr[i]arr[minIdx];arr[minIdx]t; } }二、高级排序工程常用(O(nlogn))4. 快速排序 QuickSort思路分治选基准 pivot把小于 pivot 放左边、大于放右边递归左右子区间。时间复杂度 平均 / 最好 (O(nlogn))最坏有序数组(O(n^2))空间复杂度(O(logn)O(n))递归栈稳定性不稳定工程特点综合最快JDK Arrays.sort 对基础类型使用双轴快排void quick(int[] arr,int l,int r){ if(lr) return; int pivotarr[l],il,jr; while(ij){ while(ijarr[j]pivot) j--; arr[i]arr[j]; while(ijarr[i]pivot) i; arr[j]arr[i]; } arr[i]pivot; quick(arr,l,i-1); quick(arr,i1,r); }5. 归并排序 MergeSort思路分治先递归二分拆分数组拆分到单个元素后有序合并两个有序数组。时间复杂度稳定 (O(nlogn))无最坏退化空间复杂度(O(n)) 需要辅助数组稳定性稳定适用场景大数据外部排序、要求稳定排序场景void mergeSort(int[] arr,int l,int r,int[] temp){ if(lr) return; int mid(lr)/2; mergeSort(arr,l,mid,temp); mergeSort(arr,mid1,r,temp); merge(arr,l,mid,r,temp); } // 合并两个有序区间 void merge(int[] arr,int l,int mid,int r,int[] temp){ int il,jmid1,k0; while(imidjr){ if(arr[i]arr[j]) temp[k]arr[i]; else temp[k]arr[j]; } while(imid) temp[k]arr[i]; while(jr) temp[k]arr[j]; for(int x0;xk;x) arr[lx]temp[x]; }6. 堆排序 HeapSort思路利用大顶堆特性堆顶是最大值循环把堆顶交换到数组末尾再调整堆。时间复杂度稳定 (O(nlogn))空间复杂度(O(1)) 原地排序稳定性不稳定特点最坏性能优于快排不占用额外辅助空间但缓存不友好void heapSort(int[] arr){ // 建大顶堆 for(int iarr.length/2-1;i0;i--) adjustHeap(arr,i,arr.length); // 堆顶与末尾交换调整堆 for(int iarr.length-1;i0;i--){ int tarr[0];arr[0]arr[i];arr[i]t; adjustHeap(arr,0,i); } } void adjustHeap(int[] arr,int root,int len){ int curarr[root]; for(int leftroot*21;leftlen;leftleft*21){ if(left1lenarr[left]arr[left1]) left; if(curarr[left]) break; arr[root]arr[left]; rootleft; } arr[root]cur; }三、二分查找 BinarySearch查找算法非排序前提数组必须升序有序思路不断取中间值缩小查找区间一次排除一半数据时间复杂度(O(logn))空间(O(1)) 迭代版(O(logn)) 递归版作用查找目标值、查找左 / 右边界、二分答案int binarySearch(int[] arr,int target){ int l0,rarr.length-1; while(lr){ int midl(r-l)/2; // 防止溢出 if(arr[mid]target) return mid; else if(arr[mid]target) lmid1; else rmid-1; } return -1; }四、所有排序对比总表排序算法平均时间最坏时间空间稳定性核心特点冒泡\(O(n^2)\)\(O(n^2)\)\(O(1)\)稳定有序数据可提前终止插入\(O(n^2)\)\(O(n^2)\)\(O(1)\)稳定近乎有序时速度极快选择\(O(n^2)\)\(O(n^2)\)\(O(1)\)不稳定交换次数少遍历无法提前退出快速\(O(nlogn)\)\(O(n^2)\)\(O(logn)\)不稳定综合速度最快大数据首选归并\(O(nlogn)\)\(O(nlogn)\)\(O(n)\)稳定性能稳定适合外部排序堆排\(O(nlogn)\)\(O(nlogn)\)\(O(1)\)不稳定原地nlogn缓存较差五、关键考点总结稳定排序冒泡、插入、归并其余快排、堆排、选择都是不稳定原地排序\(O(1)\)空间冒泡、插入、选择、堆排最坏仍保证 \(O(nlogn)\)归并、堆排快排有序数据会退化\(O(n^2)\)二分查找只用于有序数组核心是折半缩小区间