快速排序和归并排序

快速排序

快排模板(以中点为为分界)

快排属于分治算法，分治算法都有三步：

1. 分成子问题

2. 递归处理子问题

3. 子问题合并

#include <iostream>

using namespace std;

const int N = 100010;

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. 有数组q, 左端点 l, 右端点r

2. 确定划分边界 x

3. 将 q 分为 <=x 和 >=x 的两个小数组

4. i的含义：i之前的元素都小于等于x,即q[l...i-1] <= x

5. j的含义：j之后的元素都大于等于x,即q[j+1...r] >= x

6. 结论: while循环结束后,q[l...j] <= x, q[j+1...r] >= x

归并排序

#include <iostream>

using namespace std;

const int N = 1e5 + 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;
}

时间复杂度为O(nlogn)

总结归并思路

1. 有数组 q, 左端点 l, 右端点 r

2. 确定划分边界 mid

3. 递归处理子问题 q[l..mid], q[mid+1..r]

4. 合并子问题
   1. 主体合并，至少有一个小数组添加到tmp数组中
   2. 收尾，可能存在剩下的一个小数组的尾部直接添加到tmp数组中
   3. 复制回来，将tmp数组中的值复制回原数组