归并排序算法

归并排序

分治

  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/]