八大排序算法详解（Java版｜面试必备）

在算法和面试中“八大排序”是必须掌握的基础内容。本文从原理 代码 复杂度 使用场景系统整理八种常见排序算法适合复习与面试速记。一、排序算法总览常见八大排序冒泡排序Bubble Sort选择排序Selection Sort插入排序Insertion Sort希尔排序Shell Sort归并排序Merge Sort快速排序Quick Sort堆排序Heap Sort基数排序Radix Sort二、冒泡排序Bubble Sort原理不断比较相邻元素把较大的数“冒泡”到后面。代码public static void bubbleSort(int[] arr){ for(int i 0; i arr.length - 1; i){ for(int j 0; j arr.length - 1 - i; j){ if(arr[j] arr[j1]){ int temp arr[j]; arr[j] arr[j1]; arr[j1] temp; } } } }特点时间复杂度O(n²)稳定排序简单但效率低三、选择排序Selection Sort原理每一轮选择最小的元素放到前面。代码public static void selectionSort(int[] arr){ for(int i 0; i arr.length - 1; i){ int minIndex i; for(int j i 1; j arr.length; j){ if(arr[j] arr[minIndex]){ minIndex j; } } int temp arr[i]; arr[i] arr[minIndex]; arr[minIndex] temp; } }特点时间复杂度O(n²)不稳定排序交换次数少四、插入排序Insertion Sort原理将数组分为已排序和未排序部分每次插入到正确位置。代码public static void insertionSort(int[] arr){ for(int i 1; i arr.length; i){ int temp arr[i]; int j i - 1; while(j 0 arr[j] temp){ arr[j1] arr[j]; j--; } arr[j1] temp; } }特点时间复杂度O(n²)最好情况O(n)稳定排序适合小规模数据五、希尔排序Shell Sort原理通过“分组 插入排序”提升效率。代码public static void shellSort(int[] arr){ for(int gap arr.length/2; gap 0; gap / 2){ for(int i gap; i arr.length; i){ int temp arr[i]; int j i; while(j - gap 0 arr[j-gap] temp){ arr[j] arr[j-gap]; j - gap; } arr[j] temp; } } }特点时间复杂度约 O(n log n)不稳定排序插入排序优化版六、归并排序Merge Sort原理分治思想分解 → 排序 → 合并代码public static void mergeSort(int[] arr, int left, int right){ if(left right) return; int mid (left right) / 2; mergeSort(arr, left, mid); mergeSort(arr, mid 1, right); merge(arr, left, mid, right); } public static void merge(int[] arr, int left, int mid, int right){ int[] temp new int[right - left 1]; int i left, j mid 1, k 0; while(i mid j right){ if(arr[i] arr[j]){ temp[k] arr[i]; }else{ temp[k] arr[j]; } } while(i mid) temp[k] arr[i]; while(j right) temp[k] arr[j]; for(int t 0; t temp.length; t){ arr[left t] temp[t]; } }特点时间复杂度O(n log n)稳定排序需要额外空间七、快速排序Quick Sort原理选一个基准值小的放左边大的放右边。代码public static void quickSort(int[] arr, int left, int right){ if(left right) return; int pivot arr[left]; int l left, r right; while(l r){ while(l r arr[r] pivot) r--; arr[l] arr[r]; while(l r arr[l] pivot) l; arr[r] arr[l]; } arr[l] pivot; quickSort(arr, left, l - 1); quickSort(arr, l 1, right); }特点平均O(n log n)最坏O(n²)不稳定排序实际最快平均情况八、堆排序Heap Sort原理利用大顶堆将最大值放到数组末尾。代码public static void heapSort(int[] arr){ for(int i arr.length/2 - 1; i 0; i--){ adjustHeap(arr, i, arr.length); } for(int j arr.length - 1; j 0; j--){ int temp arr[0]; arr[0] arr[j]; arr[j] temp; adjustHeap(arr, 0, j); } } public static void adjustHeap(int[] arr, int i, int length){ int temp arr[i]; for(int k i*2 1; k length; k k*2 1){ if(k 1 length arr[k] arr[k1]){ k; } if(arr[k] temp){ arr[i] arr[k]; i k; }else{ break; } } arr[i] temp; }特点时间复杂度O(n log n)不稳定排序不需要额外空间九、基数排序Radix Sort原理按位排序个位 → 十位 → 百位代码public static void radixSort(int[] arr){ int max arr[0]; for(int num : arr){ if(num max){ max num; } } int maxLength (max ).length(); int[][] bucket new int[10][arr.length]; int[] bucketCount new int[10]; for(int i 0, n 1; i maxLength; i, n * 10){ for(int num : arr){ int digit num / n % 10; bucket[digit][bucketCount[digit]] num; } int index 0; for(int k 0; k 10; k){ for(int j 0; j bucketCount[k]; j){ arr[index] bucket[k][j]; } bucketCount[k] 0; } } }特点时间复杂度O(nk)稳定排序适合整数排序十、总结对比重点记忆排序算法时间复杂度稳定性冒泡排序O(n²)稳定选择排序O(n²)不稳定插入排序O(n²)稳定希尔排序O(n log n)不稳定归并排序O(n log n)稳定快速排序O(n log n)不稳定堆排序O(n log n)不稳定基数排序O(nk)稳定十一、面试重点总结必背O(n²)冒泡、选择、插入O(n log n)归并、快排、堆排序稳定排序冒泡、插入、归并、基数最快排序快速排序平均情况占空间归并排序十二、结语排序算法不仅是基础更是面试的高频考点。建议重点掌握快速排序必须会手写归并排序理解分治堆排序理解堆结构如果你准备面试可以重点记住时间复杂度 稳定性 适用场景基本就能应对大部分问题。