Java 十大排序算法之歸並排序刨析
歸並排序原理
1.盡可能的一組數據拆分成兩個元素相等的子組,並對每一個子組繼續拆分,直到拆分後的每個子組的元素個數是1為止。
⒉將相鄰的兩個子組進行合並成一個有序的大組。
3.不斷的重復步驟2,直到最終隻有一個組為止。
歸並排序API設計
類名 | Merge |
構造方法 | Merge():創建Merge對象 |
成員方法 |
1.public static void sort(Comparable[] a):對數組內的元素進行排序 2.private static void sort(Comparable[] a,int lo,int hi):對數組a中從索引lo到索引hi之間的元素進行排序 3.private static void merge(Comparable[] a,int lo,int mid,int hi):從索引lo到索引mid為一個子組,從索引mid+1到索引hi為另一個子組,把數組a中的這兩個子組的數據合並成一個有序的大組(從索引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數組中,索引i和索引j處的值 |
成員變量 | private static ComParable[] assit:完成歸並操作需要的輔助數組 |
歸並排序代碼實現
public class Merge { //輔助數組 private static Comparable[] assist; //對數組a中的元素進行排序 public static void sort(Comparable[] a){ assist=new Comparable[a.length]; int lo=0; int hi=a.length-1; sort(a,lo,hi); } //對數組a中從lo到hi的元素進行排序 private static void sort(Comparable[] a,int lo,int hi){ if(hi<=lo){ return; } int mid=lo+(hi-lo)/2; //對lo到mid之間的元素進行排序 sort(a,lo,mid); //對mid+1到hi之間的元素進行排序 sort(a,mid+1,hi); //對lo到mid這組數據和mid到hi這組數據進行歸並 merge(a,lo,mid,hi); } //對數組中,從lo到mid為一組,從mid+1到hi為一組,對這兩組數據進行歸並 public static void merge(Comparable[] a,int lo,int mid,int hi){ //lo到mid這組數據和mid+1到hi這組數據歸並到輔助數組assist對應的索引處 int i=lo;//定義一個指針,指向assist數組中開始填充數據的索引 int p1=lo;//定義一個指針,指向第一組數據的第一個元素 int p2=mid+1;//定義一個指針,指向第二組數據的第一個元素 //比較左邊小組和右邊小組中的元素大小,哪個小,就把哪個數據填充到assist數組中 while(p1<=mid&&p2<=hi){ if(less(a[p1],a[p2])){ assist[i++]=a[p1++]; }else{ assist[i++]=a[p2++]; } } //把未填充的數據填到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; } //數組元素i和j交換位置 private static void exchange(Comparable[] a,int i,int j){ Comparable t=a[i]; a[i]=a[j]; a[j]=t; } } //測試代碼 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)); } }
歸並排序的時間復雜度分析
歸並排序是分治思想的最典型的例子,上面的算法中,對a[lo..hi]進行排序,先將它分為a[lo..mid]和a[mid+1..hi]兩部分,分別通過遞歸調用將他們單獨排序,最後將有序的子數組歸並為最終的排序結果。該遞歸的出口在於如果一個數組不能再被分為兩個子數組,那麼就會執行merge進行歸並,在歸並的時候判斷元素的大小進行排序。
用樹狀圖來描述歸並,如果一個數組有8個元素,那麼它將每次除以2找最小的子數組,共拆log8次,值為3,所以樹共有3層那麼自頂向下第k層有2^k個子數組,每個數組的長度為2^(3-k),歸並最多需要2^(3-k)次比較。因此每層的比較次數為2^k * 2^(3-k)=2^3,那麼3層總共為3*2^3。
假設元素的個數為n,那麼使用歸並排序拆分的次數為log2(n).所以共log2(n)層,那麼使用log2(n)替換上面3*2^3中的3這個層數,最終得出的歸並排序的時間復雜度為︰log2(n)*2^(log2(n))=log2(n)*n,根據大O推導法則,忽略底數,最終歸並排序的時間復雜度為O(nlogn);
歸並排序的缺點∶
需要申請額外的數組空間,導致空間復雜度提升,是典型的以空間換時間的操作。
到此這篇關於Java 十大排序算法之歸並排序刨析的文章就介紹到這瞭,更多相關Java 歸並排序內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet!