歸并排序是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法（Divide and Conquer）的一個(gè)非常典型的應(yīng)用。將已有序的子序列合并，得到完全有序的序列；

首先來(lái)練習(xí)一下將兩個(gè)有序的數(shù)組，合并成一個(gè)有序的數(shù)組

void mergeArray(int a[], int n, int b[], int m ,int c[]) {int i ,j , k;i = j = k = 0;while (i < n&&j < m){if (a[i]>b[j]){c[k++] = b[j++];}else{c[k++] = a[i++];}}while (i < n)c[k++] = a[i++];while (j < n)c[k++] = b[j++]; }

數(shù)組：3，1，2，6，9

將數(shù)組從中間位置看成兩個(gè)無(wú)序的數(shù)組，然后再將左右兩個(gè)無(wú)序的數(shù)組，

再將左右兩個(gè)無(wú)序的數(shù)組再?gòu)闹虚g分開(kāi)，有變成兩個(gè)無(wú)序的數(shù)組。。。。

就變成了遞歸的調(diào)用。最后再一次合并數(shù)組

#include<iostream>using namespace std;void merge(int sore[],int temp[],int start, int mid,int end) {int i = start;int j = mid+1;int k = 0;while(i<=mid&&j<=end){if(sore[i] >sore[j])temp[k++] = sore[j++];elsetemp[k++] = sore[i++];}while(i <= mid)temp[k++] = sore[i++];while(j <= end)temp[k++] = sore[j++];for(i = 0;i<K;i++)sore[start + i] = temp[i]; }void mergeSort(int sore[],int temp[],int start,int end) {if(start < end){int min = (start + end)/2;mergeSort(sore,temp, start,mid);mergeSort(sore,temp,mid+1,end);merge(sore,temp,start,mid,end); } }int main() {int a[5] = {3,1,2,6,9};int b[5];mergeSort(a,b,0,4);for(int i = 0;i < 5;i++){printf("%d ", a[i]);} }

?歸并排序的形式就是一棵二叉樹(shù)，它需要遍歷的次數(shù)就是二叉樹(shù)的深度，而根據(jù)完全二叉樹(shù)的可以得出它的時(shí)間復(fù)雜度是O(n*log₂n)。

因?yàn)橐獎(jiǎng)?chuàng)建一個(gè)臨時(shí)的數(shù)據(jù)所以空間復(fù)雜度為O(N),復(fù)雜度比較復(fù)雜，是一種穩(wěn)定的排序。

轉(zhuǎn)載于:https://www.cnblogs.com/xiaoma123/p/5220353.html

總結(jié)

以上是生活随笔為你收集整理的算法四：归并排序的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。