int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;

原数组：[5, 3, 8, 1, 2]

=== 第一轮：把最大的冒泡到最后 ===
比较 5 和 3：5 > 3，交换 → [3, 5, 8, 1, 2]
比较 5 和 8：5 < 8，不动 → [3, 5, 8, 1, 2]
比较 8 和 1：8 > 1，交换 → [3, 5, 1, 8, 2]
比较 8 和 2：8 > 2，交换 → [3, 5, 1, 2, 8]
第一轮结束，8到了最后面 ✓

=== 第二轮：把第二大的冒泡到倒数第二 ===
比较 3 和 5：不动
比较 5 和 1：交换 → [3, 1, 5, 2, 8]
比较 5 和 2：交换 → [3, 1, 2, 5, 8]
（不用比较5和8了，8已经在正确位置）
第二轮结束，5到了倒数第二 ✓

=== 第三轮 ===
比较 3 和 1：交换 → [1, 3, 2, 5, 8]
比较 3 和 2：交换 → [1, 2, 3, 5, 8]
第三轮结束，3就位 ✓

=== 第四轮 ===
比较 1 和 2：不动
第四轮结束，全部有序 ✓

结果：[1, 2, 3, 5, 8]

代码

void bubbleSort(int *nums, int n) {
    for (int i = 0; i < n - 1; i++) {
        int swapped = 0;
        for (int j = 0; j < n - 1 - i; j++) {
            if (nums[j] > nums[j + 1]) {
                int temp = nums[j];
                nums[j] = nums[j + 1];
                nums[j + 1] = temp;
                swapped = 1;
            }
        }
        if (!swapped) break;
    }
}

特征

• 时间复杂度：O(n²)
• 稳定：相等元素不会交换（条件是 >，不是 >=），相对顺序不变
• 原地排序：不需要额外数组

三、选择排序

核心思想

每轮从未排序部分中找到最小元素，放到已排序部分的末尾。

思路

1. 外层循环 i 从 0 到< n-1：i 代表"当前要确定的位置"
2. 内层循环从 i+1 到 <n：找未排序部分中最小元素的索引并记录 minIndex
3. 在外层循环中判断如果 minIndex != i，交换 nums[i] 和 nums[minIndex]

过程示例

原数组：[5, 3, 8, 1, 2]

=== 第一轮：在 [5,3,8,1,2] 中找最小的 ===
最小值是 1（索引3），和第0个位置交换
[1, 3, 8, 5, 2]
位置0已确定 ✓

=== 第二轮：在 [3,8,5,2] 中找最小的 ===
最小值是 2（索引4），和第1个位置交换
[1, 2, 8, 5, 3]
位置0-1已确定 ✓

=== 第三轮：在 [8,5,3] 中找最小的 ===
最小值是 3（索引4），和第2个位置交换
[1, 2, 3, 5, 8]
位置0-2已确定 ✓

=== 第四轮：在 [5,8] 中找最小的 ===
最小值是 5（索引3），已经在正确位置，不用交换
[1, 2, 3, 5, 8]
全部有序 ✓

代码

void selectionSort(int *nums, int n) {
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;                        // 假设当前位置就是最小的
        for (int j = i + 1; j < n; j++) {        // 在后面找更小的
            if (nums[j] < nums[minIndex]) {
                minIndex = j;                    // 记录更小元素的索引
            }
        }
        // 把最小元素和位置i交换
        if (minIndex != i) {                     // 如果最小的不在位置i才交换
            int temp = nums[i];
            nums[i] = nums[minIndex];
            nums[minIndex] = temp;
        }
    }
}

特征

• 时间复杂度：O(n²)（不管数组是否已经有序，都要完整跑完两层循环）
• 不稳定： 交换可能打乱相同元素的相对顺序
• 不稳定的原因：交换会把元素甩到后面，跳过相等的元素，打乱相对顺序。例：[3a, 3b, 1] → 交换3a和1 → [1, 3b, 3a]，3b跑到3a前面了
• 原地排序

四、快速排序

核心思想

选一个基准值（pivot），把数组分成两部分——左边都 ≤ pivot，右边都 > pivot——然后对左右两部分分别递归。

整体结构：两个函数

1. partition 分区函数： 把数组按 pivot 分成左右两部分，返回 pivot 最终的位置的下标(此时pivot的位置在正确位置)
2. quickSort 递归函数：调用 partition分区，然后递归左右两边（每次递归成功确定一个pivot的位置）

（1）partition 分区的思路

本质就是快慢指针做分区：

