圖解Java經(jīng)典算法歸并排序的原理與實現(xiàn)

第圖解Java經(jīng)典算法歸并排序的原理與實現(xiàn)目錄歸并排序算法原理動圖演示代碼實現(xiàn)復雜度

歸并排序

歸并排序主要分成兩部分實現(xiàn)，分、合兩部分，分是把數(shù)組分成兩半，再遞歸的對子數(shù)組進行分操作，直到分成一個個單獨的數(shù)。合是把兩個數(shù)組合并為有序數(shù)組，在對有序數(shù)組進行合并，直到全部子數(shù)組合并為一個完整的數(shù)組。

算法原理

申請空間，使其大小為兩個已經(jīng)排序序列之和，該空間用來存放合并后的序列設定兩個指針，最初位置分別為兩個已經(jīng)排序序列的起始位置比較兩個指針所指向的元素，選擇相對小的元素放入到合并空間，并移動指針到下一位置重復步驟c直到某一指針超出序列尾將另一序列剩下的所有元素直接復制到合并序列尾

動圖演示

代碼實現(xiàn)

publicclassMergeSort{

//歸并所需的輔助數(shù)組

privatestaticComparable[]assist;

//比較v是否小于w

publicstaticbooleanless(Comparablev,Comparablew){

returnpareTo(w)

//數(shù)組元素交換位置

privatestaticvoidswap(Comparable[]a,inti,intj){

Comparabletemp;

temp=a[i];

a[i]=a[j];

a[j]=temp;

//排序

publicstaticvoidsort(Comparable[]a){

//初始化輔助數(shù)組

assist=newComparable[a.length];

intl=0;

inth=a.length-1;

sort(a,l,h);

privatestaticvoidsort(Comparable[]a,intl,inth){

if(h=l){

return;

//分組

intmid=l+(h-l)/2;

//分別對每組數(shù)據(jù)排序

sort(a,l,mid);

sort(a,mid+1,h);

//對數(shù)組進行歸并

merge(a,l,mid,h);

//對數(shù)組進行歸并

privatestaticvoidmerge(Comparable[]a,intl,intmid,inth){

//定義三個指針

inti=l;

intp1=l;

intp2=mid+1;

//遍歷，移動p1,p2指針，比較兩處索引的值,小的放到輔助數(shù)組的對應索引處

while(p1=midp2=h){

if(less(a[p1],a[p2])){

assist[i++]=a[p1++];

}else{

assist[i++]=a[p2++];

//遍歷數(shù)組，如果p1的指針沒有走完，則順序移動p1指針，把對應的元素放到輔助數(shù)組的對應索引處

while(p1=mid){

assist[i++]=a[p1++];

//遍歷數(shù)組，如果p2的指針沒有走完，則順序移動p2指針，把對應的元素放到輔助數(shù)組的對應索引處

while(p2=h){

assist[i++]=a[p2++];

//把輔助數(shù)組中的元素拷貝到原數(shù)組中

for(intj=l;jj++){

a[j]=assist[j];

}

publicclassMergeSortTest{

publicstaticvoidmain(String[]args){

Integer[]arr={5,6,3,1,8,7,2,4};

MergeSort.sort(arr);

System.out.println(Arrays.toString