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

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

歸并排序

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

算法原理

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

動圖演示

代碼實(shí)現(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ù)組進(jìn)行歸并

merge(a,l,mid,h);

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

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

//定義三個(gè)指針

inti=l;

intp1=l;

intp2=mid+1;

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

while(p1=midp2=h){

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

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

}else{

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

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

while(p1=mid){

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

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

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