GESP五级 排序

一、排序算法对比

核心概念

• 稳定性：相同元素排序后相对顺序不变
• 原地排序：不需要额外的大规模辅助空间

二、快速排序

1. 核心原理

分治思想：选一个基准值（pivot），将数组中小于基准值的数都放到基准值左边，大于基准值的数都放到基准值右边（基准值归位），此时基准值自身相对有序了，只需要对左右两部分再二分递归进行上述处理。

基准值（pivot） 一般取随机位置，最好情况下基准值每次都正好二分整个数组，时间复杂度nlog(n)，最坏情况下基准值取最左或最右，而数组本身有序，导致二分时每次数据规模只能减少1个，时间复杂度退化到n*n。

2. 考点

（1）时间复杂度

• 平均：O(n log n)（常数小，实践中最快）
• 最坏：O(n²)（有序数组+首/尾元素为基准，每轮划分成0和n-1）
• 优化：随机选基准、三数取中（首/中/尾选中间值），可大幅降低最坏情况概率

（2）特性

• ❌ 不稳定（交换会打乱相等元素顺序，与基准选择无关）
• ✅ 原地排序（仅用递归栈空间）

（3）核心代码 基准值归位

// 首元素为基准的Partition
int partition(vector<int>& arr, int low, int high) {
    int pivot = arr[low];
    int i = low, j = high;
    while (i < j) {
        // 先从右往左找小于基准的元素
        while (i < j && arr[j] >= pivot) j--;
        // 再从左往右找大于基准的元素
        while (i < j && arr[i] <= pivot) i++;
        if (i < j) swap(arr[i], arr[j]);
    }
    swap(arr[i], arr[low]); // 基准归位
    return i;
}

• 易错：左右查找顺序不能交换（先右后左），否则会导致基准归位错误

三、归并排序

1. 核心原理

分治思想：将数组不断二分，直到数组中只有一个数，则自身是有序的。然后再在回溯过程中，将有序的小数组两两有序合并。

2. 考点

（1）时间复杂度

• 最好/最坏/平均：均为O(n log n)（与输入数据是否有序无关）
• 适合大规模数据排序

（2）特性

• ✅ 稳定排序（相等元素先取左数组，保持原顺序）
• ❌ 非原地排序：需要 O(n) 额外辅助空间做数组合并用

（3）核心代码 数组合并

// 合并两个有序数组 [left,mid] 和 [mid+1,right]
void merge(vector<int>& arr, vector<int>& temp, int left, int mid, int right) {
    int i = left, j = mid + 1, k = 0;
    // 同时遍历两个子数组
    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++];
    // 复制回原数组
    for (int p = 0; p < k; p++) arr[left + p] = temp[p];
}

• 高频填空：while (j <= right)（右子数组剩余元素）
• 合并两个有序数组的比较条件：arr[i] <= arr[j]（保证稳定性）

3. 应用 统计逆序对

归并排序是统计逆序对的最优方法，时间复杂度 O(n log n)

void merge_count(vector<int>& a, int l, int mid, int r) {
    int i = l;      // 左区间起点
    int j = mid+1;  // 右区间起点
    vector<int> temp; // 临时数组：存储合并后的有序结果
    
    // 1. 双指针合并 + 统计逆序对
    while (i <= mid && j <= r) {
        if (a[i] <= a[j]) {
            temp.push_back(a[i++]);
        } else {
            // 核心：左区间剩余所有数都 > a[j]，构成逆序对
            cnt += mid - i + 1;
            temp.push_back(a[j++]);
        }
    }
    
    // 2. 把剩余元素加入临时数组
    while (i <= mid) temp.push_back(a[i++]);
    while (j <= r) temp.push_back(a[j++]);
    
    // 3. 将合并后的有序数组 赋值回原数组 a
    for (int k = 0; k < temp.size(); k++) {
        a[l + k] = temp[k];
    }
}

四、基础排序算法（冒泡/插入/选择）

1. 核心考点

2. 易错点

• 冒泡和插入排序在完全有序数组下时间复杂度为O(n)
• 选择排序不稳定（如 [2,2,1] 排序后两个2顺序交换）

五、本文涉及排序全部模板

1. 冒泡排序（基础排序）

核心：重复交换相邻逆序元素，每轮把最大值「冒泡」到末尾
时间复杂度：$O(n^2)$，稳定排序

// 冒泡排序：a为待排序数组，n为数组长度
void bubbleSort(int a[], int n) {
    // 外层循环：控制排序轮数，n个元素最多排n-1轮
    for (int i = 0; i < n - 1; i++) {
        bool flag = false; // 优化标记：本轮是否发生交换
        // 内层循环：两两比较，每轮少比较i个（末尾i个已排好序）
        for (int j = 0; j < n - 1 - i; j++) {
            // 前一个数 > 后一个数，交换（升序）
            if (a[j] > a[j + 1]) {
                swap(a[j], a[j + 1]); // 交换两个元素
                flag = true; // 标记发生了交换
            }
        }
        // 优化：如果本轮无交换，说明数组已有序，直接退出
        if (!flag) break;
    }
}

