一、基础三大简单排序（稳定 / 不稳定、时间空间）

1. 冒泡排序 BubbleSort

思路：相邻元素两两比较，大值往后冒泡，每轮把最大值沉到末尾。

• 时间复杂度： 最好（有序）(O(n))；最坏 / 平均 (O(n^2))
• 空间复杂度：(O(1)) 原地排序
• 稳定性：稳定（相等元素不交换）
• 缺点：大量无效交换，大数据完全不适用

void bubble(int[] arr){ for(int i=0;i<arr.length;i++){ boolean flag = true; for(int j=0;j<arr.length-1-i;j++){ if(arr[j]>arr[j+1]){ int t=arr[j];arr[j]=arr[j+1];arr[j+1]=t; flag=false; } } if(flag) break; } }

2. 插入排序 InsertSort

思路：把数组分为有序前缀 + 无序后缀；逐个取出无序元素，向前插入到有序区对应位置。

• 时间复杂度： 最好（有序）(O(n))；最坏 / 平均 (O(n^2))
• 空间：(O(1))
• 稳定性：稳定
• 优点：数据接近有序时极快，小数据场景优秀

void insert(int[] arr){ for(int i=1;i<arr.length;i++){ int cur=arr[i]; int j=i-1; for(;j>=0&&arr[j]>cur;j--) arr[j+1]=arr[j]; arr[j+1]=cur; } }

3. 选择排序 SelectSort

思路：每轮遍历无序区间找到最小值，和无序区间首元素交换。

• 时间复杂度：无论有序与否，恒 (O(n^2))
• 空间：(O(1))
• 稳定性：不稳定（交换会打乱相等元素相对位置）
• 缺点：无论数据是否有序都要完整遍历，性能差

void select(int[] arr){ for(int i=0;i<arr.length;i++){ int minIdx=i; for(int j=i+1;j<arr.length;j++) if(arr[j]<arr[minIdx]) minIdx=j; int t=arr[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(l>=r) return; int pivot=arr[l],i=l,j=r; while(i<j){ while(i<j&&arr[j]>=pivot) j--; arr[i]=arr[j]; while(i<j&&arr[i]<=pivot) i++; arr[j]=arr[i]; } arr[i]=pivot; quick(arr,l,i-1); quick(arr,i+1,r); }

5. 归并排序 MergeSort

思路：分治；先递归二分拆分数组，拆分到单个元素后，有序合并两个有序数组。

• 时间复杂度：稳定 (O(nlogn))，无最坏退化
• 空间复杂度：(O(n)) 需要辅助数组
• 稳定性：稳定
• 适用场景：大数据外部排序、要求稳定排序场景

void mergeSort(int[] arr,int l,int r,int[] temp){ if(l>=r) return; int mid=(l+r)/2; mergeSort(arr,l,mid,temp); mergeSort(arr,mid+1,r,temp); merge(arr,l,mid,r,temp); } // 合并两个有序区间 void merge(int[] arr,int l,int mid,int r,int[] temp){ int i=l,j=mid+1,k=0; while(i<=mid&&j<=r){ if(arr[i]<=arr[j]) temp[k++]=arr[i++]; else temp[k++]=arr[j++]; } while(i<=mid) temp[k++]=arr[i++]; while(j<=r) temp[k++]=arr[j++]; for(int x=0;x<k;x++) arr[l+x]=temp[x]; }

6. 堆排序 HeapSort

思路：利用大顶堆特性，堆顶是最大值；循环把堆顶交换到数组末尾，再调整堆。

• 时间复杂度：稳定 (O(nlogn))
• 空间复杂度：(O(1)) 原地排序
• 稳定性：不稳定
• 特点：最坏性能优于快排，不占用额外辅助空间，但缓存不友好

void heapSort(int[] arr){ // 建大顶堆 for(int i=arr.length/2-1;i>=0;i--) adjustHeap(arr,i,arr.length); // 堆顶与末尾交换，调整堆 for(int i=arr.length-1;i>0;i--){ int t=arr[0];arr[0]=arr[i];arr[i]=t; adjustHeap(arr,0,i); } } void adjustHeap(int[] arr,int root,int len){ int cur=arr[root]; for(int left=root*2+1;left<len;left=left*2+1){ if(left+1<len&&arr[left]<arr[left+1]) left++; if(cur>=arr[left]) break; arr[root]=arr[left]; root=left; } arr[root]=cur; }

三、二分查找 BinarySearch（查找算法，非排序）

前提：数组必须升序有序思路：不断取中间值缩小查找区间，一次排除一半数据

• 时间复杂度：(O(logn))
• 空间：(O(1)) 迭代版；(O(logn)) 递归版
• 作用：查找目标值、查找左 / 右边界、二分答案

int binarySearch(int[] arr,int target){ int l=0,r=arr.length-1; while(l<=r){ int mid=l+(r-l)/2; // 防止溢出 if(arr[mid]==target) return mid; else if(arr[mid]<target) l=mid+1; else r=mid-1; } return -1; }

四、所有排序对比总表

五、关键考点总结

1. 稳定排序：冒泡、插入、归并；其余快排、堆排、选择都是不稳定
2. 原地排序（\(O(1)\)空间）：冒泡、插入、选择、堆排
3. 最坏仍保证 \(O(nlogn)\)：归并、堆排；快排有序数据会退化\(O(n^2)\)
4. 二分查找只用于有序数组，核心是折半缩小区间