题解：P1177 【模板】排序

Igallta · 2025-03-14 15:05:38 · 题解

省流：快排。

这道题就是一个排序的模板。

首先，我们考虑一个比较辣鸡的排序。

既然是从小到大排序，那我们就遍历整个数组，如果相邻的两个数 a_{i-1} 和 a_i，有 a_i<a_{i-1}，那么我们就把它们俩交换，一直重复这个操作，直到排好序。

这种排序叫做冒泡排序。

如何证明冒泡排序？

循环不变量定义

外层循环不变量：第 i 次外层循环结束时，数组的最后 i 个元素是已排序的，并且是原数组中最大的 i 个元素。

数学归纳法证明

基例
当 i = 0 时，未进行任何排序操作，数组末尾的 0 个元素为空，显然满足循环不变量。
归纳假设
假设第 k 次外层循环结束后，数组的最后 k 个元素已排序且为最大元素。
归纳步骤
- 第 k+1 次外层循环中，内层循环遍历未排序部分 [0, n-k-2]。
- 每次内层循环比较相邻元素 arr[j] 和 arr[j+1]，若逆序则交换。
- 通过遍历，未排序部分的最大值会被交换到 arr[n-k-1] 的位置。
- 此时，末尾 k+1 个元素满足有序且为最大元素。
终止条件
当 i = n-1 时，末尾 n-1 个元素已有序，剩余第一个元素自然为最小值，整个数组有序。

时间复杂度分析

最坏/平均情况：\Omicron(n^2)

需两层嵌套循环，比较次数为 \frac{n(n-1)}{2}。
最好情况（已有序）：\Omicron(n)

通过 swapped 标志优化，只需一次遍历即可终止。

因为冒泡排序为 \Omicron(n^2) 所以只能获得部分分，无法通过此题。

我们观察到数据范围为 N\leqslant 10^5，那我们就得考虑一个更厉害的算法。

首先，我们考虑冒泡排序哪里不好：

冒泡排序的局限性

冒泡排序通过相邻元素交换将最大值逐步“浮”到数组末尾，时间复杂度为 O(n^2)。其核心问题：

低效的局部操作：每次仅消除一个逆序对。
缺乏分治策略：无法利用子问题的独立性加速排序。

快速排序（QuickSort）的核心思想

快速排序采用分治策略和递归，平均时间复杂度 O(n \log n)。

算法步骤

选择基准：从数组中选一个元素作为基准（如首元素、末元素或随机元素）。
分区：将数组划分为两部分：
- 左半部分：所有元素 \leqslant 基准
- 右半部分：所有元素 > 基准
递归排序：对左右子数组递归执行上述操作。

关键优势

高效的分区操作：单次分区可消除多个逆序对。
分治递归：子问题相互独立，适合并行优化。

快速排序正确性证明

分区操作的正确性

循环不变量：

设基准为 arr[high]，分区过程中维护区间 [0, i]，其中所有元素 \leqslant 基准。
遍历时，若当前元素 \leqslant 基准，则将其交换到 [0, i] 的末尾，并扩展区间。

证明：

初始化：i = low - 1，区间为空，满足条件。
保持：若 arr[j] <= pivot，交换后区间 [0, i] 仍满足条件。
终止：遍历结束时，arr[i+1] 是第一个 > 基准的元素，交换 arr[i+1] 与基准，完成分区。

递归过程正确性（数学归纳法）

基例：当子数组长度为 1 时，天然有序。
归纳假设：假设对长度 < n 的子数组，快速排序能正确排序。
归纳步骤：分区操作确保基准左侧 \leqslant 基准，右侧 > 基准；递归排序左右子数组后，整体有序。

时间复杂度分析

最佳情况

每次分区均分数组，递归树高度为 \log n，每层工作量 O(n)，总时间 O(n \log n)。

最坏情况

每次分区极不均衡（如数组已有序），递归树退化为链表，时间 O(n^2)。

平均情况

通过随机化选择基准，期望时间复杂度为 O(n \log n)。

总结对比

特性	冒泡排序	快速排序
时间复杂度（平均）	O(n^2)	O(n \log n)
空间复杂度	O(1)	O(\log n)（递归栈）
稳定性	稳定	不稳定（分区可能破坏顺序）
适用场景	小规模或近似有序	大规模随机数据

参考代码：

#include<iostream>
#include<algorithm>
#define int long long
using namespace std;
int n,a[100001];
void qsort(int l,int r){
    int i=l,j=r;
    int key=a[(l+r)/2],tmp;
    for(;i<j;){
        while(a[i]<key)i++;
        while(a[j]>key)j--;
        if(i<=j)swap(a[i],a[j]),i++,j--;

    }
    if(l<j)qsort(l,j);
    if(i<r)qsort(i,r);
}
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    qsort(1,n);
    for(int i=1;i<=n;i++)cout<<a[i]<<" ";
}