您好,登錄后才能下訂單哦!
這篇文章主要介紹“Java歸并排序舉例分析”,在日常操作中,相信很多人在Java歸并排序舉例分析問題上存在疑惑,小編查閱了各式資料,整理出簡(jiǎn)單好用的操作方法,希望對(duì)大家解答”Java歸并排序舉例分析”的疑惑有所幫助!接下來,請(qǐng)跟著小編一起來學(xué)習(xí)吧!
1.盡可能的一組數(shù)據(jù)拆分成兩個(gè)元素相等的子組,并對(duì)每一個(gè)子組繼續(xù)拆分,直到拆分后的每個(gè)子組的元素個(gè)數(shù)是1為止。
⒉將相鄰的兩個(gè)子組進(jìn)行合并成一個(gè)有序的大組。
3.不斷的重復(fù)步驟2,直到最終只有一個(gè)組為止。
類名 | Merge |
構(gòu)造方法 | Merge():創(chuàng)建Merge對(duì)象 |
成員方法 | 1.public static void sort(Comparable[] a):對(duì)數(shù)組內(nèi)的元素進(jìn)行排序 2.private static void sort(Comparable[] a,int lo,int hi):對(duì)數(shù)組a中從索引lo到索引hi之間的元素進(jìn)行排序 3.private static void merge(Comparable[] a,int lo,int mid,int hi):從索引lo到索引mid為一個(gè)子組,從索引mid+1到索引hi為另一個(gè)子組,把數(shù)組a中的這兩個(gè)子組的數(shù)據(jù)合并成一個(gè)有序的大組(從索引lo到索引hi) 4.private static boolean less(Comparable v,Comparable w):判斷v是否小于w 5.private static void exchange(Comparable[] a,int i,int j):交換a數(shù)組中,索引i和索引j處的值 |
成員變量 | private static ComParable[] assit:完成歸并操作需要的輔助數(shù)組 |
public class Merge { //輔助數(shù)組 private static Comparable[] assist; //對(duì)數(shù)組a中的元素進(jìn)行排序 public static void sort(Comparable[] a){ assist=new Comparable[a.length]; int lo=0; int hi=a.length-1; sort(a,lo,hi); } //對(duì)數(shù)組a中從lo到hi的元素進(jìn)行排序 private static void sort(Comparable[] a,int lo,int hi){ if(hi<=lo){ return; } int mid=lo+(hi-lo)/2; //對(duì)lo到mid之間的元素進(jìn)行排序 sort(a,lo,mid); //對(duì)mid+1到hi之間的元素進(jìn)行排序 sort(a,mid+1,hi); //對(duì)lo到mid這組數(shù)據(jù)和mid到hi這組數(shù)據(jù)進(jìn)行歸并 merge(a,lo,mid,hi); } //對(duì)數(shù)組中,從lo到mid為一組,從mid+1到hi為一組,對(duì)這兩組數(shù)據(jù)進(jìn)行歸并 public static void merge(Comparable[] a,int lo,int mid,int hi){ //lo到mid這組數(shù)據(jù)和mid+1到hi這組數(shù)據(jù)歸并到輔助數(shù)組assist對(duì)應(yīng)的索引處 int i=lo;//定義一個(gè)指針,指向assist數(shù)組中開始填充數(shù)據(jù)的索引 int p1=lo;//定義一個(gè)指針,指向第一組數(shù)據(jù)的第一個(gè)元素 int p2=mid+1;//定義一個(gè)指針,指向第二組數(shù)據(jù)的第一個(gè)元素 //比較左邊小組和右邊小組中的元素大小,哪個(gè)小,就把哪個(gè)數(shù)據(jù)填充到assist數(shù)組中 while(p1<=mid&&p2<=hi){ if(less(a[p1],a[p2])){ assist[i++]=a[p1++]; }else{ assist[i++]=a[p2++]; } } //把未填充的數(shù)據(jù)填到assist中 while(p1<=mid){ assist[i++]=a[p1++]; } while(p2<=hi){ assist[i++]=a[p2++]; } for(int index=lo;index<=hi;index++){ a[index]=assist[index]; } } //比較v元素是否小于w元素 private static boolean less(Comparable v,Comparable w){ return v.compareTo(w)<0; } //數(shù)組元素i和j交換位置 private static void exchange(Comparable[] a,int i,int j){ Comparable t=a[i]; a[i]=a[j]; a[j]=t; } } //測(cè)試代碼 class Test{ public static void main(String[] args) { Integer[] a={8,4,6,5,7,1,3,6,2}; Merge.sort(a); System.out.println(Arrays.toString(a)); } }
歸并排序是分治思想的最典型的例子,上面的算法中,對(duì)a[lo..hi]進(jìn)行排序,先將它分為a[lo..mid]和a[mid+1..hi]兩部分,分別通過遞歸調(diào)用將他們單獨(dú)排序,最后將有序的子數(shù)組歸并為最終的排序結(jié)果。該遞歸的出口在于如果一個(gè)數(shù)組不能再被分為兩個(gè)子數(shù)組,那么就會(huì)執(zhí)行merge進(jìn)行歸并,在歸并的時(shí)候判斷元素的大小進(jìn)行排序。
用樹狀圖來描述歸并,如果一個(gè)數(shù)組有8個(gè)元素,那么它將每次除以2找最小的子數(shù)組,共拆log8次,值為3,所以樹共有3層那么自頂向下第k層有2^k個(gè)子數(shù)組,每個(gè)數(shù)組的長(zhǎng)度為2^(3-k),歸并最多需要2^(3-k)次比較。因此每層的比較次數(shù)為2^k * 2^(3-k)=2^3,那么3層總共為3*2^3。
假設(shè)元素的個(gè)數(shù)為n,那么使用歸并排序拆分的次數(shù)為log2(n).所以共log2(n)層,那么使用log2(n)替換上面3*2^3中的3這個(gè)層數(shù),最終得出的歸并排序的時(shí)間復(fù)雜度為︰log2(n)*2^(log2(n))=log2(n)*n,根據(jù)大O推導(dǎo)法則,忽略底數(shù),最終歸并排序的時(shí)間復(fù)雜度為O(nlogn);
歸并排序的缺點(diǎn)∶
需要申請(qǐng)額外的數(shù)組空間,導(dǎo)致空間復(fù)雜度提升,是典型的以空間換時(shí)間的操作。
到此,關(guān)于“Java歸并排序舉例分析”的學(xué)習(xí)就結(jié)束了,希望能夠解決大家的疑惑。理論與實(shí)踐的搭配能更好的幫助大家學(xué)習(xí),快去試試吧!若想繼續(xù)學(xué)習(xí)更多相關(guān)知識(shí),請(qǐng)繼續(xù)關(guān)注億速云網(wǎng)站,小編會(huì)繼續(xù)努力為大家?guī)砀鄬?shí)用的文章!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。