所謂歸并排序，其實就是將一個數(shù)組分成等分兩個相等的數(shù)組，然后對這兩個數(shù)組都做同樣的排序操作，再將兩個數(shù)組結(jié)合起。實際是一個遞歸的過程 那么這個結(jié)合是怎么樣的操作？ 舉例左數(shù)組為經(jīng)過排序操作等于【3，4】，右數(shù)組等于【1，2】，那么 這個數(shù)組本應(yīng)是【3，4，1，2】，如何使之變成【1，2，3，4】呢？ 事實上，這是兩個有序的數(shù)組，我們只須不斷地比較兩個數(shù)組各自的第一個，取出最小的加入新數(shù)組，直到兩個數(shù)組再也沒有元素。這樣就完成了排序
a=[6,2,3,9,2,1,5,6,19,87,65,65,21,35,75,82,59,62]def merge(left,right): ret=[] j=0 k=0 while(j<len(left) and k<len(right)): if left[j]<right[k]: temp=left[j] j+=1 else: temp=right[k] k+=1 ret.append(temp) while(j<len(left)): ret.append(left[j]) j+=1 while(k<len(right)): ret.append(right[k]) k+=1 return retdef mergeSort(a): if len(a)<2: return a l=len(a) left=a[:l/2] right=a[l/2:] return merge(mergeSort(left),mergeSort(right))PRint mergeSort(a)新聞熱點
疑難解答
