归并排序(cc++)

文章目录

• • 一：归并排序简单介绍
  • 二：归并排序代码实现
  • 三：归并排序算法应用

一：归并排序简单介绍

一：原理介绍：

  1. 传统排序： 在现实生活当中对一串数字进行排序相信大家的传统思维都是很简单的，我们只要首先找到数组A当中最小的一个数字，然后放入到数组B中，然后再在剩下的数组A当中找到第二个小的数字放到数组B当中，这样直到数组A被逐个拿空我们就可以得到一个排好序的数组B了.
  2. 归并排序： 相对于普通排序而言，归并排序讲究的原理就是分治，即分开治理。即先将一个数组分成两半，再先分别处理其中的两半，处理好了之后再进行一个合并回归成一个的过程.
   空间复杂度： 需要一个同样大小数组储存分开的数组 : O(n)
   时间复杂度： 不断二分最终可以分为log2n层，每层n个数。 O(nlog2n)

二：归并过程：

  1. 将原有数组进行分离

  2. 将已经分离数组处理好

  3. 将处理好的分离数组合并

  4. 过程图

二：归并排序代码实现

  1. 将原有数组进行分离代码

void merge_sort(int s[],int l,int r){//s[]要排序的数组,l和r分别代表其要排序的区间
    int mid=(l+r)/2;
}

  2. 将已经分离数组处理

void merge_sort(int s[],int l,int r){
    merge_sort(s,l,mid),merge_sort(s,mid+1,r); //按照区间调用自身就可以处理
}

  3. 将处理好的分离数组合并代码

void merge_sort(int s[],int l,int r){
    int tmp[N],top=0; //原有部分的s[l,mid]  s[mid+1,r]已经处理将合并的数组用tmp[]保存

    int i=l,j=mid+1;//分别代表s[l,mid],s[mid+1,r]的起始位置坐标
    while(i<=mid&&j<=r){  //按顺序进行比较直到一个为空
        if(s[i]<s[j]) tmp[top++]=s[i++];
        else tmp[top++]=s[j++];
    }

    while(i<=mid) tmp[top++]=s[i++];//如果s[l,mid]部分还有剩余，全部直接放入tmp[]当中
    while(j<=r) tmp[top++]=s[j++];//如果s[mid+1,r]部分还有剩余，全部直接放入tmp[]当中

    for(int k=l,p=0;k<=r;k++,p++) s[k]=tmp[p]; //将合并完成的结果重新放回到原来的s[]数组当中
}

  4. 总代码

void merge_sort(int s[],int l,int r){
    if(l>=r) return; //二分到最小的区间只有一个数字后直接返回

    int mid=(l+r)/2;

    merge_sort(s,l,mid),merge_sort(s,mid+1,r);

    int tmp[N],top=0;
    int i=l,j=mid+1;
    while(i<=mid&&j<=r){
        if(s[i]<s[j]) tmp[top++]=s[i++];
        else tmp[top++]=s[j++];
    }
    while(i<=mid) tmp[top++]=s[i++];
    while(j<=r) tmp[top++]=s[j++];
    for(int k=l,p=0;k<=r;k++,p++) s[k]=tmp[p];
}

三：归并排序算法应用

  1. 调用归并排序结果展示