十大排序算法深度解析与Java实现指南

2025年12月16日 互联网

十大排序算法深度解析与Java实现指南

排序算法是计算机科学中的基础技术，直接影响数据处理效率。本文系统梳理十大经典排序算法的原理、时间复杂度及Java实现，结合代码示例与优化建议，为开发者提供实用指南。

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

排序算法可根据实现方式分为比较类与非比较类，核心评价指标包括时间复杂度（最好/最坏/平均）、空间复杂度及稳定性。稳定性指相等元素的相对顺序是否保持，如工资表排序时需保留入职时间顺序。

1.1 比较类排序

依赖元素间比较操作，时间复杂度下限为O(nlogn)。

1.2 非比较类排序

通过计数、桶分配或位运算实现，突破O(nlogn)限制但需特定条件。

二、十大排序算法详解与Java实现

2.1 冒泡排序（Bubble Sort）

原理：重复遍历数组，相邻元素两两比较并交换，每轮将最大元素”冒泡”至末尾。
时间复杂度：O(n²)（最坏/平均），O(n)（最好，已排序时）
空间复杂度：O(1)
稳定性：稳定
Java实现：

  1. public static void bubbleSort(int[] arr) {
  2.     boolean swapped;
  3.     for (int i = 0; i < arr.length - 1; i++) {
  4.         swapped = false;
  5.         for (int j = 0; j < arr.length - 1 - i; j++) {
  6.             if (arr[j] > arr[j + 1]) {
  7.                 swap(arr, j, j + 1);
  8.                 swapped = true;
  9.             }
  10.         }
  11.         if (!swapped) break; // 提前终止优化
  12.     }
  13. }

优化建议：添加swapped标志位，若某轮无交换则提前终止。

2.2 选择排序（Selection Sort）

原理：每轮选择未排序部分的最小元素，与未排序部分首元素交换。
时间复杂度：O(n²)（所有情况）
空间复杂度：O(1)
稳定性：不稳定（交换可能破坏顺序）
Java实现：

  1. public static void selectionSort(int[] arr) {
  2.     for (int i = 0; i < arr.length - 1; i++) {
  3.         int minIdx = i;
  4.         for (int j = i + 1; j < arr.length; j++) {
  5.             if (arr[j] < arr[minIdx]) minIdx = j;
  6.         }
  7.         swap(arr, i, minIdx);
  8.     }
  9. }

适用场景：数据量小或交换成本高的场景（如链表排序）。

2.3 插入排序（Insertion Sort）

原理：构建有序序列，逐个将未排序元素插入到已排序部分的正确位置。
时间复杂度：O(n²)（最坏/平均），O(n)（最好，已排序时）
空间复杂度：O(1)
稳定性：稳定
Java实现：

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

优化建议：对近乎有序的数据效率高，常用于分治算法的子问题处理。

2.4 希尔排序（Shell Sort）

原理：插入排序的改进版，通过分组间隔（gap）逐步缩小至1，实现不完全插入排序。
时间复杂度：取决于gap序列，最优可达O(n^(3/2))
空间复杂度：O(1)
稳定性：不稳定
Java实现：

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

关键点：gap序列选择影响性能，常见序列有Knuth序列（3k+1）。

2.5 归并排序（Merge Sort）

原理：分治思想，将数组递归分为两半，分别排序后合并。
时间复杂度：O(nlogn)（所有情况）
空间复杂度：O(n)（需额外数组）
稳定性：稳定
Java实现：

  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]) temp[k++] = arr[i++];
  15.         else temp[k++] = arr[j++];
  16.     }
  17.     while (i <= mid) temp[k++] = arr[i++];
  18.     while (j <= right) temp[k++] = arr[j++];
  19.     System.arraycopy(temp, 0, arr, left, temp.length);
  20. }

优化建议：对小规模子数组切换为插入排序，减少递归开销。

2.6 快速排序（Quick Sort）

原理：分治思想，选择基准（pivot）将数组分为左右两部分，递归排序。
时间复杂度：O(nlogn)（平均），O(n²)（最坏，如已排序数组）
空间复杂度：O(logn)（递归栈）
稳定性：不稳定
Java实现：

  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.             swap(arr, i, j);
  16.         }
  17.     }
  18.     swap(arr, i + 1, high);
  19.     return i + 1;
  20. }

优化建议：

  • 三数取中法选择基准，避免最坏情况。
  • 对小规模子数组切换为插入排序。

