归并排序算法

发表于 分类于 阅读次数：
本文字数： 1.2k 阅读时长 ≈ 1 分钟

归并排序

分治

  1. 确定分界点，mid=(l+r)/2
  2. 递归排序左边和右边
  3. ⭐归并,合二为一

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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, tmp[r - l + 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(k = 0, i = l; i <= r; k++, i++) q[i] = tmp[k];
}

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
#include <iostream>
using namespace std;

const int N=1e5+10;
int q[N],temp[N];
int n;
inline 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;j++,i++) 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;
}

例题

(合并两个有序单链表)[https://leetcode-cn.com/problems/merge-two-sorted-lists/]