【笔记/模板】排序算法

【模板】快速排序 - 洛谷

1. 冒泡排序

排序原理：
每次将未确定部分的相邻两个值对比，设为$a_{i},a_{i+1}$，如果$a_{i}>a_{i+1}$,则对这两个值进行交换，可以使用swap来快速对两个值进行交换。
那么，这样一轮交换下去，第一个数就可以确定是最小的了。以此类推，直到所有值都被确定，就得出最终排好序的数列了。
时间复杂度：$O(n^2)$

核心模板代码如下：

1
2
3
4
5
6

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].
}

2. 桶排序

排序原理：

桶排序的原理很简单，就是定义一个数组为桶，然后每个桶代表一个数字，每输入一个数就将这个数对应的桶加上 $1$（比如说 $3$，它所对应的桶下标就是 $3$），最后扫描桶，因为题目要求是从小到大排序，所以就直接正序扫描即可，只要桶里有值就输出。
这种排序的速度比较快，但是缺点是数值如果数的范围十分大，需要定义一个$10^9$大的桶，这样会 MLE。

时间复杂度：$O(n+k)$（$k$​ 为待排序数据值域）

核心模板代码如下：

1
2
3
4
5
6
7
8
9

const int N = 1e8 + 9;
int book[N];
int n,a;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a,book[a]++;
    for(int i=0;i<=1e8;i++) for(int j=1;j<=book[i];j++) cout<<i<<" ";
}

3. 快速排序

排序原理：

我们设待排序的序列为一个长度为 $n$ 的序列 $a$。
快速排序的具体原理如下：

首先，在 $a$ 中随机选择一个数 $x$，之后我们进行如下操作：

如果 $n = 0$ 或 $n = 1$ ，此时根本无需排序，直接退出。

定义三个新的序列 $b, c, d$ ；

在 $a$ 中随机选择一个数 $x$ ；

遍历整个序列 $a$ ，将比 $x$ 小的放在 $b$ 内，比 $x$ 大的放在 $d$ 内，和 $x$ 相等的放在 $c$ 内；

将 $b$ , $d$ 按如上过程继续排序。

序列 $c$​ 中的数因为都相等所以不必排序。

时间复杂度：$O(n \log n)$

核心模板代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

void quicksort(int a[],int l,int r){
    int i=l,j=r,flag=a[(l+r)/2];
    do{
        while(a[i]<flag){
            i++;
        }
        while(a[j]>flag){
            j--;
        }
        if(i<=j){
            swap(a[i],a[j]);
            i++;
            j--;
        }
    }while(i<=j);
    if(l<j){
        quicksort(a,l,j);
    }
    if(i<r){
        quicksort(a,i,r);
    }
}

4. 归并排序

排序原理：

归并排序用的是分治思想，分为三大步：

1. 将$n$个元素分成两个含有$n / 2$个元素的子序列。

2. 解决：用合并排序法对两个子序列递归来排序。

3. 合并：合并两个已排序的子序列来得到最终的排序结果。

时间复杂度：$O(n \log n)$

两种实现方法：

1. 迭代法

① 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列。
② 设定两个指针，最初位置分别为两个已经排序序列的起始位置。
③ 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置。
④ 重复步骤③直到某一指针到达序列尾。
⑤ 将另一序列剩下的所有元素直接复制到合并序列尾。

2. 递归法

① 将序列每相邻两个数字进行归并操作，形成$\left \lfloor \frac{n}{2} \right \rfloor $个序列，排序后每个序列包含两个元素。 ② 将上述序列再次归并，形成$\left \lfloor \frac{n}{4} \right \rfloor $个序列，每个序列包含四个元素。
③ 重复步骤②，直到所有元素排序完毕。

核心模板代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

void mergesort(int l, int r, int a[])
{
    int mid = l + r >> 1;
    if (l == r) return;
    mergesort(l, mid, a);
    mergesort(mid + 1, r, a);

    int i = l, j = mid + 1, k = l;
    while (i <= mid && j <= r)
    {
        if (a[i] > a[j]) b[k ++] = a[j ++];
        else b[k ++] = a[i ++];
    }
    while (i <= mid) b[k ++] = a[i ++];
    while (j <= r) b[k ++] = a[j ++];
    for (int i = l; i <= r; i++) a[i] = b[i];
}