P1177题解

66xyyd · 2023-05-03 17:21:58 · 题解

良好的开端：冒泡排序

拿到这道题，我们一眼就能看出来，题目要求把一个无序序列变为从小到大排序的有序序列~~人尽皆知~~。我们可以考虑我们是怎么把一个序列变有序的。如对于下面的序列：

4 2 4 5 1

我们可以从左到右巡视一遍。首先我们看到 4 和 2 顺序反了，所以把它们换一下：

2 4 4 5 1

然后我们继续从左到右看，发现 5 和 1 的顺序反了，所以把它们换一下：

2 4 4 1 5

但是 1 次过后序列并没有变有序。所以我们还需要再巡视一遍：

2 4 1 4 5

这样再巡视 2 次，我们就可以得到最终的序列：

1 2 4 4 5

在这里您可以仔细研究一下交换的逻辑。

问题来了：为什么我们要从左到右巡视那么多遍？怎么确定巡视的倍数？

这是因为，每次巡视后我们只能保证新固定至少一个数。 想一下，我们在之前交换的时候，第一次巡视把最大数的固定在了序列最右边，第二次把次大的数固定在了最大数的左边，第三次把第三大的数固定在了次大数的左边……等到最后一次，我们把第 N-1 大的数固定在了第 N-2 大的数的左边，剩下的一个数自然不用比较。这样，我们就得到了一个有序的序列。

代码（60pts）：

#include<iostream>
using namespace std;
int N,a[100001]={};
int main(){
    //输入部分
    cin >> N;
    for(int i=0;i<N;i++){
        cin >> a[i];
    }
    //排序部分（这里是重点）
    for(int i=1;i<=N-1;i++){//一共要巡视N-1次，因为最后一次最小的一个数位置已经固定，不用巡视
        for(int j=0;j<N-i;j++){//开始从左到右巡视，因为右边的数已经固定，所以无需比较
            if(a[j]>a[j+1]){
                swap(a[j],a[j+1]);//如果顺序反了就交换
            }
        }
    }
    //输出部分
    for(int i=0;i<N;i++){
        cout << a[i] << ' ';
    }
    return 0;
}

当然冒泡排序是有优化的，但不是本文的重点，所以略去不讲。

优化：快速排序

冒泡排序是很快的，但面临 10^5 的数据范围还是有些乏力。如何优化呢？这时，我们就需要运用二分这个利器了。

二分从何而来？我们可以先把数列分成两段，分别排序后进行归并操作。在这里，数列被划分成更小的两个子序列，就是在二分（归并排序的思想，本文略去不讲）；而另一种思路就是使用划分了。

如果有一个位置，在这个位置之前，所有的数都比它小；在这个位置之后，所有的数都比它大，这样对左边再进行排序，对右边再进行排序，最后的数列一定满足单调不降。划分正是照着这个思路来的。我们可以选定一个基准数，并根据“比基准数小的放基准数前面，比基准数大的放基准数后面”的原则调整序列。这应该怎么办呢？（可以思考一下）

哈，有了！我们可以参照冒泡排序巡视的原则，设定两个哨兵。一个哨兵从左往右巡视，专门找比基准数大的数；一个哨兵从右往左巡视，专门找比基准数小的数。两个哨兵找到了就交换，然后开始下一轮巡视。如果两个哨兵相遇了，那就满足了条件，结束划分。

代码（100pts）：

#include<iostream>
#include<ctime>
#include<random>
using namespace std;
int N,a[100001]={};
inline int randint(int l,int r){
    //从[l,r]中随机选择一个整数返回
    static default_random_engine e(time(0));
    return uniform_int_distribution<int>(l,r)(e);
}
void quicksort(int l,int r){
    //快速排序函数
    if(l>=r)    return;
    int pivot=a[randint(l,r)],i=l,j=r;//pivot是此次选定的基准数（本代码选取区间随机一个数），i和j是两个哨兵，分别从两端开始。
    do{//要循环至少1次
        while(a[i]<pivot)   i++;//哨兵i找到现在开始第一个比基准数大的数
        while(a[j]>pivot)   j--;//哨兵j找到现在开始第一个比基准数小的数
        if(i<=j){//判断哨兵i和哨兵j，要求不能相遇（特别注意判断相等的情况）
            swap(a[i],a[j]);
            i++,j--;
        }
    }while(i<=j);//判断哨兵i和哨兵j，要求不能相遇（特别注意判断相等的情况）
    quicksort(l,j);//因为j是为基准数范围的最左端，所以再左移一位即可
    quicksort(i,r);//因为i是为基准数范围的最右端，所以再右移一位即可
}
int main(){
    //输入部分
    cin >> N;
    for(int i=0;i<N;i++){
        cin >> a[i];
    }
    //排序部分
    quicksort(0,N-1);
    //输出部分
    for(int i=0;i<N;i++){
        cout << a[i] << ' ';
    }
    return 0;
}

懒人的福利：sort

~~看前面说了那么多，实际上只需要用这个就够了~~

C++标准库头文件中有一个函数：sort。sort 函数运用了快速排序来给序列排序，默认从小到大排序，但加入了许多优化，使得程序运行得非常快（有些甚至基于底层）。如果您不喜欢快速排序的不稳定，也可以使用归并排序的 stable_sort。使用方法：

#include<iostream>
#include<algorithm>
using namespace std;
int N,a[100001]={};
int main(){
    //输入部分
    cin >> N;
    for(int i=0;i<N;i++){
        cin >> a[i];
    }
    //排序部分
    sort(a+0,a+N);//sort格式为sort(begin,end)，排序[begin,end)（也就是begin~end-1）的部分。内置数组在排序时要传入指针，所以是a+0,a+N
    //sort(a+0,a+N,[](int a,int b){return a<b;});sort还支持自定义比较函数，只需要在后面再传入一个函数指针cmp即可（这里偷懒用了lambda表达式），排序后保证对于任意范围内指针iter，cmp(*iter,*(iter+1))为true。
    //stable_sort(a+0,a+N);stable_sort的格式和sort是一样的，区别仅在内部排序方式。
    //输出部分
    for(int i=0;i<N;i++){
        cout << a[i] << ' ';
    }
    return 0;
}

后记

感谢Untitled_unrevised指出本文归并排序与快速排序使用二分的不同点，已改正。
感谢这个讨论中指出的事实性错误导致可以把本文的快速排序卡到最坏时间复杂度，已采用随机选取基准数的方法，且通过测试。