首页 > 代码库 > 归并排序
归并排序
归并排序算法是用分治策略实现对n个元素进行排序的算法。
其基本思想是：将待排序的元素分成大小大致相同的两个子集合，分别对2个子集合进行排序，最终将排序好的子集合合并成为所要求的排好序的集合。
递归版本算法(不完全版本)：
1 public static void mergeSort(Comparable a[],int left,int right){2 if(left<right){//至少有两个元素3 int i=(left+right)/2; //取中点4 mergeSort(a,left,i);5 mergeSort(a, i+1, right);6 merge(a,b,left,right); //合并到数组b7 copy(a,b,left,right); //复制回数组a8 }9 }
非递归版本实现：
可以看出，算法mergeSort的递归过程只是将待排序集合一分为二，直至待排序的集合只剩下一个元素为止。然后不断合并2个排序好的子集合。
由此可以想到，我们可以先将数组a中相邻元素两两配对。用合并算法将他们排序，构成n/2组长度为2的排好序的子集合，然后将它们排序成长度为4
的子集合，如此继续下去，直至整个数组排好序。
这样一来就可以消除递归了。
1 public class MergeSort { 2 3 // 非递归版本归并排序 4 @SuppressWarnings("rawtypes") 5 public static void mergeSort(Comparable[] a) { 6 Comparable b[] = new Comparable[a.length]; 7 int s = 1; 8 while (s < a.length) { 9 // a,b交替保证了a一直是有序的10 mergePass(a, b, s);11 s = s * 2;12 mergePass(b, a, s);13 s = s * 2;14 }15 }16 17 @SuppressWarnings("rawtypes")18 private static void mergePass(Comparable[] x, Comparable[] y, int s) {19 // 合并大小为s的相邻子数组20 int i = 0;21 while (i + 2 * s <= x.length) {22 // 合并大小为s的相邻2段子数组，x[i,i+s-1]，x[i+s-1,i+2*s-1]23 merge(x, y, i, i + s - 1, i + 2 * s - 1);24 i = i + 2 * s;25 }26 27 if (i + s < x.length) {28 // 剩下的元素个数大于s小于2s,仍然要合并29 merge(x, y, i, i + s - 1, i + 2 * s - 1);30 } else {31 // i+s>=x.length的时候，此时剩余的元素个数小于s， 当小于s的时候已经是有序的，直接把剩余元素添加到y的末尾32 for (; i < y.length; i++)33 y[i] = x[i];34 }35 }36 37 @SuppressWarnings({ "rawtypes", "unchecked" })38 private static void merge(Comparable[] copy, Comparable[] to, int left,39 int middle, int right) {40 // 合并copy[left,middle]和to[middle+1,right]到to[left,right]41 int i = left, j = middle + 1, k = left;42 43 while (i <= middle && j <= right) {44 if (copy[i].compareTo(copy[j]) <= 0) // 由小到大排序45 to[k++] = copy[i++];46 else47 to[k++] = copy[j++];48 }49 50 /*51 * 以下两个循环用于将剩下已经有序的元素添加到to的末尾， 其中一个数组最大的元素n已经在to中，另外一个数组的元素肯定大于等于n，52 * 因此直接添加就行53 */54 while (i <= middle)55 to[k++] = copy[i++];56 while (j <= right)57 to[k++] = copy[j++];58 }59 60 @SuppressWarnings("rawtypes")61 public static void main(String[] args) {62 Comparable a[] = { 4, 6, 7, 1, 2, 5, 9, 0 };63 mergeSort(a);64 for (int i = 0; i < a.length; i++)65 System.out.print(" "+a[i]);66 }67 68 }
归并排序
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。