疯子的算法总结(六) 复杂排序算法 ① 归并排序 merge

归并排序采取了分治的思想，每次分别排左半边和右半边，不断递归调用自己，直到只有一个元素递归结束，开始回溯，调用merge函数，合并两个有序序列，再合并的时候每次给末尾追上一个最大int这样就不怕最后一位的数字不会被排序。

#include <bits/stdc++.h>

using namespace std;

void merge(int a[],int n,int left ,int mid,int right);

void merge_sort(int a[],int n,int left,int right);

const int Maxn=5e5;

const int Sentinel=0x3f3f3f3f;

int L[Maxn/2],R[Maxn/2];

int cnt;

int main()

{

    int n;

    int a[1000];

    cin>>n;

    for(int i=0;i<n;i++) cin>>a[i];

    merge_sort(a,n,0,n);

    for(int i=0;i<n;i++) cout<<a[i]<<' ';

}

void merge(int a[],int n,int left ,int mid,int right)

{

    int n1=mid-left;

    int n2=right-mid;

    for(int i=0;i<n1;i++) L[i]=a[left+i];

    for(int i=0;i<n2;i++) R[i]=a[mid+i];

    L[n1]=R[n2]=Sentinel;

    int i=0,j=0;

    for(int k=left;k<right;k++)

    {

        cnt++;

        if(L[i]<R[j]){

            a[k]=L[i++];

        }

        else{

            a[k]=R[j++];

        }

    }

}

void merge_sort(int a[],int n,int left,int right)

{

    if(left<right)

    {

        int mid=(left+right)>>1;

        merge_sort(a,n,left,mid);

        merge_sort(a,n,mid+1,right);

        merge(a,n,left,mid,right);

    }

}

————————————————————————————————————————————

以上为实现原理，借助C++的merge函数可以简化merge_sort()代码。

#include <bits/stdc++.h>

using namespace std;

void merge_sort(int a[],int n,int left,int right);

const int Maxn=5e5;

int main()

{

    int n;

    int a[Maxn];

    cin>>n;

    for(int i=0;i<n;i++) cin>>a[i];

    merge_sort(a,n,0,n);

    for(int i=0;i<n;i++) cout<<a[i]<<' ';

}

void merge_sort(int a[],int n,int left,int right)

{

    if(left<right)

    {

        int mid=(left+right)>>1;

        merge_sort(a,n,left,mid);

        merge_sort(a,n,mid+1,right);

        merge(a+left,a+mid+1,a+mid+1,a+right,a+left);

    }

}

巴特西

疯子的算法总结(六) 复杂排序算法 ① 归并排序 merge_sort()

最新文章

热门文章