1. 选最后一个元素 nums[high] 作为 pivot
2. 指针 i = low（"≤ pivot 区域"的右边界，类似 slow）
3. 指针 j 从 low 到 high-1 扫描（类似 fast）：

• • nums[j] <= pivot → 交换 nums[i] 和 nums[j]，i++
  • nums[j] > pivot → 跳过

1. 扫描结束后，交换 nums[i] 和 nums[high]（把 pivot 放到正确位置）
2. 返回 i（pivot 的位置）

分区过程的数组状态：

分区过程中，数组被分成三个区域：

[low ... i-1]  [i ... j-1]  [j ... high-1]  [high]
  ≤ pivot        > pivot      未处理的        pivot

• i 左边（low 到 i-1）：已经确认 ≤ pivot 的元素
• i 到 j-1：已经确认 > pivot 的元素
• j 到 high-1：还没扫描到的元素
• high：pivot 自己

每次 nums[j] <= pivot 时，把 nums[j] 交换到 i 的位置（扩展"≤ pivot"区域），i++。

partition 分区代码

// 对 nums[low..high] 做分区，返回 pivot 最终的位置
int partition(int *nums, int low, int high) {
    int pivot = nums[high];    // 选最后一个元素作为pivot
    int i = low;               // i: 小于等于pivot区域的下一个位置

    for (int j = low; j < high; j++) {    // j 扫描 low 到 high-1
        if (nums[j] <= pivot) {
            // 交换 nums[i] 和 nums[j]
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
            i++;
        }
    }

    // 把 pivot 放到正确位置
    int temp = nums[i];
    nums[i] = nums[high];
    nums[high] = temp;

    return i;    // 返回 pivot 的位置
}

（2）quickSort 递归

分区完成后，pivot 在正确位置，左边都比它小，右边都比它大。对左右两部分别再次递归确定新pivot的位置

时间复杂度

最好和平均情况：O(n log n)。 每次 partition 把数组大致分成两半，递归深度是 log n 层，每层扫描全部 n 个元素。

最坏情况：O(n²)。 当数组已经有序（或逆序），每次选最后一个元素做 pivot，partition 后一边是 n-1 个元素，另一边是 0 个——完全不均匀。递归深度变成 n 层，退化成 O(n²)。

如何避免最坏情况

方法：随机选 pivot。 不固定选最后一个，而是随机选一个元素和最后一个交换，再正常做 partition

quickSort 递归代码

void quickSort(int *nums, int low, int high) {
    if (low >= high) return;

    // 随机选一个元素作为pivot
    int randomIndex = low + rand() % (high - low + 1);
    // 把它和最后一个元素交换
    int temp = nums[randomIndex];
    nums[randomIndex] = nums[high];
    nums[high] = temp;

    int pivotIndex = partition(nums, low, high);
    quickSort(nums, low, pivotIndex - 1);
    quickSort(nums, pivotIndex + 1, high);
}

// 调用：quickSort(nums, 0, numsSize - 1);

特征

• 平均 O(n log n)，最坏 O(n²)（加随机化后极少发生）
• 空间 O(log n)（递归栈，不需要额外数组）
• 不稳定
• 实际速度通常比归并快（原地操作，常数因子小）

五、归并排序

核心思想

把数组从中间分成两半（一直递归分到单个），分别递归排序，然后把两个有序半边合并成一个有序数组。

和快排的区别：快排先分区再递归（分区时做工作），归并先递归再合并（合并时做工作）。

整体结构：两个函数

1. merge 合并函数：把两个相邻的有序区间合并成一个有序区间（ 不是原地操作，需要创建一个临时数组来存合并结果，合并完再复制回原数组）
2. mergeSortHelper 递归拆分函数：递归拆分，然后调用 merge 合并

（1）merge 合并的思路

和题目 21（合并有序链表）、题目 88（合并有序数组）一样——两个指针分别指向两边，每次取较小的放到结果临时数组里。

1. i 指向左半边起点（left），j 指向右半边起点（mid+1），k 指向临时数组写入位置（left）
2. 两边都有元素时，取较小的放入 temp[k]
3. 某一边遍历完后，把另一边剩余的直接放入
4. 把 temp 的内容复制回原数组对应区间

merge 代码

void merge(int *nums, int left, int mid, int right, int *temp) {
    int i = left;       // 左半边的起点
    int j = mid + 1;    // 右半边的起点
    int k = left;       // 临时数组的写入位置

    // 两边都有元素时，取较小的
    while (i <= mid && j <= right) {
        if (nums[i] <= nums[j]) {
            temp[k++] = nums[i++];
        } else {
            temp[k++] = nums[j++];
        }
    }

    // 左边剩余
    while (i <= mid) {
        temp[k++] = nums[i++];
    }

    // 右边剩余
    while (j <= right) {
        temp[k++] = nums[j++];
    }

    // 把临时数组的内容复制回原数组
    for (int p = left; p <= right; p++) {
        nums[p] = temp[p];
    }
}

