Java排序算法全解析：8种经典实现与性能优化指南

2025年12月17日 互联网

Java排序算法全解析：8种经典实现与性能优化指南

在Java开发中，排序算法是数据处理的基础工具，无论是数据库查询优化、日志分析还是算法竞赛，掌握不同排序算法的特性与实现至关重要。本文将以“干饭”般的热情，系统梳理Java中8种经典排序算法的实现细节、时间复杂度及适用场景，并提供代码示例与性能优化建议。

一、排序算法分类与核心指标

排序算法的核心指标包括时间复杂度、空间复杂度、稳定性及适用场景。根据实现原理，排序算法可分为比较类排序（如冒泡排序、快速排序）和非比较类排序（如计数排序、基数排序）。开发者需根据数据规模、数据分布及内存限制选择合适算法。

1.1 时间复杂度对比

算法 平均时间复杂度 最坏时间复杂度 空间复杂度 稳定性
冒泡排序 O(n²) O(n²) O(1) 稳定
选择排序 O(n²) O(n²) O(1) 不稳定
插入排序 O(n²) O(n²) O(1) 稳定
希尔排序 O(n log n) O(n²) O(1) 不稳定
归并排序 O(n log n) O(n log n) O(n) 稳定
快速排序 O(n log n) O(n²) O(log n) 不稳定
堆排序 O(n log n) O(n log n) O(1) 不稳定
计数排序 O(n + k) O(n + k) O(n + k) 稳定

二、8种排序算法实现详解

2.1 冒泡排序（Bubble Sort）

原理：重复遍历数组，比较相邻元素并交换，将最大元素“冒泡”至末尾。
代码示例：

  1. public static void bubbleSort(int[] arr) {
  2.     int n = arr.length;
  3.     for (int i = 0; i < n - 1; i++) {
  4.         for (int j = 0; j < n - i - 1; j++) {
  5.             if (arr[j] > arr[j + 1]) {
  6.                 int temp = arr[j];
  7.                 arr[j] = arr[j + 1];
  8.                 arr[j + 1] = temp;
  9.             }
  10.         }
  11.     }
  12. }

优化点：增加标志位，若某轮未发生交换则提前终止。

2.2 选择排序（Selection Sort）

原理：每次选择未排序部分的最小元素，与当前位置交换。
代码示例：

  1. public static void selectionSort(int[] arr) {
  2.     int n = arr.length;
  3.     for (int i = 0; i < n - 1; i++) {
  4.         int minIdx = i;
  5.         for (int j = i + 1; j < n; j++) {
  6.             if (arr[j] < arr[minIdx]) {
  7.                 minIdx = j;
  8.             }
  9.         }
  10.         int temp = arr[minIdx];
  11.         arr[minIdx] = arr[i];
  12.         arr[i] = temp;
  13.     }
  14. }

特点：交换次数少，但不稳定。

2.3 插入排序（Insertion Sort）

原理：将未排序元素插入已排序部分的正确位置。
代码示例：

  1. public static void insertionSort(int[] arr) {
  2.     int n = arr.length;
  3.     for (int i = 1; i < n; i++) {
  4.         int key = arr[i];
  5.         int j = i - 1;
  6.         while (j >= 0 && arr[j] > key) {
  7.             arr[j + 1] = arr[j];
  8.             j--;
  9.         }
  10.         arr[j + 1] = key;
  11.     }
  12. }

适用场景：小规模数据或基本有序的数据。

2.4 希尔排序（Shell Sort）

原理：分组插入排序，通过缩小增量逐步排序。
代码示例：

  1. public static void shellSort(int[] arr) {
  2.     int n = arr.length;
  3.     for (int gap = n / 2; gap > 0; gap /= 2) {
  4.         for (int i = gap; i < n; i++) {
  5.             int temp = arr[i];
  6.             int j;
  7.             for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
  8.                 arr[j] = arr[j - gap];
  9.             }
  10.             arr[j] = temp;
  11.         }
  12.     }
  13. }

性能：优于插入排序，但稳定性较差。

2.5 归并排序（Merge Sort）

