排序（sort）

一、排序核心基础概念

1. 排序的稳定性（最高频基础考点）

核心定义

稳定排序：排序前后，值相等的元素的相对位置保持不变；反之则为不稳定排序。

GESP必考三大排序的稳定性结论

• 选择排序不稳定示例：
  数组{2, 3, 2, 1, 5, 4}升序选择排序，第一轮最小值交换后结果为{1, 3, 2, 2, 5, 4}；注意此时第四个2是原来的第一个2，第三个2没动，第一个2跑到第三个2后面了。

  2. 时间复杂度

  排序算法	最坏时间复杂度	平均时间复杂度	最好时间复杂度	说明
  冒泡排序	O(n²)	O(n²)	O(n)	最好情况：数组已有序+设置交换标志位优化，无需交换直接退出
  插入排序	O(n²)	O(n²)	O(n)	最好情况：数组已有序，内层while循环无需执行，仅遍历一次数组
  选择排序	O(n²)	O(n²)	O(n²)	无论数组是否有序，都必须完整遍历未排序区间找极值，比较次数固定

考点结论

1. 选择排序无论初始数组是否有序，都必须执行O(n²)次比较，此为判断题固定考点。
2. 冒泡排序、插入排序的最优时间复杂度为O(n)，最坏/平均为O(n²)。
3. 小数据量场景下，插入排序因单元操作少、逻辑简单，实际执行效率高，是工程中常用的小数据排序方案。

二、三大排序算法模板

1. 插入排序（考察频次最高）

核心思想

将数组分为已排序区间和未排序区间，初始已排序区间为数组第一个元素；依次取出未排序区间的每个元素，插入到已排序区间的正确位置，直到所有元素排序完成。

核心适用场景

• 数据几乎有序，仅需少量调整；
• 小数据量排序；
• 需要稳定排序的场景。

升序排序核心代码

void insertionSort(int arr[], int n) {
    // 外层循环：从第2个元素开始（i=1），遍历未排序区间
    for (int i = 1; i < n; i++) {
        // 考点1：定义待插入的基准值key，j初始化为i-1（已排序区间最后一个元素下标）
        int key = arr[i]; // 当前待排序元素
        int j = i - 1; // 向前遍历
        
        // 考点2：内层循环：找到key的正确插入位置
        // 循环条件：j不越界，且已排序元素大于key（需要后移）
        while (j >= 0 && arr[j] > key) {
            // 考点3：元素后移，为key腾出位置
            arr[j + 1] = arr[j];
            j--;
        }
        // 考点4：将key插入到正确位置
        arr[j + 1] = key; // j为不大于key的位置，实际插入到j+1位置。
    }
}

考点

1. 基准值key必须赋值为arr[i]，j的初始值必须为i-1；
2. 升序排序的while循环条件为arr[j] > key，降序则为arr[j] < key；
3. 最终插入位置为j+1，而非j。

2. 冒泡排序

核心思想

重复遍历数组，两两比较相邻元素，若逆序则交换；每一轮遍历都会将当前未排序区间的最大元素，逐步“冒泡”到未排序区间的末尾，已排序区间从数组末尾逐步扩大。

升序排序核心代码（含优化标志位）

void bubbleSortWithFlag(int nums[], int n) {
    // 外层循环：控制未排序区间的右边界，从末尾逐步前移
    for (int i = 0; i < n; i++) {
        // 考点1：交换标志位初始化，默认false（本轮无交换）
        bool flag = false;
        // 内层循环：遍历未排序区间，两两比较相邻元素
        for (int j = 0; j < n - i; j++) { // 每一轮排序后都可以少处理一个元素，因为最后一个有序了
            if (nums[j] > nums[j + 1]) {
                swap(nums[j], nums[j + 1]);
                // 发生交换，将标志位设为true
                flag = true;
            }
        }
        // 本轮无交换，说明数组已有序，直接退出排序
        if (!flag) break;
    }
}

真题高频考点

1. 每轮排序后的数组结果计算：升序排序第一轮结束后，数组的最大值会被移动到数组末尾；

   • 示例1：数组{4, 1, 3, 1, 5, 2}，第一轮升序冒泡后结果为{1, 3, 1, 4, 2, 5}；
   • 示例2：数组{5, 3, 8, 1}，第一轮升序冒泡后结果为{3, 5, 1, 8}。
2. 标志位优化：flag初始化为false，发生交换时设为true；若一轮结束flag仍为false，说明数组已有序，可提前终止排序，此为冒泡排序最优O(n)时间复杂度的实现基础。

3. 选择排序

核心思想

将数组分为已排序区间和未排序区间，初始已排序区间为空；每一轮从未排序区间中找到最小（升序）/最大（降序）元素，与未排序区间的第一个元素交换，已排序区间逐步扩大，直到所有元素排序完成。

升序排序核心代码（真题填空考点全覆盖）

void selectionSort(int nums[], int n) {
    // 外层循环：未排序区间的起始下标
    for (int i = 0; i < n - 1; ++i) {
        // 初始化最小值下标为未排序区间第一个元素
        int minIndex = i;
        // 内层循环：遍历未排序区间，找到最小值的下标
        // j从i+1开始，遍历到数组末尾
        for (int j = i + 1; j < n; ++j) {
            // 升序排序，找到比当前最小值更小的元素，更新最小值下标
            if (nums[j] < nums[minIndex]) {
                minIndex = j;
            }
        }
        // 将最小值与未排序区间第一个元素交换
        if (minIndex != i) {
            swap(nums[i], nums[minIndex]);
        }
    }
}

考点

1. 代码填空核心点：

   • 最小值下标minIndex初始化为i；
   • 内层循环j的起始值为i+1；
   • 升序比较条件为nums[j] < nums[minIndex]，降序则为nums[j] > nums[maxIndex]；
   • 最终交换的是nums[i]和nums[minIndex]，而非其他元素。
2. TopK场景应用：从n个元素中选出前k个最大/最小元素，可通过选择排序实现：外层循环仅执行k次，每轮找到极值交换到前面，无需完成全量排序。

3. 每轮排序后的数组结果计算：升序排序第一轮结束后，数组的最小值会被交换到数组第一个位置。

   • 真题示例：数组{4,3,1,5,2}，第一轮升序选择排序后，最小值1被交换到首位，结果为{1,3,4,5,2}。

三、易错点与陷阱

本模块覆盖真题所有判断题考点，是GESP 4级排序题的高频失分点：