有关于排序算法

发表于 更新于 分类于 本文字数： 2.1k 阅读时长 ≈ 8 分钟

本文围绕提供的 Java 排序算法代码，按「基础排序算法」「进阶排序算法」「快速排序算法」三大类，深入剖析每种算法的核心思想、代码逻辑细节、关键设计亮点、时间复杂度、空间复杂度及适用场景。所有讲解均紧密结合代码实现，让理论与实践深度融合。

基础排序算法

基础排序算法通常是入门级实现，核心逻辑简单直观，时间复杂度多为 $O(n^2)$，适用于小规模数据排序。本节包含冒泡排序、选择排序、插入排序及希尔排序（插入排序的优化版）。

冒泡排序

核心思想

通过相邻元素的两两比较与交换，将最大（或最小）的元素逐步“冒泡”到数组的末尾。每一轮遍历都会确定一个未排序区间的最值元素，遍历 n-1 轮后完成排序。代码中加入了 sorted 标志位优化，避免已排序数组的无效遍历。

代码逻辑拆解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public void bubbleSort(int[] nums) {
    int n = nums.length;

    for (int i = 0; i < n - 1; i++) {
        boolean sorted = true;
        for (int j = 0; j < n - i - 1; j++) {
            if (nums[j] > nums[j + 1]) {
                swap(nums, j, j + 1);
                sorted = false;
            }
        }
        if (sorted) break;
    }
}

private void swap(int[] a, int i, int j) {
    int t = a[i];
    a[i] = a[j];
    a[j] = t;
}
  • 外层循环控制轮次
  • 内层循环比较相邻元素
  • sorted 标志优化：若无交换则提前结束

复杂度与适用场景

  • 时间复杂度：最好 $O(n)$，最坏 $O(n²)$
  • 空间复杂度：$O(1)$
  • 适用场景：小规模数据、接近有序的数组

选择排序

核心思想

每轮从未排序区间找到最小元素，与未排序区间第一个元素交换，逐步扩大已排序区间。

代码逻辑拆解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public void selectionSort(int[] nums) {
    for (int i = 0; i < nums.length; i++) {
        int leftMin = findMin(nums, i);
        swap(nums, i, leftMin);
    }
}

private int findMin(int[] nums, int L) {
    int minIndex = L;
    for (int i = L; i < nums.length; i++) {
        if (nums[i] < nums[minIndex]) {
            minIndex = i;
        }
    }
    return minIndex;
}
  • 每轮只交换一次，减少交换次数

复杂度与适用场景

  • 时间复杂度：O(n²)
  • 空间复杂度：O(1)
  • 适用场景：小规模数据、交换代价高的场景

插入排序

核心思想

将数组分为已排序和未排序区间，依次将未排序元素插入到已排序区间的正确位置。

代码逻辑拆解

1
2
3
4
5
6
7
8
9
10
11
public void insertionSort(int[] nums) {
    for (int i = 1; i < nums.length; i++) {
        int key = nums[i];
        int j = i - 1;
        while (j >= 0 && nums[j] > key) {
            nums[j + 1] = nums[j];
            j--;
        }
        nums[j + 1] = key;
    }
}
  • 关键字 key 保存当前元素
  • 元素后移腾出插入位置

复杂度与适用场景

  • 时间复杂度：最好 O(n)，最坏 O(n²)
  • 空间复杂度：O(1)
  • 适用场景：小规模、接近有序的数据

希尔排序

核心思想

插入排序的优化版，通过递减步长分组插入排序，使数组逐步接近有序。

代码逻辑拆解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static void shellSort(int[] arr) {
    if (arr == null || arr.length <= 1) return;
    int n = arr.length;
    for (int gap = n / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < n; i++) {
            int current = arr[i];
            int j = i - gap;
            while (j >= 0 && arr[j] > current) {
                arr[j + gap] = arr[j];
                j -= gap;
            }
            arr[j + gap] = current;
        }
    }
}
  • 步长 gap 初始为 n/2，每次减半
  • 分组执行插入排序

复杂度与适用场景

  • 时间复杂度：O(n^(3/2))
  • 空间复杂度：O(1)
  • 适用场景：中大规模数据、空间敏感场景

进阶排序算法

归并排序

核心思想

分治思想：将数组递归拆分为两个子数组，排序后再合并。

代码逻辑拆解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public static void mergeSort(int[] arr) {
    if (arr == null || arr.length <= 1) return;
    int[] temp = new int[arr.length];
    split(arr, 0, arr.length - 1, temp);
}

private static void split(int[] arr, int left, int right, int[] temp) {
    if (left >= right) return;
    int mid = left + (right - left) / 2;
    split(arr, left, mid, temp);
    split(arr, mid + 1, right, temp);
    merge(arr, left, mid, right, temp);
}

private static void merge(int[] arr, int left, int mid, int right, int[] temp) {
    int i = left, j = mid + 1, k = left;
    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, left, arr, left, right - left + 1);
}
  • 临时数组 temp 避免重复创建
  • 合并过程保证稳定性

复杂度与适用场景

  • 时间复杂度：O(n log n)
  • 空间复杂度：O(n)
  • 适用场景：大规模数据、要求稳定排序

快速排序

核心思想

选基准、分区间，递归排序左右子区间。

代码逻辑拆解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public void quickSort(int[] arr) {
    sortHelper(arr, 0, arr.length - 1);
}

