算法 - 归并排序

2020-08-05 11:10:32

题目来源： https://www.acwing.com/problem/content/789/

描述：

给定你一个长度为n的整数数列。

请你使用归并排序对这个数列按照从小到大进行排序。

并将排好序的数列按顺序输出。

归并排序的思路：

  • 首先确定分界点，归并排序是以中间点划分，mid = left + right >> 1
  • 然后递归去划分只有一个的情况
  • 然后归并解决，利用双指针：
  • i指针指向左半部分最左边，j指针指向右半部分最左边，i = left, r = mid + 1。
  • 当i <= mid 并且 j <= right时， 如果q[i] <= q[j] 那么q[i]复制到辅助数组，i++, 否者复制q[j]到辅助数组， j++.
  • 必然有一个越界，把越界剩余的部分复制到辅助数组就行
  • 然后把排序好的数组再复制回原数组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

#include <iostream>

using namespace std;

const int N = 1e5;

int q[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;
    cin >> 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]);
}