经典算法3:分治法求解归并排序
发布时间:2020-12-16 07:48:05 所属栏目:百科 来源:网络整理
导读:今天PHP站长网 52php.cn把收集自互联网的代码分享给大家,仅供参考。 /*分治法——归并排序 ?* 二路归并排序的分治策略是: (1)划分:将待排序序列r1,r2,…,rn划分为两个长度相等的子序列r1,rn/2和rn/2+1,rn; (2)求
以下代码由PHP站长网 52php.cn收集自互联网 现在PHP站长网小编把它分享给大家,仅供参考
/*分治法——归并排序
?* 二路归并排序的分治策略是: (1)划分:将待排序序列r1,r2,…,rn划分为两个长度相等的子序列r1,rn/2和rn/2+1,rn; (2)求解子问题:分别对这两个子序列进行排序,得到两个有序子序列; (3)合并:将这两个有序子序列合并成一个有序序列。 ?*/ public class MergeSort { /** * @param args */ public static void main(String[] args) { int a[] = { 21,34,56,43,99,37,78,10 };// 这里对8个元素进行排序 int low = 0,high = 7;// 初始化low和high的值,即数组的起始和终止的坐标 // 辅助数组b,作为临时数组 int b[] = new int[a.length]; //输出排序前的数组 System.out.print("排序前:"); for (int i = 0; i <= high; i++) { System.out.print(a[i] + " "); } // 归并排序 mergerSort(a,low,high,b); //输出排序后的数组 System.out.print("排序后:"); for (int i = 0; i <= high; i++) { System.out.print(a[i] + " "); } } /** * 分治和归并 * * @param a * @param low * @param high * @param b */ public static void mergerSort(int a[],int low,int high,int b[]) { int mid = 0; if (low < high) { mid = (high + low) / 2;// 分治位置,即将数组拆分的位置 mergerSort(a,mid,b); mergerSort(a,mid + 1,b); merger(a,b);// 归并 } } /** * 合并两个有序子序列 * * @param a * @param low * @param mid * @param high * @param b * 辅助数组 */ public static void merger(int[] a,int mid,int b[]) { int i = low; int j = mid + 1; int p = 0; // 合并两个有序数组 子序列1 a[low..mid] 子序列2 a[mid+1..high] while (i <= mid && j <= high) { b[p++] = (a[i] <= a[j]) ? a[i++] : a[j++]; } // 如果子序列1没有合并完则直接复制到复制数组中去 while (i <= mid) { b[p++] = a[i++]; } // 如果子序列2没有合并完则直接复制到复制数组中去 while (j <= high) { b[p++] = a[j++]; } // 把辅助数组的元素复制到原来的数组中去 for (p = 0,i = low; i <= high; i++,p++) { a[i] = b[p]; } } } 以上内容由PHP站长网【52php.cn】收集整理供大家参考研究 如果以上内容对您有帮助,欢迎收藏、点赞、推荐、分享。 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |