排序

· · 题解

排序算法

排序算法是对一个数列根据某种规律进行重排列的操作，一般都是从小（大）到大（小）。

经典入门排序算法：冒泡排序

虽然不是正解但是可以介绍，这个主要是带萌新了解排序的实现，这也是排序算法中最通俗易懂的一个了。

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,a[100001];
void pop_sort(){
    for (int i=1;i<=n;i++)
        for (int j=1;j<n;j++)
            if (a[j]>a[j+1]) swap(a[j],a[j+1]);//change a[j] and a[j+1].
}
signed main(){
    cin>>n;
    for (int i=1;i<=n;i++) cin>>a[i];
    pop_sort();
    for (int i=1;i<=n;i++) cout<<a[i]<<' ';
    return 0;
}

思路：

每次将未确定部分的相邻两个值对比，设为 a_i,a_{i+1}。如果 a_i>a_{i+1} 则对这两个值进行交换，可以使用 swap 来快速对两个值进行交换。

那么，这样一轮交换下去，第一个数就可以确定是最小的了。以此类推，直到所有值都被确定，就得出最终排好序的数列了。

时间复杂度 \text O(n^2)。

分析本题

本题 1\leq n \leq 10^5，那么 \text O(n^2) 是过不去的，至少要 \text O(n\log n)。

正解来力，快速排序

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,a[100001],b[100001],c[100001],d[100001];
void quick_sort(int l,int r){
    if (l>=r) return;
    int mid=rand()%(r-l+1)+l;//This value is random.
    int tb=0,tc=0,td=0;//b is smaller than a[mid],c is bigger than it,d is the same of it.
    for (int i=l;i<=r;i++){
        if (a[i]<a[mid]) b[++tb]=a[i];
        else if (a[i]>a[mid]) c[++tc]=a[i];
        else d[++td]=a[i];
    }
    for (int i=1;i<=tb;i++) a[l+i-1]=b[i];
    for (int i=1;i<=td;i++) a[l+i-1+tb]=d[i];
    for (int i=1;i<=tc;i++) a[l+i-1+tb+td]=c[i];
    quick_sort(l,l+tb-1);
    quick_sort(l+tb+td,r);
}
signed main(){
    srand((int)time(0));
    cin>>n;
    for (int i=1;i<=n;i++) cin>>a[i];
    quick_sort(1,n);
    for (int i=1;i<=n;i++) cout<<a[i]<<' ';
    return 0;
}

思路：

找到一个“基准”，将小的往前面放，将大的往后面放。由于数据的不确定性，这个“基准”最好是一个随机数。这样分成三块：比基准小的，等于基准的，大于基准的。将第一者和第三者再递归进行快排。

平均复杂度 \text O(n \log n)，但是并不太稳定。

上述是手写快排，更稳定更简单的 STL 大法给我们提供了 sort 排序！其用法为 sort(<要排序的数组>+<排序区间左端>,<要排序的数组>+<排序区间右端>,<排序规则>)。其中排序规则默认为从小到大。

复杂度 \text O(n \log n)，稳定。所以考场最好写一个 sort 实现排序。

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,a[100001];
signed main(){
    cin>>n;
    for (int i=1;i<=n;i++) cin>>a[i];
    sort(a+1,a+n+1);
    for (int i=1;i<=n;i++) cout<<a[i]<<' '; 
    return 0;
}

拓展 STL sort 的排序规则（命名为 cmp）：

只是一个普通数列的排序直接写就行。如下是从大到小的排序规则的示例：

bool cmp(int o,int p){
    return o>p;//biggest is first
}

当然你可以玩更多的花样，比如数列所有值模上 3 的值从大到小的排列，如果模上 3 的值相等，原值大的在前面：

bool cmp(int o,int p){
    if (o%3>p%3) return 1;
    else if (o%3==p%3&&o>p) return 1;
    else return 0;
}

结构体排序：

结构体的复杂那么一点点，但也很简单。如果不知道结构体可以自行百度。如下的判定规则：结构体的两个值为 a,b，按照 a 从大到小排序，如果 a 出现相等，按照 b 从大到小排序。

struct node{
    int a,b;//create a struct "node"
};
bool cmp(node o,node p){
    if (o.a!=p.a) return o.a>p.a;
    return o.b>p.b;
}

结构体重载运算符排序：

重载即为重写 sort 的规则，主要在结构体内运用 operator<，而不是 cmp。

struct node{
    int a,b;//create a struct "node"
    bool operator<(const node x){
        if (a!=x.a) return this->a>x.a;
        return this->b<x.b;
    }
};

在 sort 中调用的时候直接写 cmp 就行，不用加括号。不过如果你使用了结构体重载运算符，则不需要调用。