排序

一、快速排序

• 核心思想——分治法 ^0ea077

• 步骤

• 确定分界点：
  1. q[l]、q[(l+r)/2]、q[r]、随机
  2. 调整区间：分为两份，左边大（小），右边小（大）
  3. 递归处理左右两边的区间
• 调整区间：
  1. 双指针（分别指向数组的两边，往中间走，直到相遇）

#include <iostream>
using namespace std;
const int N = 1e6 + 10;
int q[N];
int n;

void qsort(int q[], int l, int r)
{
    if (l >= r)
        return;
    int s = q[l + r >> 1], i = l - 1, j = r + 1;
    while (i < j)
    {
        do
            i++;
        while (q[i] < s);
        do
            j--;
        while (q[j] > s);
        if (i < j)
            swap(q[i], q[j]);
    }

    qsort(q, l, j);
    qsort(q, j + 1, r);
}

int main()
{
    int n;
    scanf("%d", &n);

    for (int i = 0; i < n; i++)
        scanf("%d", &q[i]);

    qsort(q, 0, n - 1);

    for (int i = 0; i < n; i++)
        printf("%d ", q[i]);

    return 0;
}

二、归并排序

• 核心思想——分治

• 步骤

• 找分界点：(l + r)/2
• 递归排序左边右边
• 归并——合二为一

#include <iostream>
using namespace std;

const int N = 1000010;
int n;
int q[N], temp[N];

void merge_sort(int q[], int l, int r)
{
    if (l >= r)
    {
        return;
    }

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

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &q[i]);
    }

    merge_sort(q, 0, n - 1);
    for (int i = 0; i < n; i++)
    {
        printf("%d ", q[i]);
    }
    return 0;
}