快速排序 平均时间复杂度为 O(n log n)，最坏为 O(n^2)

  • 📌 快速排序步骤（以升序为例）
    • 使用两个指针：left 和 right
    • 选定一个基准值 pivot
    • left 从左往右找大于等于 pivot的元素
    • right 从右往左找小于等于 pivot的元素
    • → 交换它们
    • 重复直到 left >= right，此时返回 right（注意不是 left）

示例演示:

  • 初始数组 [6, 3, 1, 5, 2, 4] pivot = 6
  • 第1次递归
    • 第 1 轮：
      • i 从 -1 ➜ 0（arr[0]=6 ≥ pivot）✅ 停止
      • j 从 6 ➜ 5（arr[5]=4 ≤ pivot）✅ 停止
      • i < j 成立，交换 index=0 和 5 → 6 ↔ 4
      • 数组变为：[4, 3, 1, 5, 2, 6]
    • 第 2 轮：
      • i 从 1 ➜ i=5 ➜ arr[5]=6 == pivot ✅ 停止
      • j 从 5 ➜ 4（arr[4]=2 ≤ 6）✅ 停止
      • i=5 >= j=4，循环结束，返回 j=4
    • 结果: [4, 3, 1, 5, 2 | 6] pivotIndex = 4
  • 第2次递归：略

代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
private static int hoarePartition(int[] arr, int left, int right) {
    int pivot = arr[left];  // Hoare 方法通常选最左边为 pivot
    int i = left - 1;
    int j = right + 1;

    while (true) {
        // 从左往右找 >= pivot 的元素
        do {
            i++;
        } while (arr[i] < pivot);

        // 从右往左找 <= pivot 的元素
        do {
            j--;
        } while (arr[j] > pivot);

        // 如果指针交错，分区完成
        if (i >= j) {
            return j; // 注意这里返回的是 j
        }

        // 交换 arr[i] 和 arr[j]
        swap(arr, i, j);
    }
}

private static void quickSort(int[] arr, int left, int right) {
    if (left < right) {
        int pivotIndex = hoarePartition(arr, left, right);
        quickSort(arr, left, pivotIndex);     // 注意包含 pivotIndex
        quickSort(arr, pivotIndex + 1, right);
    }
}

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²)

冒泡排序的核心思想是： 重复地比较相邻的两个元素，如果它们的顺序错误就交换它们的位置。

  • 📊 示例过程演示
    以数组 [5, 3, 4, 1, 2] 为例，执行冒泡排序的过程如下：

    • 第 1 趟（把最大的冒到最后）：

      • 比较 5 和 3 → 交换 → [3, 5, 4, 1, 2]
      • 比较 5 和 4 → 交换 → [3, 4, 5, 1, 2]
      • 比较 5 和 1 → 交换 → [3, 4, 1, 5, 2]
      • 比较 5 和 2 → 交换 → [3, 4, 1, 2, 5] ✅

    • 第 2 趟：

      • 比较 3 和 4 → 不换
      • 比较 4 和 1 → 交换 → [3, 1, 4, 2, 5]
      • 比较 4 和 2 → 交换 → [3, 1, 2, 4, 5] ✅
    • 第 3 趟：
      • 比较 3 和 1 → 交换 → [1, 3, 2, 4, 5]
      • 比较 3 和 2 → 交换 → [1, 2, 3, 4, 5] ✅

        代码实现

        1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        12
        13
        14
        15
        16
        17
        18
        19
        public static void bubbleSort(int[] arr) {
            int n = arr.length;
            boolean swapped;
            
            for (int i = 0; i < n - 1; i++) {
                swapped = false; // 本轮是否有交换
                for (int j = 0; j < n - 1 - i; j++) { // 每次都可以少比较1个
                    if (arr[j] > arr[j + 1]) {
                        // 交换 arr[j] 和 arr[j+1]
                        int temp = arr[j];
                        arr[j] = arr[j + 1];
                        arr[j + 1] = temp;
                        swapped = true;
                    }
                }
                // 如果某一轮没有发生交换，说明已经有序，可以提前结束
                if (!swapped) break;
            }
        }

选择排序 平均时间复杂度为 O(n²)，最坏为 O(n²)

每一轮从未排序部分中找出最小（或最大）的元素，放到已排序部分的末尾。

  • 📊 示例演示
    对数组 [5, 3, 4, 1, 2] 使用选择排序的过程如下：
    • 第 1 趟（从索引 0 开始）：
      • 找出最小值是 1，索引为 3
      • 交换 arr[0] 和 arr[3]
    • 第 2 趟（从索引 1 开始）：
      • 找出最小值是 2，索引为 4
      • 交换 arr[1] 和 arr[4]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static void selectionSort(int[] arr) {
    int n = arr.length;
    
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i; // 假设当前位置是最小值
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j; // 找到更小的值
            }
        }
        // 交换当前位置和最小值的位置
        if (minIndex != i) {
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
}