741 字
4 分钟
【OI考古】基础算法 | 排序

排序算法(Sorting algorithm)是一种将一组特定的数据按某种顺序进行排列的算法。排序算法多种多样,性质也大多不同。

几种排序算法的比较:

6hhmgH.gif

模板题:洛谷 P1177 | [模板]快速排序#

题目描述#

利用快速排序算法将读入的 NN 个数从小到大排序后输出。

输入格式#

11 行为一个正整数 NN,第 22 行包含 NN 个空格隔开的正整数 aia_i ,为你需要进行排序的数,数据保证了 aia_i 不超过 10910^9

输出格式#

将给定的 NN 个数从小到大输出,数之间空格隔开,行末换行且无空格。

输入输出样例#

输入 #1#
5
4 2 4 5 1
输出 #1#
1 2 4 4 5

说明/提示#

对于 20%20\% 的数据,有 N103N\leq 10^3

对于 100%100\% 的数据,有 N105N\leq 10^5

快速排序#

快速排序(Quicksort),又称分区交换排序(partition-exchange sort),简称快排,是一种被广泛运用的排序算法。

解决方案#

#include <iostream>
#include <cstdio>
using namespace std;
const int maxn = 100500;
int n;
int a[maxn];
void quick_sort(int a_[], int l, int r)
{
    int mid = a_[(l + r) >> 1]; //取区间中点的数,也可以随机化取数
    int i = l;
    int j = r;
    do
    {
        while (a_[i] < mid) //如果合法,就继续遍历
            i++;
        while (a_[j] > mid)
            j--;
        if (i <= j) //找到一对不合法的数,将其交换
        {
            swap(a_[i], a_[j]);
            i++;
            j--;
        }
    } while (i <= j); //最终的效果是[l, j]内的数都≤mid,[i, r]内的数都≥mid,与初始mid的位置无关
    if (l < j)        //如果[l, j]是一个合法区间,则继续排序
        quick_sort(a_, l, j);
    if (r > i) //如果[i, r]是一个合法区间,则继续排序
        quick_sort(a_, i, r);
}
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
    }
    quick_sort(a, 1, n);
    for (int i = 1; i <= n; i++)
    {
        printf("%d ", a[i]);
    }
    return 0;
}

归并排序#

归并排序(merge sort)是一种采用了 分治 思想的排序算法。

解决方案#

#include <iostream>
#include <cstdio>
using namespace std;
const int maxn = 100500;
int n;
int a[maxn];
void merge_sort(int a_[], int l, int r)
{
    int mid = (l + r) >> 1; //取区间中点,左右子区间分别排序
    int len = r - l + 1;
    if (l < mid)
        merge_sort(a_, l, mid);
    if (r > mid + 1)
        merge_sort(a_, mid + 1, r);
    int tmp[len];
    int i = l, j = mid + 1, k = 0;
    while (i <= mid && j <= r) //将两个有序数组合并,保存在临时数组tmp中
        tmp[k++] = a_[i] < a_[j] ? a_[i++] : a_[j++];
    while (i <= mid)
        tmp[k++] = a_[i++];
    while (j <= r)
        tmp[k++] = a_[j++];
    for (i = 0; i < len; i++) //将tmp数组中的临时有序序列传回a_数组
    {
        a_[l + i] = tmp[i];
    }
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
    }
    merge_sort(a, 1, n);
    for (int i = 1; i <= n; i++)
    {
        printf("%d ", a[i]);
    }
    return 0;
}

例题#

洛谷 P1309 | [NOIP2011 普及组] 瑞士轮#

请参阅#

【OI考古】基础算法 | 排序
https://blog.vonbrank.com/posts/oi-basic-algorithm-sort/
作者
Von Brank
发布于
2021-03-20
许可协议
CC BY-NC-SA 4.0