【C/C++】排序算法之归并排序_c++归并排序

归并排序

一、归并排序是什么？

归并排序（Merge Sort）是建立在归并操作上的一种有效，稳定的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

时间复杂度 O(n log n)
空间复杂度 T（n)

简而言之，归并排序是将大问题拆分成几个小问题进行解决（分）再将解决后的小问题合并起来（治）最终解决了整个复杂的问题

二、基本实现

核心步骤：

1. 拆分
2. 合并

1.合并（治）

代码解析：

在这部分函数里，我们将已经排好序的各部分序列进行合并，此时可以想象，有两个已经排好序的序列A和B，要将A和B进行合并，但是问题是，A和B之间并没有排好序，换句话说，我们还要将A和B合并在一起的序列再排个序。
1

要实现A和B之间排序，我们就需要一个临时数组，以存放正确序列
首先，以mid为中心，A序列以low为起点，mid为终点；B序列以mid+1为起点，high为终点。

之后，将A，B序列中的数字进行比较，小的放在临时数组里，这样不断比较下来，临时数组就存放了正确的从小到大排列的序列。

最后，如果A或者B序列中仍有残留的数字，则之间将这些数字接到临时数组的末端即可。然后将临时数组中的数字放到起始数组中，此时，我们一开始传入的数组就已经排好序了。
1
2
3
4
5
6

void merge(int *a,int low,int mid,int high)
{
   
    int *tmp=(int*)malloc((high-low+1)*sizeof(int));//开辟一个临时数组
    int k=0;
    int i=low;
    int j=mid+1;
    while(i<=mid&&j<=high)
    {
   
        if(a[i]<a[j]) tmp[k++]=a[i++];
        else tmp[k++]=a[j++];
    }
    if(i==mid+1)
        while(j<=high)
            tmp[k++]=a[j++];
    if(j==high+1)
        while(i<=mid)
            tmp[k++]=a[i++];
    for(j=0,i=low;j<k;i++,j++)
    a[i]=tmp[j];
    return;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

2.排序（分）

代码解析：

这部分比较精简，我们需要取序列的中间值mid，之后再将序列进行分割，这部分用递归完成&