ac_787归并排序

题目描述

题目大意&链接

给定一个长度为n的乱序数列，用归并排序将数列排成有序数列。

输入输出样例：
输入:

5
3 1 2 4 5

输出：

1 2 3 4 5

详情：ac_787归并排序

解题思路

归并排序也是采用分治思想，最开始数列每个元素单独作为一个子序列，然后相邻子序列两两归并，最后归并成一个子序列。

1. 确定分界点mid：

   int mid = l + r >> 1;

2. 递归排序mid的左右子区间：

   merge_sort(q, l, mid), merge_sort(q, mid + 1, r);

3. 递归到mid左右区间只有一个元素后开始归并：

   //k为temp数组的索引，i取左边子序列的左端点，j取右边子序列的左端点
   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++];
   
   //将temp数组赋值给q数组
   for(i = l, j = 0; i <= r; i++, j++) q[i] = temp[j];

完整代码

#include<iostream>

using namespace std;

const int N = 1e6 + 10;

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);
    
    //k为temp数组的索引，i取左边子序列的左端点，j取右边子序列的左端点
    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++];
    
    //将temp数组赋值给q数组
    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;
}

时间和空间复杂度

时间复杂度：O(nlogn)
空间复杂度：O(n) 开辟了长度为n的temp数组