【OI考古】基础算法 | 排序

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

几种排序算法的比较：

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

题目描述

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

输入格式

第 $1$ 行为一个正整数 $N$ ，第 $2$ 行包含 $N$ 个空格隔开的正整数 $a_i$ ，为你需要进行排序的数，数据保证了 $a_i$ 不超过 $10^9$ 。

输出格式

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

输入输出样例

输入 #1

1 2	5 4 2 4 5 1

输出 #1

1 2 4 4 5

说明/提示

对于 $20\%$ 的数据，有 $N\leq 10^3$ ；

对于 $100\%$ 的数据，有 $N\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;
}