归并排序算法实例详解

1.复杂度与稳定性

算法时间复杂度

最坏情况O(NlogN)

最好情况O(NlogN)

平均情况O(NlogN)

空间复杂度O(N)   注：归并排序需要创建一个与原数组相同长度的数组来辅助排序

稳定性：稳定排序

2.过程介绍

归并排序的核心思想是将两个有序的数列合并成一个大的有序的序列。通过递归，层层合并，即为归并，归并排序的算法效率仅次于快速排序，是一种稳定的算法，需要建立两倍的数组空间，一般用于对总体而言无序，但是各子项又相对有序【并不是完全乱序】的情况比较适用。

a)申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列

b)设定两个指针，最初位置分别为两个已经排序序列的起始位置

c)比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置

重复步骤c直到某一指针超出序列尾

将另一序列剩下的所有元素直接复制到合并序列尾

3.图示过程

第一次排序将数据分为“两个”一组，组内顺序，其次再逐个的将各组进行整合，最终完成归并排序

4. 相关的代码

#include <iostream>
#include <math.h>
using namespace std;
 
void merge(int arr[],int l,int mid,int r) {
    int aux[r-l+1];//开辟一个新的数组，将原数组映射进去
    for(int m=l; m<=r; m++) {
        aux[m-l]=arr[m];
    }
 
    int i=l,j=mid+1;//i和j分别指向两个子数组开头部分
 
    for(int k=l; k<=r; k++) {
        if(i>mid) {
            arr[k]=aux[j-l];
            j++;
        } else if(j>r) {
            arr[k]=aux[i-l];
            i++;
        } else if(aux[i-l]<aux[j-l]) {
            arr[k]=aux[i-l];
            i++;
        } else {
            arr[k]=aux[j-l];
            j++;
        }
    }
}
 
void merge_sort(int arr[],int n) {
    for(int sz=1; sz<=n; sz+=sz) {
        for(int i=0; i+sz<n; i+=sz+sz) { //i+sz防止越界
            //对局部：arr[i...sz-1]和arr[i+sz.....i+2*sz-1]进行排序
            merge(arr,i,i+sz-1,min(i+sz+sz-1,n-1));    //min函数防止越界
        }
    }
 
}
 
int main() {
    int a[8]= {70,50,30,20,10,70,40,60};
    int n=8;
    merge_sort(a,n);
    for(int i=0; i<n; i++) {
        cout<<a[i]<<" ";
    }
    return 0;
}