private void sortHelper(int[] arr, int L, int R) {
    if (L >= R) return;
    int pivot = partition(arr, L, R);
    sortHelper(arr, L, pivot);
    sortHelper(arr, pivot + 1, R);
}

private int partition(int[] arr, int L, int R) {
    int pivot = arr[L];
    int i = L - 1, j = R + 1;
    while (i < j) {
        do { i++; } while (arr[i] < pivot);
        do { j--; } while (arr[j] > pivot);
        if (i >= j) break;
        swap(arr, i, j);
    }
    return j;
}
  • 双指针分区
  • 基准选择可优化（如三数取中）

复杂度与适用场景

  • 时间复杂度：平均 O(n log n)，最坏 O(n²)
  • 空间复杂度：O(log n)
  • 适用场景：大规模数据、实际效率高

堆排序

核心思想

构建大顶堆，交换堆顶与堆尾，调整堆。

代码逻辑拆解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public static void heapSort(int[] arr) {
    if (arr == null || arr.length <= 1) return;
    int n = arr.length;
    for (int i = n / 2 - 1; i >= 0; i--) siftDown(arr, i, n);
    for (int end = n - 1; end > 0; end--) {
        swap(arr, 0, end);
        siftDown(arr, 0, end);
    }
}

private static void siftDown(int[] arr, int index, int size) {
    int largest = index;
    while (true) {
        int left = 2 * index + 1;
        int right = left + 1;
        if (left < size && arr[left] > arr[largest]) largest = left;
        if (right < size && arr[right] > arr[largest]) largest = right;
        if (largest == index) break;
        swap(arr, index, largest);
        index = largest;
    }
}
  • 从最后一个非叶子节点开始构建堆
  • 下沉调整保证堆性质

复杂度与适用场景

  • 时间复杂度：O(n log n)
  • 空间复杂度：O(1)
  • 适用场景：大规模数据、空间敏感、Top K 问题

线性时间排序算法

计数排序

核心思想

统计元素出现次数，根据计数数组重构有序序列。

不稳定版实现

1
2
3
4
5
6
7
8
9
10
11
public void countingSort_unStable(int[] nums) {
    if (nums == null || nums.length <= 1) return;
    int max = nums[0];
    for (int num : nums) max = Math.max(max, num);
    int[] count = new int[max + 1];
    for (int num : nums) count[num]++;
    int pos = 0;
    for (int i = 0; i <= max; i++) {
        while (count[i]-- > 0) nums[pos++] = i;
    }
}

稳定版实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public void countingSort_stable(int[] nums) {
    if (nums == null || nums.length <= 1) return;
    int max = nums[0];
    for (int num : nums) max = Math.max(max, num);
    int[] count = new int[max + 1];
    for (int num : nums) count[num]++;
    for (int i = 1; i <= max; i++) count[i] += count[i - 1];
    int[] output = new int[nums.length];
    for (int i = nums.length - 1; i >= 0; i--) {
        int value = nums[i];
        output[count[value] - 1] = value;
        count[value]--;
    }
    System.arraycopy(output, 0, nums, 0, nums.length);
}

复杂度与适用场景

  • 时间复杂度：O(n + max)
  • 空间复杂度：O(n + max)
  • 适用场景：非负整数、取值范围小、需稳定排序

基数排序

核心思想

按位（个位、十位…）进行多轮桶排序。

代码逻辑拆解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public void radixSort(int[] arr) {
    if (arr == null || arr.length <= 1) return;
    List<Integer>[] buckets = new ArrayList[10];
    for (int i = 0; i < 10; i++) buckets[i] = new ArrayList<>();
    int divisor = 1;
    boolean hasMoreDigit = true;
    while (hasMoreDigit) {
        hasMoreDigit = false;
        for (int num : arr) {
            int digit = (num / divisor) % 10;
            buckets[digit].add(num);
            if (num / divisor > 0) hasMoreDigit = true;
        }
        int idx = 0;
        for (int i = 0; i < 10; i++) {
            for (int num : buckets[i]) arr[idx++] = num;
            buckets[i].clear();
        }
        divisor *= 10;
    }
}
  • 低位优先（LSD）
  • 使用计数排序作为稳定子排序

复杂度与适用场景

  • 时间复杂度：O(d × (n + r))
  • 空间复杂度：O(n + r)
  • 适用场景：非负整数、位数较少的大规模数据

总结：各排序算法核心特性对比

排序算法 时间复杂度(平均) 空间复杂度 稳定性 核心优势 适用场景
冒泡排序 O(n²) O(1) 稳定 实现简单 小规模、接近有序
选择排序 O(n²) O(1) 不稳定 交换次数少 小规模、交换代价高
插入排序 O(n²) O(1) 稳定 接近有序时高效 小规模、动态数据
希尔排序 O(n^(3/2)) O(1) 不稳定 优于基础O(n²) 中大规模数据
归并排序 O(n log n) O(n) 稳定 效率稳定 大规模、需稳定
快速排序 O(n log n) O(log n) 不稳定 原地排序、实际快 大规模、无稳定性要求
堆排序 O(n log n) O(1) 不稳定 原地、可获最值 大规模、空间敏感
计数排序 O(n + max) O(n + max) 稳定 线性时间 非负整数、范围小
基数排序 O(d×(n+r)) O(n+r) 稳定 线性时间 非负整数、位数少