经典算法3：分治法求解归并排序

概述经典算法3：分治法求解归并排序

下面是内存溢出 jb51.cc 通过网络收集整理的代码片段。

内存溢出小编现在分享给大家，也给大家做个参考。

/*分治法——归并排序
 * 二路归并排序的分治策略是：
（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];              }          }      }  

以上是内存溢出(jb51.cc)为你收集整理的全部代码内容，希望文章能够帮你解决所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。

总结

以上是内存溢出为你收集整理的经典算法3：分治法求解归并排序全部内容，希望文章能够帮你解决经典算法3：分治法求解归并排序所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。