2020-1024=996：归并排序！

1.png (709.8 KB, 下载次数: 1)

下载附件  保存到相册

2020-10-26 10:50 上传

一、归并排序：

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

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

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

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

2、举例：

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

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

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

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

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

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

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

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

二、代码示例：

代码：

' u6 X% n# g# n6 C8 J else& f- X6 F$ `1 \. V5 K+ r
  tmp[k++] = q[j++];
- n0 `+ n6 r& N- c7 }2 x //把源数组中剩余的数字（注意这里的数字一定是最小的)放到临时数组后面去0 E& L4 a0 u. @) U
while(i <= mid)tmp[k++] = q[i++];" ?. z2 j1 V+ F+ W9 M
while(j <= r)tmp[k++] = q[j++];
) _3 T, d! a* r4 f //把临时数组中排好序的数字放到源数组中去  g# ~* j. u& S8 ], d% i5 V% D" g
for(i = l, j =0;i<=r;i++,j++)q=tmp[j];
  R3 c4 Z0 l( `$ f. @3 d) A}2 z1 u1 E- Q& S
% U7 r& S' _% R. s4 Q

9 F* m9 D4 W! d* L1 o. nint main()
3 k, x& [; o( G4 w7 S, {4 q3 X' j{
9 w) g# c# b5 V7 \: u  H% q1 P. J scanf("%d",&n);
2 u: l+ O% \( s; @: n& e3 }- u( y for(int i = 0;i<n;i++)
1 F% ]0 t* p2 f. U1 B/ m {
! Y" l1 Z# M0 a1 f  o' k" K  scanf("%d",&q);5 a% K! X6 y! {2 v# K' Y  i
}
3 O( G, p/ X$ ]: z2 @ merge_sort(q,0,n-1);
) e* x% w5 B+ w; R2 K% Y for(int i = 0; i<n;i++)
" ]" c& n7 l" @' B1 D- N {' c1 N  {! V. U; W
  printf("%d ",q);( N* U+ I. B  W' \$ G. p; R4 x
}
8 F  V5 y# p% D$ B/ c return 0;% E$ z- W3 V$ d! \+ R& G
- v9 ~. w7 u2 G

, F+ J' \  N# s- K, h: a0 O}

9.png (24.26 KB, 下载次数: 1)

下载附件  保存到相册

2020-10-26 10:50 上传

: p" y2 ]- m; r+ I! w# l3 R6 `