数据结构-8.Java. 七大排序算法

Java 中的七大经典排序算法详解

在 Java 中讨论排序算法时，通常指以下七种最经典、最常被考察的排序算法（大学数据结构课 + 面试最常出现的组合）：

1. 冒泡排序 (Bubble Sort)
2. 选择排序 (Selection Sort)
3. 插入排序 (Insertion Sort)
4. 希尔排序 (Shell Sort)
5. 归并排序 (Merge Sort)
6. 快速排序 (Quick Sort)
7. 堆排序 (Heap Sort)

下面给出Java 实现 + 核心思想 + 时间/空间复杂度 + 稳定性 + 适用场景的完整对比与代码。

复杂度与特性一览表

1.冒泡排序（Bubble Sort）

publicstaticvoidbubbleSort(int[]arr){intn=arr.length;for(inti=0;i<n-1;i++){booleanswapped=false;for(intj=0;j<n-i-1;j++){if(arr[j]>arr[j+1]){// 交换inttemp=arr[j];arr[j]=arr[j+1];arr[j+1]=temp;swapped=true;}}// 优化：如果一趟没有交换，已经有序if(!swapped)break;}}

2. 选择排序（Selection Sort）

publicstaticvoidselectionSort(int[]arr){intn=arr.length;for(inti=0;i<n-1;i++){intminIdx=i;for(intj=i+1;j<n;j++){if(arr[j]<arr[minIdx]){minIdx=j;}}// 交换inttemp=arr[i];arr[i]=arr[minIdx];arr[minIdx]=temp;}}

3. 插入排序（Insertion Sort）

publicstaticvoidinsertionSort(int[]arr){intn=arr.length;for(inti=1;i<n;i++){intkey=arr[i];intj=i-1;// 将比 key 大的元素向后移动while(j>=0&&arr[j]>key){arr[j+1]=arr[j];j--;}arr[j+1]=key;}}

4. 希尔排序（Shell Sort）

publicstaticvoidshellSort(int[]arr){intn=arr.length;// 初始间隔可以有很多取法，这里用 n/2 递减for(intgap=n/2;gap>0;gap/=2){// 对每个分组进行插入排序for(inti=gap;i<n;i++){inttemp=arr[i];intj;for(j=i;j>=gap&&arr[j-gap]>temp;j-=gap){arr[j]=arr[j-gap];}arr[j]=temp;}}}

5. 归并排序（Merge Sort）

publicstaticvoidmergeSort(int[]arr){if(arr==null||arr.length<=1)return;int[]temp=newint[arr.length];mergeSort(arr,0,arr.length-1,temp);}privatestaticvoidmergeSort(int[]arr,intleft,intright,int[]temp){if(left>=right)return;intmid=left+(right-left)/2;mergeSort(arr,left,mid,temp);mergeSort(arr,mid+1,right,temp);merge(arr,left,mid,right,temp);}privatestaticvoidmerge(int[]arr,intleft,intmid,intright,int[]temp){inti=left,j=mid+1,k=left;while(i<=mid&&j<=right){temp[k++]=arr[i]<=arr[j]?arr[i++]:arr[j++];}while(i<=mid)temp[k++]=arr[i++];while(j<=right)temp[k++]=arr[j++];System.arraycopy(temp,left,arr,left,right-left+1);}

6. 快速排序（Quick Sort）——最经典版本

publicstaticvoidquickSort(int[]arr){if(arr==null||arr.length<=1)return;quickSort(arr,0,arr.length-1);}privatestaticvoidquickSort(int[]arr,intlow,inthigh){if(low>=high)return;// 优化：小数组用插入排序if(high-low<=10){insertionSort(arr,low,high);return;}intpivotIndex=partition(arr,low,high);quickSort(arr,low,pivotIndex-1);quickSort(arr,pivotIndex+1,high);}privatestaticintpartition(int[]arr,intlow,inthigh){// 随机化 pivot 防止最坏情况intrandomIdx=low+(int)(Math.random()*(high-low+1));swap(arr,randomIdx,high);intpivot=arr[high];inti=low-1;for(intj=low;j<high;j++){if(arr[j]<pivot){i++;swap(arr,i,j);}}swap(arr,i+1,high);returni+1;}privatestaticvoidswap(int[]arr,inti,intj){inttemp=arr[i];arr[i]=arr[j];arr[j]=temp;}privatestaticvoidinsertionSort(int[]arr,intlow,inthigh){for(inti=low+1;i<=high;i++){intkey=arr[i];intj=i-1;while(j>=low&&arr[j]>key){arr[j+1]=arr[j];j--;}arr[j+1]=key;}}

7. 堆排序（Heap Sort）

publicstaticvoidheapSort(int[]arr){intn=arr.length;// 建堆（从第一个非叶子节点开始）for(inti=n/2-1;i>=0;i--){heapify(arr,n,i);}// 依次把最大值放到末尾for(inti=n-1;i>0;i--){swap(arr,0,i);heapify(arr,i,0);}}privatestaticvoidheapify(int[]arr,intn,inti){intlargest=i;intleft=2*i+1;intright=2*i+2;if(left<n&&arr[left]>arr[largest])largest=left;if(right<n&&arr[right]>arr[largest])largest=right;if(largest!=i){swap(arr,i,largest);heapify(arr,n,largest);}}

面试最常问的对比与总结问题

1. 哪种排序最稳定？ → 归并排序、插入排序、冒泡排序
2. 哪种排序空间复杂度最低？ → 堆排序、选择排序、插入排序、冒泡排序、希尔排序（O(1)）
3. 为什么 Java 的 Arrays.sort() 默认使用快速排序 + 双轴快速排序 + 插入排序混合？
4. 快速排序最坏情况如何避免？（随机化 pivot、三数取中、双轴快排）
5. 什么时候用归并排序比快速排序更好？（需要稳定排序、大数据外部排序、链表排序）

如果你正在准备面试，建议把快速排序、归并排序、堆排序的代码 + 手写 partition / merge / heapify 过程练熟，这是高频手撕代码题。

需要哪一个算法的更详细的动图讲解思路、边界case分析、还是完整测试代码？
或者想看 Java 中内置排序（Arrays.sort、Collections.sort）的底层实现细节？