歸併排序

• 2020 年 4 月 16 日
• 筆記
• 演算法

歸併排序（MERGE-SORT）是利用歸併的思想實現的排序方法，該演算法採用經典的分治（divide-and-conquer）策略（分治法將問題分(divide)成一些小的問題然後遞歸求解，

而治(conquer)的階段則將分的階段得到的各答案”修補”在一起，即分而治之)。

#include<bits/stdc++.h>
using namespace std;
const int N=1000010;
int q[N];
int tmp[N];
void merge_sort(int q[],int l,int r)
{
    if(l>=r) return;
    int mid=(l+r)>>1;
    merge_sort(q,l,mid);
    merge_sort(q,mid+1,r);
    int i=l,j=mid+1,k=0;
    while(i<=mid&&j<=r)
    {
        if(q[i]<q[j]) tmp[k++]=q[i++];
        else tmp[k++]=q[j++];
        
    }
    while(i<=mid) tmp[k++]=q[i++];
    while(j<=r) tmp[k++]=q[j++];
    for(int i=l,j=0;i<=r;i++,j++)
    q[i]=tmp[j];
    
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    scanf("%d",&q[i]);
    merge_sort(q,0,n-1);
    for(int i=0;i<n;i++)
    printf("%d ",q[i]);
    
    
}

簡而言之、就是將一個整體得數組，分為兩個小段，兩個指針分別放在第一個數組，第二個數組上，依次比較指針所指向的數字大小，

將小的放在tmp新數組中，指針繼續移動、直到將兩個數組全部讀進tmp中、再將tmp放回最原始的數組中。