Java排序算法全解析：8种经典方法详解与对比
排序算法是计算机科学中的基础模块，也是Java开发中高频使用的工具。无论是处理数据库查询结果、优化搜索算法，还是实现数据可视化，排序都扮演着关键角色。本文将系统梳理Java中8种经典排序算法，从实现原理到性能对比，再到适用场景，为开发者提供一份“下饭”的干货总结。
一、冒泡排序：最基础的排序算法
冒泡排序（Bubble Sort）是排序算法中最直观的一种，其核心思想是通过多次遍历数组，比较相邻元素的大小，将较大的元素逐步“冒泡”到数组的末尾。
实现原理
- 外层循环：控制遍历的轮数，共需n-1轮（n为数组长度）。
- 内层循环：每轮遍历中，比较相邻的两个元素，若顺序错误则交换。
- 优化点：若某一轮未发生交换，说明数组已有序，可提前终止。
代码示例
public static void bubbleSort(int[] arr) {boolean swapped;for (int i = 0; i < arr.length - 1; i++) {swapped = false;for (int j = 0; j < arr.length - 1 - i; j++) {if (arr[j] > arr[j + 1]) {swap(arr, j, j + 1);swapped = true;}}if (!swapped) break; // 提前终止}}private static void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}
性能分析
- 时间复杂度：
- 最坏情况：O(n²)（完全逆序）。
- 最好情况：O(n)（已有序且优化后）。
- 空间复杂度：O(1)（原地排序）。
- 稳定性：稳定（相等元素不交换）。
适用场景
- 数据量小（n < 1000）。
- 对稳定性有要求且数据基本有序。
二、选择排序：每次选择最小元素
选择排序（Selection Sort）通过每次遍历找到未排序部分的最小元素，并将其放到已排序部分的末尾。
实现原理
- 外层循环：控制已排序部分的边界（0到i-1）。
- 内层循环：在未排序部分（i到n-1）中找到最小元素的索引。
- 交换：将最小元素与未排序部分的第一个元素交换。
代码示例
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;}}swap(arr, i, minIndex);}}
性能分析
- 时间复杂度：O(n²)（无论数据是否有序）。
- 空间复杂度：O(1)。
- 稳定性：不稳定（交换可能改变相等元素的顺序）。
适用场景
- 数据量小且对稳定性无要求。
- 交换操作成本较高时（如对象排序）。
三、插入排序：适合部分有序的数据
插入排序（Insertion Sort）通过构建有序序列，将未排序元素逐个插入到已排序部分的正确位置。
实现原理
- 外层循环：从第二个元素开始遍历（i=1到n-1）。
- 内层循环：将当前元素与已排序部分的元素从后向前比较，找到插入位置。
- 移动与插入：将大于当前元素的元素后移，插入当前元素。
代码示例
public static void insertionSort(int[] arr) {for (int i = 1; i < arr.length; i++) {int key = arr[i];int j = i - 1;while (j >= 0 && arr[j] > key) {arr[j + 1] = arr[j];j--;}arr[j + 1] = key;}}
性能分析
- 时间复杂度：
- 最坏情况：O(n²)（完全逆序）。
- 最好情况：O(n)（已有序）。
- 空间复杂度：O(1)。
- 稳定性：稳定。
适用场景
- 数据量小或部分有序。
- 实时系统（如游戏引擎）中需要逐步排序的场景。
四、归并排序：分治思想的典范
归并排序（Merge Sort）采用分治策略，将数组递归分成两半，分别排序后合并。
实现原理
- 分解：将数组分成左右两半，直到子数组长度为1。
- 合并：将两个有序子数组合并为一个有序数组。
代码示例
public static void mergeSort(int[] arr, int left, int right) {if (left < right) {int mid = left + (right - left) / 2;mergeSort(arr, left, mid);mergeSort(arr, mid + 1, right);merge(arr, left, mid, right);}}private 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++];System.arraycopy(temp, 0, arr, left, temp.length);}
性能分析
- 时间复杂度：O(n log n)（所有情况）。
- 空间复杂度：O(n)（需要额外数组）。
- 稳定性：稳定。
适用场景
- 大规模数据排序（n > 10^5）。
- 链表排序（无需随机访问）。
五、快速排序：平均性能最优
快速排序（Quick Sort）通过选择基准元素（pivot），将数组分为小于和大于基准的两部分，递归排序。
实现原理
- 分区：选择基准元素，将数组分为左右两部分。
- 递归：对左右部分分别递归排序。
代码示例
public static void quickSort(int[] arr, int low, int high) {if (low < high) {int pi = partition(arr, low, high);quickSort(arr, low, pi - 1);quickSort(arr, pi + 1, high);}}private static int partition(int[] arr, int low, int high) {int pivot = arr[high];int i = low - 1;for (int j = low; j < high; j++) {if (arr[j] < pivot) {i++;swap(arr, i, j);}}swap(arr, i + 1, high);return i + 1;}
性能分析
- 时间复杂度：
- 平均情况：O(n log n)。
- 最坏情况：O(n²)（数组已有序且基准选择不当）。
- 空间复杂度：O(log n)（递归栈）。
- 稳定性：不稳定。
适用场景
- 大规模数据排序（n > 10^5）。
- 对平均性能要求高且数据分布随机。
六、堆排序：利用完全二叉树
堆排序（Heap Sort）通过构建最大堆（或最小堆），每次取出堆顶元素并调整堆。
实现原理
- 建堆：将无序数组构建为最大堆。
- 排序：重复取出堆顶元素，放到数组末尾，并调整剩余堆。
代码示例
public static void heapSort(int[] arr) {int n = arr.length;// 建堆for (int i = n / 2 - 1; i >= 0; i--) {heapify(arr, n, i);}// 排序for (int i = n - 1; i > 0; i--) {swap(arr, 0, i);heapify(arr, i, 0);}}private static void heapify(int[] arr, int n, int i) {int largest = i;int left = 2 * i + 1;int right = 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);}}
性能分析
- 时间复杂度：O(n log n)（所有情况）。
- 空间复杂度：O(1)（原地排序）。
- 稳定性：不稳定。
适用场景
- 大规模数据排序且要求原地排序。
- 对最坏情况性能有严格要求。
七、希尔排序：插入排序的优化
希尔排序（Shell Sort）是插入排序的改进版，通过分组插入排序逐步缩小间隔。
实现原理
- 选择间隔：初始间隔为数组长度的一半，逐步减半至1。
- 分组插入：对每个间隔的子数组进行插入排序。
代码示例
public static void shellSort(int[] arr) {int n = arr.length;for (int gap = n / 2; gap > 0; gap /= 2) {for (int i = gap; i < n; i++) {int key = arr[i];int j = i;while (j >= gap && arr[j - gap] > key) {arr[j] = arr[j - gap];j -= gap;}arr[j] = key;}}}
性能分析
- 时间复杂度：
- 最好情况：O(n log n)。
- 最坏情况：O(n²)（取决于间隔序列）。
- 空间复杂度：O(1)。
- 稳定性：不稳定。
适用场景
- 中等规模数据排序（n < 10^5）。
- 对内存使用有限制的场景。
八、计数排序：非比较排序的代表
计数排序（Counting Sort）是一种非比较排序，通过统计元素出现次数实现排序。
实现原理
- 统计频率：遍历数组，统计每个元素的出现次数。
- 计算前缀和：将频率数组转换为位置数组。
- 反向填充：根据位置数组将元素放回原数组。
代码示例
public static void countingSort(int[] arr) {int max = Arrays.stream(arr).max().orElse(0);int[] count = new int[max + 1];for (int num : arr) {count[num]++;}for (int i = 1; i < count.length; i++) {count[i] += count[i - 1];}int[] output = new int[arr.length];for (int i = arr.length - 1; i >= 0; i--) {output[count[arr[i]] - 1] = arr[i];count[arr[i]]--;}System.arraycopy(output, 0, arr, 0, arr.length);}
性能分析
- 时间复杂度：O(n + k)（k为数据范围）。
- 空间复杂度：O(n + k)。
- 稳定性：稳定。
适用场景
- 数据范围小（k < 10^3）且分布均匀。
- 整数排序且对稳定性有要求。
总结：如何选择排序算法？
-
数据规模：
- 小规模（n < 1000）：插入排序、选择排序。
- 中等规模（n < 10^5）：快速排序、归并排序。
- 大规模（n > 10^5）：堆排序、归并排序（外部排序）。
-
数据特性：
- 部分有序：插入排序、希尔排序。
- 数据范围小：计数排序。
- 对稳定性有要求：归并排序、计数排序。
-
性能要求：
- 平均性能：快速排序。
- 最坏性能：堆排序、归并排序。
通过合理选择排序算法，可以显著提升代码效率。在实际开发中，Java的Arrays.sort()方法已对不同数据规模和类型进行了优化，但在特定场景下，手动实现排序算法仍具有重要价值。