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

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

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;
}

四、所有排序对比总表

五、关键考点总结