2020-1024=996：归并排序！

dreams5678

今天给大家分享排序算法里面的另外一种排序算法：归并排序!

. O; D9 P) m9 O# r* _6 Q* |

0 g- A  @9 e# C4 h) i% p

一、归并排序：

1、归并排序操作的核心思想：

a、确定分界点:mid=(l+r)/2

b、递归排序左边和右边(排完左右两边的数，就会成为两个有序的序列了)

c、归并（把上面的两个有序序列合并成一个有序的序列，用一个简单的词来说，就是合二为一！）

# ?; B* `3 v. S5 k3 ~6 z

2、举例：

比如上图我们有两组已经排好的序列数字，我们要进行第三步合并，该如何进行呢?思路如下：

a、这里先定义一个空的数组res，它主要是为了临时存放合并序列排序好的数字；我们从图中可以看到，第一个序列指针i指向数字1，第二序列指针j指向2，这个时候我们要比较两个数字的大小,小的数字就放到临时数组res里面去，这里我们明显知道数字1小于2，所以把1放到临时数组res里去

0 Y! l' j9 {" Z& W) m( j

b、然后指针i往下移动，如下图所示,再次进行比较，明显发现指针j指向的数字2更小，把它放到res里面去，然后指针j往下移动，指针i不动，后面依次类推

c、如下图所示，两个指针都指向了数字5，如果遇到两个数字一样的话，一般是把第一个序列的数字放到临时数组res里面去，这点稍微要注意一下

d、最后把临时数组里面的是数字放到原来的数组里面去

注意：一个算法稳定，并不能说它的时间效率是稳定的；这里的稳定是说两个序列中有两个数是相同的，如果在排完序之后，他们的位置还是没有发生变化的话，那么这个排序就是稳定的，反之亦然!

3、归并排序的平均时间复杂度的计算推导:

从图片的纵性来分析，当拆解到1的时候，这个时候什么数等于n除于它等于1，通过计算，我们知道是logn，然后再从横向分析，我们要最多比较n个数字，所以归并排序的时间复杂度就是：nlogn

二、代码示例：

代码：

#include <iostream>
using namespace std;
const int N = 1e5 + 10;
7 L% J3 m1 K' x3 L4 Kint n;
int q[N], tmp[N];

void merge_sort(int q[],int l, int r)
{
5 w9 ]: ^' Z4 V if(l>=r)return;//判断序列中是否为空或者只有一个数字，如果是的话，我们就不用排序了
//确定分界点
int mid = l + r >> 1;
5 E- M8 ~  v5 |& ~4 U //递归处理
merge_sort(q,l,mid);
0 }  q2 [* P- V% K: X6 G merge_sort(q,mid+1,r);
//定义双指针
int k =0,i = l, j= mid+1;
//归并处理
while(i <= mid && j <= r)
/ ~% ], u  B- q0 @% b  if(q < q[j])tmp[k++] = q[i++];
else
6 l- z- ~$ \( q  tmp[k++] = q[j++];
1 [) Y3 w; {* v: X //把源数组中剩余的数字（注意这里的数字一定是最小的)放到临时数组后面去
( k* O8 d" d) @- S while(i <= mid)tmp[k++] = q[i++];
0 C  ^0 |) B) ]) \# c" W3 l3 u3 c while(j <= r)tmp[k++] = q[j++];
8 m) ~$ b# h. Y' r/ @, l% W4 @ //把临时数组中排好序的数字放到源数组中去
, P: L; G, t' u/ O9 j( U for(i = l, j =0;i<=r;i++,j++)q=tmp[j];
}

# o& B8 u: w7 u) ^3 H- b& T
% r/ A  j' a7 Q" t9 K. Vint main()
{
" ?6 M, B! d) r9 x+ W# _ scanf("%d",&n);
$ P  [/ H7 g3 f; _; n; j for(int i = 0;i<n;i++)
{
  scanf("%d",&q);
4 o& C) f: M: I. u1 X0 O; I }
4 a7 ]+ v" o5 |+ L) V1 a+ g merge_sort(q,0,n-1);
for(int i = 0; i<n;i++)
{
: F( l! r* H( p  printf("%d ",q);
}
return 0;
8 E. Y# ^3 m* ?% Q
* l7 N2 l# p: o7 p  \9 r9 ]5 _
}

4 |3 ]8 M4 C# t1 T# V, {" {

shapeofyou888

2020-1024=996,哈哈