說一說歸并排序

歸并排序：歸并排序（英語：Merge sort，或mergesort），是創(chuàng)建在歸并操作上的一種有效的排序算法，效率為O(n log n)。1945年由約翰·馮·諾伊曼首次提出。該算法是采用分治法（Divide and Conquer）的一個(gè)非常典型的應(yīng)用，且各層分治遞歸可以同時(shí)進(jìn)行。

 

歸并排序的核心思想是將兩個(gè)有序的數(shù)列合并成一個(gè)大的有序的序列。通過遞歸，層層合并，即為歸并。

 大數(shù)據(jù)培訓(xùn),云培訓(xùn),數(shù)據(jù)挖掘培訓(xùn),云計(jì)算培訓(xùn),高端軟件開發(fā)培訓(xùn),項(xiàng)目經(jīng)理培訓(xùn)

 


如圖，從下到上，每一步都需要將兩個(gè)已經(jīng)有序的子數(shù)組合并成一個(gè)大的有序數(shù)組，如下是實(shí)現(xiàn)合并的具體代碼，請(qǐng)讀者細(xì)細(xì)體會(huì)

大數(shù)據(jù)培訓(xùn),云培訓(xùn),數(shù)據(jù)挖掘培訓(xùn),云計(jì)算培訓(xùn),高端軟件開發(fā)培訓(xùn),項(xiàng)目經(jīng)理培訓(xùn)

 1 void merge(int arr[],int l,int mid,int r) 2 { 3     int aux[r-l+1];//開辟一個(gè)新的數(shù)組，將原數(shù)組映射進(jìn)去  4     for(int m=l;m<=r;m++) 5     { 6