2. 选择排序（基础排序）

核心：每轮选未排序区间的最小值，放到已排序区间末尾
时间复杂度：$O(n^2)$，不稳定排序

// 选择排序：a为待排序数组，n为数组长度
void selectionSort(int a[], int n) {
    // 外层循环：划分已排序/未排序区间，i是已排序区间末尾
    for (int i = 0; i < n - 1; i++) {
        int minIdx = i; // 记录最小值的下标，初始为未排序区间第一个元素
        // 内层循环：遍历未排序区间，找最小值下标
        for (int j = i + 1; j < n; j++) {
            if (a[j] < a[minIdx]) {
                minIdx = j; // 更新最小值下标
            }
        }
        // 把最小值交换到已排序区间末尾
        swap(a[i], a[minIdx]);
    }
}

3. 插入排序（基础排序）

核心：将当前元素插入到前面已排序的正确位置
时间复杂度：$O(n^2)$，稳定排序

// 插入排序：a为待排序数组，n为数组长度
void insertionSort(int a[], int n) {
    // 外层循环：从第2个元素开始，逐个插入（第一个元素默认有序）
    for (int i = 1; i < n; i++) {
        int temp = a[i]; // 保存当前要插入的元素
        int j = i - 1;   // 从已排序区间最后一个元素开始比较

        // 向前遍历已排序区间：如果前面元素更大，就向后挪位
        while (j >= 0 && a[j] > temp) {
            a[j + 1] = a[j]; // 元素后移
            j--;
        }
        // 跳出循环：j+1就是当前元素的插入位置
        a[j + 1] = temp;
    }
}

4. 快速排序（考试高频，分治）

核心：选基准值 → 分区（小左大右）→ 递归处理左右区间
时间复杂度：平均 $O(n\log n)$，最坏 $O(n^2)$，不稳定排序

// 快速排序分区函数：把数组按基准值划分，返回基准值最终位置
int partition(int a[], int l, int r) {
    // 随机选基准值（优化：防止有序数组退化）
    swap(a[l], a[l + rand() % (r - l + 1)]);
    int pivot = a[l]; // 选定基准值

    // 双指针分区：i左，j右
    int i = l, j = r;
    while (i < j) {
        // 右指针向左找 < 基准值的数
        while (i < j && a[j] >= pivot) j--;
        // 左指针向右找 > 基准值的数
        while (i < j && a[i] <= pivot) i++;
        swap(a[i], a[j]); // 交换左右指针元素
    }
    swap(a[l], a[i]); // 基准值归位
    return i; // 返回基准值下标
}

// 快速排序主函数：l=左边界，r=右边界
void quickSort(int a[], int l, int r) {
    // 递归终止条件：区间只有一个元素/空，无需排序
    if (l >= r) return;

    // 分区：得到基准值位置
    int pos = partition(a, l, r);
    // 递归排序左区间（基准值左边）
    quickSort(a, l, pos - 1);
    // 递归排序右区间（基准值右边）
    quickSort(a, pos + 1, r);
}

5. 归并排序（分治，稳定，可统计逆序对）

核心：拆分数组 → 递归排序子数组 → 合并两个有序数组
时间复杂度：$O(n\log n)$，稳定排序

// 归并函数：合并两个有序区间 [l,mid] 和 [mid+1,r]
void merge(int a[], int l, int mid, int r, int temp[]) {
    int i = l;      // 左区间指针
    int j = mid + 1;// 右区间指针
    int k = 0;      // 临时数组指针

    // 1. 双指针遍历两个有序区间，按顺序放入临时数组
    while (i <= mid && j <= r) {
        if (a[i] <= a[j]) {
            temp[k++] = a[i++];
        } else {
            temp[k++] = a[j++];
        }
    }

    // 2. 把左区间剩余元素放入临时数组
    while (i <= mid) temp[k++] = a[i++];
    // 3. 把右区间剩余元素放入临时数组
    while (j <= r) temp[k++] = a[j++];

    // 4. 把临时数组的有序结果复制回原数组
    for (int p = 0; p < k; p++) {
        a[l + p] = temp[p];
    }
}

// 归并排序主函数：l=左边界，r=右边界，temp=临时数组
void mergeSort(int a[], int l, int r, int temp[]) {
    // 递归终止条件
    if (l >= r) return;

    int mid = (l + r) / 2; // 拆分中点
    mergeSort(a, l, mid, temp);    // 递归排序左半
    mergeSort(a, mid + 1, r, temp);// 递归排序右半
    merge(a, l, mid, r, temp);     // 合并两个有序区间
}