感謝博客https://blog.csdn.net/a130737/article/details/38228369

歸并排序的時間復雜度為o(nlgn)，空間復雜度為o(n)。是一種采用分治思想的排序方法。

邏輯分析：

假設輸入數(shù)組a[] = { 2, 1, 4, 5, 3, 8, 7, 9, 0, 6 }。

首先將數(shù)組二分成兩個數(shù)組left[]={ 2, 1, 4, 5, 3}，right=?{8, 7, 9, 0, 6 }。

再將left和right兩個數(shù)組二分，一直到每一個單獨元素為一個數(shù)組。

{ 2, 1, 4}，{5, 3}，{8, 7, 9}，{0, 6 }。

{2，1}，{4}，{5}，{3}，{8,7}，{9}，{0}，{6}。

{2}，{1}，{4}，{5}，{3}，{8}，{7}，{9}，{0}，{6}。

然后比較數(shù)組{2}，{1}，將小的元素放在左邊，然后合并成一個新數(shù)組a1[]={1,2}

繼續(xù)比較數(shù)組{4}，{5}，將小的元素放在左邊，然后合并成一個新數(shù)組a2[]={4,5}

一直比較完畢，此時共有5個數(shù)組a1[]={1，2}，a2[]={4，5}，a3[]={3，8}，a4[]={7，9}，a5[]={0，6}。

再來比較數(shù)組{a1[]=1，2}，a2[]={4，5}，由于a1[0]=1<a2[0]=4，所以將a1[0]賦值到b1[0]中，由于a1[1]=2<a2[0]=4，所以將a1[1]放入b1[1]中，再把a2[]中元素存入b1中，數(shù)組b1[]={1，2，4，5}

同理數(shù)組b2[]={3，7，8，9}

數(shù)組b3[]={0,6}

比較數(shù)組b1,b2，存入到數(shù)組a1[]={1,2,3,4,5,7,8,9}

b3數(shù)組存入到a2[]={0,6}

比較數(shù)組a1[]和a2[],存入數(shù)組到a[]={0,1,2,3,4,5,6,

#include<iostream> #include<cstdlib>using namespace std;void merge(int a[], int *left, int leftcount, int *right,int rightcount) {int i, j, k;i = 0, j =0, k = 0;while (i < leftcount&&j < rightcount){if (left[i] < right[j])a[k++] = left[i++];else a[k++] = right[j++];}while (i < leftcount)a[k++] = left[i++];while (j < rightcount)a[k++] = right[j++]; }void mergeSort(int a[], int n) {int mid=n/2;if (n < 2) return;int *left = new int[mid];int *right = new int[n - mid ];for (int i = 0; i < mid; i++)left[i] = a[i];for (int j = mid ; j < n; j++)right[j-mid] = a[j];mergeSort(left, mid);mergeSort(right, n - mid);merge(a,left,mid,right,n-mid);delete[] left;delete[] right;}int main() {int a[] = { 2, 1, 4, 5, 3, 8, 7, 9, 0, 6 };int length = 10; mergeSort(a, length);for (int i = 0; i < length; i++)cout << a[i] << " ";system("pause");return 0; }

7,8,9}

總結

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

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