mergeSortHelper 递归拆分的思路

1. 基准情况：left >= right，0或1个元素，直接返回
2. 算中点 mid = left + (right - left) / 2
3. 递归排序左半边 [left, mid]
4. 递归排序右半边 [mid+1, right]
5. 合并两个有序半边

void mergeSort(int *nums, int left, int right, int *temp) {
    if (left >= right) return;    // 基准情况：0或1个元素

    int mid = left + (right - left) / 2;

    mergeSort(nums, left, mid, temp);        // 递归排序左半边
    mergeSort(nums, mid + 1, right, temp);   // 递归排序右半边
    merge(nums, left, mid, right, temp);     // 合并两个有序半边
}

完整代码

void merge(int *nums, int left, int mid, int right, int *temp) {
    int i = left, j = mid + 1, k = left;

    while (i <= mid && j <= right) {
        if (nums[i] <= nums[j]) {
            temp[k++] = nums[i++];
        } else {
            temp[k++] = nums[j++];
        }
    }
    while (i <= mid) temp[k++] = nums[i++];
    while (j <= right) temp[k++] = nums[j++];

    for (int p = left; p <= right; p++) {
        nums[p] = temp[p];
    }
}

void mergeSortHelper(int *nums, int left, int right, int *temp) {
    if (left >= right) return;

    int mid = left + (right - left) / 2;
    mergeSortHelper(nums, left, mid, temp);
    mergeSortHelper(nums, mid + 1, right, temp);
    merge(nums, left, mid, right, temp);
}

void mergeSort(int *nums, int n) {
    int *temp = (int *)malloc(sizeof(int) * n);
    mergeSortHelper(nums, 0, n - 1, temp);
    free(temp);
}

// 调用方式：
// mergeSort(nums, numsSize);

特征

• 时间复杂度：始终 O(n log n)（最好最坏平均都是，不会退化）
• 空间复杂度：O(n)（临时数组 O(n) + 递归栈 O(log n)，O(n) 是大头）
• 稳定： 合并时条件用 <=，相等元素左边的先放入，相对顺序不变

六、快速选择（题目215：第K个最大元素）

核心思想

利用快排 partition 分区的性质：partition 分区后 pivot 在最终正确位置。如果 pivot 恰好在目标位置，直接返回；否则只递归包含目标位置的那一边。

和快排的区别：快排每次递归两边，快速选择每次只递归一边。

思路

第K大的元素在升序排序后的索引是 targetIndex = n - k。

1. 对数组做 partition， 得到 pivot 的位置 pivotIndex
2. pivotIndex == targetIndex → 找到了，返回 nums[pivotIndex]
3. pivotIndex < targetIndex → 目标在右半边，只递归右边
4. pivotIndex > targetIndex → 目标在左半边，只递归左边

代码

int partition(int *nums, int low, int high) {
    // 随机选pivot
    int randomIndex = low + rand() % (high - low + 1);
    int temp = nums[randomIndex];
    nums[randomIndex] = nums[high];
    nums[high] = temp;

    int pivot = nums[high];
    int i = low;
    for (int j = low; j < high; j++) {
        if (nums[j] <= pivot) {
            int t = nums[i];
            nums[i] = nums[j];
            nums[j] = t;
            i++;
        }
    }
    int t = nums[i];
    nums[i] = nums[high];
    nums[high] = t;
    return i;
}

int quickSelect(int *nums, int low, int high, int targetIndex) {
    if (low == high) return nums[low];    // 只剩一个元素

    int pivotIndex = partition(nums, low, high);

    if (pivotIndex == targetIndex) {
        return nums[pivotIndex];               // 找到了
    } else if (pivotIndex < targetIndex) {
        return quickSelect(nums, pivotIndex + 1, high, targetIndex);   // 在右边找
    } else {
        return quickSelect(nums, low, pivotIndex - 1, targetIndex);    // 在左边找
    }
}

int findKthLargest(int *nums, int numsSize, int k) {
    return quickSelect(nums, 0, numsSize - 1, numsSize - k);
}

时间复杂度

• 平均 O(n)。 每次 partition 是 O(n)，但只递归一半。总工作量：n + n/2 + n/4 + ... ≈ 2n = O(n)。
• 最坏 O(n²)（和快排一样，每次 partition 极度不均匀）。加随机化后最坏情况极少发生。