快速排序 归并排序

快速排序：

• 快排思想：分治思想

  1. 选择基准值，一般该基准值为x = q[(l +r) >> 1] (为了避免有序的情况下，子问题规模依旧较大的问题)
  2. 把待排序列分为两个区间，一区间小于该基准值，另一区间大于该基准值。
  3. 递归的对两个区间进行快速排序，直到区间为空或者只有一个元素。

快排板子：

#include <iostream>

using namespace std;

const int N = 1000010;

int q[N];

void quick_sort(int q[], int l, int r)
{
    //递归的终止情况
    if (l >= r) return;
     // 分成子问题
    int i = l - 1, j = r + 1, x = q[l + r >> 1];
    while (i < j)
    {
        do i ++ ; while (q[i] < x);
        do j -- ; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
    }
    // 递归处理子问题
    quick_sort(q, l, j);
    quick_sort(q, j + 1, r);
}

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

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

    quick_sort(q, 0, n - 1);

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

    return 0;
}

归并排序：

• 归并思想：分治思想

  1. 选择基准值，一般该基准值为x = q[(l +r) >> 1]
  2. 递归调用merge_sort(arr ,l ,mid)和merge(arr,mid+1,r)
  3. 把待排序列分为两个区间
  4. 把两个区间排完序之后再合并

归并板子：

#include <iostream>

using namespace std;

const int N = 1e6 + 10;

int a[N], tmp[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]) tmp[k ++ ] = q[i ++ ];
        else tmp[k ++ ] = q[j ++ ];
    while (i <= mid) tmp[k ++ ] = q[i ++ ];
    while (j <= r) tmp[k ++ ] = q[j ++ ];

    for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}

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

    merge_sort(a, 0, n - 1);

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

    return 0;
}