归并排序

归并排序(MERGE-SORT):是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。归并排序是一种稳定的排序方法。

时间复杂度:O(n log n
空间复杂度:T(n)
发明者:约翰·冯·诺伊曼
归并排序
归并排序 归并排序

输入:

8

23 13 49 6 31 19 28 4

输出:

4 6 13 19 23 28 31 49

代码:

 

#include<iostream>

using namespace std;

//   left  下标起点
//   right  下标终点
void merge_sort(int left,int right,int a[],int keep[])
{
    if(left>=right)
    {
        return;
    }
    int mid=(left+right)/2;//数组分成两部分

    merge_sort(left,mid,a,keep);//左递归
    merge_sort(mid+1,right,a,keep);//右递归

    int i=left,j=mid+1,k=0;//  i为左边的数 , j为右边的数 , k为keep数组的下标
    while(i<=mid && j<=right)
    {
        if(a[i]<=a[j])// 哪边的数小就存入keep中
        {
            keep[k++]=a[i++];
        }
        else
        {
            keep[k++]=a[j++];
        }
    }
    //将没有存入keep数组中的数存进去
    while(i<=mid)
    {
        keep[k++]=a[i++];
    }
    while(j<=right)
    {
        keep[k++]=a[j++];
    }
    //将已排序好的数组再赋值给原数组
    for(i=0;i<k;i++)
    {
        a[left+i]=keep[i];//left是针对右边的数
    }
}
int main ()
{
    int a[100];
    int keep[100];
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    merge_sort(0,n-1,a,keep);
    //输出
    for(int i=0;i<n;i++)
    {
        cout<<a[i]<<" ";
    }
    return 0;
}

 

 

 
上一篇:keep alive实现原理


下一篇:vue的keep-alive组件使用详解(亲测可用)