首页 > 代码库 > Merge Sort
Merge Sort
Good for array and linked list. Stable Sort.
Time Complexity: Best, Average, Worst => O(nlogn);
Space Complexity: O(n), in-place merge sort makes it very complicated.
public static void main(String[] args) { Random r = new Random(); int[] a = new int[]{r.nextInt(100), r.nextInt(100), r.nextInt(100),r.nextInt(100),r.nextInt(100),r.nextInt(100),r.nextInt(100),r.nextInt(100),r.nextInt(100),r.nextInt(100),r.nextInt(100)}; int[] aCopy1 = Arrays.copyOf(a, a.length); int[] aCopy2 = Arrays.copyOf(a, a.length); mergeSort1(aCopy1); mergeSort2(aCopy2); System.out.println(Arrays.toString(a)); System.out.println(Arrays.toString(aCopy1)); System.out.println(Arrays.toString(aCopy2)); } private static void mergeSort1(int[] a) { TopDownSplitMerge(a, 0, a.length, new int[a.length]); } //[begin,end) private static void TopDownSplitMerge(int[] a, int iBegin, int iEnd, int[] helper) { if(iEnd-iBegin<2) return; int iMid = (iBegin + iEnd)/2; TopDownSplitMerge(a, iBegin, iMid, helper); TopDownSplitMerge(a, iMid, iEnd, helper); //merge to helper array //left half a[iBegin:iMid-1] //right half a[iMid:iEnd-1] int iLeft = iBegin; int iRight = iMid; for(int j=iBegin;j<iEnd;++j) { if(iLeft<iMid && (iRight>=iEnd || a[iLeft]<a[iRight])) { helper[j] = a[iLeft]; ++iLeft; } else { helper[j] = a[iRight]; ++iRight; } } //copy values from helper array to original array. for(int j = iBegin;j<iEnd;++j) { a[j] = helper[j]; } } private static void mergeSort2(int[] a) { BottomUpMerge(a, a.length, new int[a.length]); } // Make successively longer sorted runs of length 2, 4, 8, 16... until whole array is sorted. private static void BottomUpMerge(int[] a, int length, int[] helper) { for(int width = 1;width<length;width *=2) { for(int i = 0;i<length;i+=width*2) { //for each iteration, merge the range [i, i+2*width-1] //left half: a[i: i+width-1] //right half:a[i+width:i+2*width-1] int iLeft = i; int iMid = Math.min(i+width, length); int iRight = iMid; int iEnd = Math.min(i+2*width, length); for(int j = iLeft; j<iEnd; ++j) { if(iLeft<iMid && (iRight>=iEnd || a[iLeft]<a[iRight])) { helper[j] = a[iLeft]; ++iLeft; } else { helper[j] = a[iRight]; ++iRight; } } } //copy values from helper array to original array. for(int j = 0;j<length;++j) { a[j] = helper[j]; } } }
Merge Sort
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。