1.復(fù)雜度與穩(wěn)定性

算法時(shí)間復(fù)雜度

最壞情況O(NlogN)

最好情況O(NlogN)

平均情況O(NlogN)

空間復(fù)雜度O(N)   注：歸并排序需要?jiǎng)?chuàng)建一個(gè)與原數(shù)組相同長度的數(shù)組來輔助排序

穩(wěn)定性：穩(wěn)定排序

2.過程介紹

歸并排序的核心思想是將兩個(gè)有序的數(shù)列合并成一個(gè)大的有序的序列。通過遞歸，層層合并，即為歸并，歸并排序的算法效率僅次于快速排序，是一種穩(wěn)定的算法，需要建立兩倍的數(shù)組空間，一般用于對(duì)總體而言無序，但是各子項(xiàng)又相對(duì)有序【并不是完全亂序】的情況比較適用。

a)申請(qǐng)空間，使其大小為兩個(gè)已經(jīng)排序序列之和，該空間用來存放合并后的序列

b)設(shè)定兩個(gè)指針，最初位置分別為兩個(gè)已經(jīng)排序序列的起始位置

c)比較兩個(gè)指針?biāo)赶虻脑?，選擇相對(duì)小的元素放入到合并空間，并移動(dòng)指針到下一位置

重復(fù)步驟c直到某一指針超出序列尾

將另一序列剩下的所有元素直接復(fù)制到合并序列尾

3.圖示過程

第一次排序?qū)?shù)據(jù)分為“兩個(gè)”一組，組內(nèi)順序，其次再逐個(gè)的將各組進(jìn)行整合，最終完成歸并排序

4. 相關(guān)的代碼

#include <iostream>
#include <math.h>
using namespace std;
 
void merge(int arr[],int l,int mid,int r) {
    int aux[r-l+1];//開辟一個(gè)新的數(shù)組，將原數(shù)組映射進(jìn)去
    for(int m=l; m<=r; m++) {
        aux[m-l]=arr[m];
    }
 
    int i=l,j=mid+1;//i和j分別指向兩個(gè)子數(shù)組開頭部分
 
    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防止越界
            //對(duì)局部：arr[i...sz-1]和arr[i+sz.....i+2*sz-1]進(jìn)行排序
            merge(arr,i,i+sz-1,min(i+sz+sz-1,n-1));    //min函數(shù)防止越界
        }
    }
 
}
 
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;
}