2.7 堆排序（Heap Sort）

原理：利用堆数据结构，将无序数组构建为最大堆，依次取出堆顶元素。
时间复杂度：O(nlogn)（所有情况）
空间复杂度：O(1)（原地排序）
稳定性：不稳定
Java实现：

  1. public static void heapSort(int[] arr) {
  2.     int n = arr.length;
  3.     // 构建最大堆
  4.     for (int i = n / 2 - 1; i >= 0; i--) {
  5.         heapify(arr, n, i);
  6.     }
  7.     // 逐个提取元素
  8.     for (int i = n - 1; i > 0; i--) {
  9.         swap(arr, 0, i);
  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.         swap(arr, i, largest);
  22.         heapify(arr, n, largest);
  23.     }
  24. }

关键点：堆排序适合大数据量且内存受限的场景。

2.8 计数排序（Counting Sort）

原理：非比较排序，统计每个元素的出现次数，按计数重建有序数组。
时间复杂度：O(n+k)（k为数据范围）
空间复杂度：O(n+k)
稳定性：稳定
Java实现：

  1. public static void countingSort(int[] arr) {
  2.     int max = Arrays.stream(arr).max().getAsInt();
  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. }

适用场景：整数且范围较小的数据（如年龄排序）。

2.9 桶排序（Bucket Sort）

原理：将数据分到有限数量的桶中，对每个桶单独排序后合并。
时间复杂度：平均O(n+k)，最坏O(n²)（桶内排序为插入排序时）
空间复杂度：O(n+k)
稳定性：稳定
Java实现：

  1. public static void bucketSort(int[] arr, int bucketSize) {
  2.     if (arr.length == 0) return;
  3.     int max = Arrays.stream(arr).max().getAsInt();
  4.     int min = Arrays.stream(arr).min().getAsInt();
  5.     int bucketCount = (max - min) / bucketSize + 1;
  6.     ArrayList<Integer>[] buckets = new ArrayList[bucketCount];
  7.     for (int i = 0; i < buckets.length; i++) {
  8.         buckets[i] = new ArrayList<>();
  9.     }
  10.     for (int num : arr) {
  11.         buckets[(num - min) / bucketSize].add(num);
  12.     }
  13.     int idx = 0;
  14.     for (ArrayList<Integer> bucket : buckets) {
  15.         Collections.sort(bucket); // 桶内排序
  16.         for (int num : bucket) {
  17.             arr[idx++] = num;
  18.         }
  19.     }
  20. }

优化建议：根据数据分布动态调整桶数量。

2.10 基数排序（Radix Sort）

原理：按位数从低位到高位依次排序，使用计数排序作为子过程。
时间复杂度：O(d(n+k))（d为最大位数）
空间复杂度：O(n+k)
稳定性：稳定
*Java实现：

  1. public static void radixSort(int[] arr) {
  2.     int max = Arrays.stream(arr).max().getAsInt();
  3.     for (int exp = 1; max / exp > 0; exp *= 10) {
  4.         countingSortByDigit(arr, exp);
  5.     }
  6. }
  8. private static void countingSortByDigit(int[] arr, int exp) {
  9.     int[] output = new int[arr.length];
  10.     int[] count = new int[10];
  11.     for (int num : arr) count[(num / exp) % 10]++;
  12.     for (int i = 1; i < 10; i++) count[i] += count[i - 1];
  13.     for (int i = arr.length - 1; i >= 0; i--) {
  14.         output[count[(arr[i] / exp) % 10] - 1] = arr[i];
  15.         count[(arr[i] / exp) % 10]--;
  16.     }
  17.     System.arraycopy(output, 0, arr, 0, arr.length);
  18. }

适用场景：整数或固定长度字符串排序。

三、算法选择与性能优化建议

  1. 小规模数据：优先选择插入排序或选择排序，代码简洁且常数因子小。
  2. 大规模数据：快速排序或归并排序，需注意快速排序的最坏情况。
  3. 内存受限：堆排序或原地归并排序变种。
  4. 特定数据范围：计数排序、桶排序或基数排序。
  5. 稳定性要求：归并排序、计数排序或基数排序。

四、总结

十大排序算法各有优劣，开发者需根据数据规模、范围、稳定性要求及内存限制综合选择。理解算法原理与实现细节，结合实际场景优化，是提升数据处理效率的关键。建议通过LeetCode等平台实践排序算法变种问题，深化理解。

最新文章