原理：分治思想，递归拆分数组后合并有序子数组。
代码示例：

  1. public static void mergeSort(int[] arr, int left, int right) {
  2.     if (left < right) {
  3.         int mid = left + (right - left) / 2;
  4.         mergeSort(arr, left, mid);
  5.         mergeSort(arr, mid + 1, right);
  6.         merge(arr, left, mid, right);
  7.     }
  8. }
  10. private static void merge(int[] arr, int left, int mid, int right) {
  11.     int[] temp = new int[right - left + 1];
  12.     int i = left, j = mid + 1, k = 0;
  13.     while (i <= mid && j <= right) {
  14.         if (arr[i] <= arr[j]) {
  15.             temp[k++] = arr[i++];
  16.         } else {
  17.             temp[k++] = arr[j++];
  18.         }
  19.     }
  20.     while (i <= mid) temp[k++] = arr[i++];
  21.     while (j <= right) temp[k++] = arr[j++];
  22.     System.arraycopy(temp, 0, arr, left, temp.length);
  23. }

优势：稳定且适合大规模数据。

2.6 快速排序（Quick Sort）

原理：分治思想，选择基准值将数组分为左右两部分。
代码示例：

  1. public static void quickSort(int[] arr, int low, int high) {
  2.     if (low < high) {
  3.         int pi = partition(arr, low, high);
  4.         quickSort(arr, low, pi - 1);
  5.         quickSort(arr, pi + 1, high);
  6.     }
  7. }
  9. private static int partition(int[] arr, int low, int high) {
  10.     int pivot = arr[high];
  11.     int i = low - 1;
  12.     for (int j = low; j < high; j++) {
  13.         if (arr[j] < pivot) {
  14.             i++;
  15.             int temp = arr[i];
  16.             arr[i] = arr[j];
  17.             arr[j] = temp;
  18.         }
  19.     }
  20.     int temp = arr[i + 1];
  21.     arr[i + 1] = arr[high];
  22.     arr[high] = temp;
  23.     return i + 1;
  24. }

优化点：随机选择基准值避免最坏情况。

2.7 堆排序（Heap Sort）

原理：构建最大堆，逐步将堆顶元素与末尾交换。
代码示例：

  1. public static void heapSort(int[] arr) {
  2.     int n = arr.length;
  3.     for (int i = n / 2 - 1; i >= 0; i--) {
  4.         heapify(arr, n, i);
  5.     }
  6.     for (int i = n - 1; i > 0; i--) {
  7.         int temp = arr[0];
  8.         arr[0] = arr[i];
  9.         arr[i] = temp;
  10.         heapify(arr, i, 0);
  11.     }
  12. }
  14. private static void heapify(int[] arr, int n, int i) {
  15.     int largest = i;
  16.     int left = 2 * i + 1;
  17.     int right = 2 * i + 2;
  18.     if (left < n && arr[left] > arr[largest]) largest = left;
  19.     if (right < n && arr[right] > arr[largest]) largest = right;
  20.     if (largest != i) {
  21.         int temp = arr[i];
  22.         arr[i] = arr[largest];
  23.         arr[largest] = temp;
  24.         heapify(arr, n, largest);
  25.     }
  26. }

特点：原地排序，适合大数据量。

2.8 计数排序（Counting Sort）

原理：统计元素出现次数，按顺序输出。
代码示例：

  1. public static void countingSort(int[] arr) {
  2.     int max = Arrays.stream(arr).max().orElse(0);
  3.     int[] count = new int[max + 1];
  4.     for (int num : arr) count[num]++;
  5.     int idx = 0;
  6.     for (int i = 0; i < count.length; i++) {
  7.         while (count[i] > 0) {
  8.             arr[idx++] = i;
  9.             count[i]--;
  10.         }
  11.     }
  12. }

限制：仅适用于整数且范围较小的数据。

三、性能优化与最佳实践

  1. 小规模数据：优先选择插入排序或选择排序，减少递归开销。
  2. 大规模数据：快速排序或归并排序，结合随机化基准值避免最坏情况。
  3. 内存受限：堆排序或希尔排序，降低空间复杂度。
  4. 稳定性需求：归并排序或计数排序，确保相等元素顺序不变。
  5. 数据分布：若数据范围已知且较小，计数排序效率极高。

四、总结与展望

掌握8种排序算法的实现原理与性能特性，是Java开发者提升数据处理能力的关键。实际开发中，需结合数据规模、内存限制及稳定性需求灵活选择算法。例如，在日志分析场景中，归并排序的稳定性可确保时间戳顺序；在内存敏感的嵌入式系统中，堆排序的原地特性更具优势。未来，随着数据规模持续增长，结合多线程或分布式排序框架（如MapReduce）将成为优化方向。

最新文章
热门标签