[关闭]
@xujun94 2016-07-02T23:57:44.000000Z 字数 4445 阅读 2607

归并排序的实现（java）

排序 归并排序 java

本文固定链接：https://www.zybuluo.com/xujun94/note/424570

关于二分查找的，可以参考我的这篇博客二分查找的相关算法题

关于归并排序的的，可以参考我的这篇博客归并排序 递归版和非递归版的实现（java）

关于快速排序的，可以参考我的这篇博客 快速排序的相关算法题（java）

转载请注明原博客地址： http://write.blog.csdn.net/postedit/51292207

什么是归并排序

首先我们来看一下分解是怎样实现的呢？

  1. // 递归退出条件，及left》=right的时候
  2.  if (left < right) {
  3.     // 找出中间索引
  4.     center = (left + right) / 2;
  5.     // 对左边数组进行递归
  6.      mSort(k, 0, center);
  7.     // 对右边数组进行递归
  8.     mSort(k, center + 1, right);
  9.      // 合并
  10.    merging(k, left, center, right);
  11.  }

接着合并是怎样实现的呢？

  1. 初始化一个数组，将左右数组的数进行比较，将较小的数存入中间数组
  2. 再将左右数组剩下的数存到中间数组
  3. 最后，将中间数组复制回原来的数组
  1.  private static void merging(int[] k, int left, int center, int right) {
  2.         int tempArr[] = new int[k.length];// 存放数据的数组
  3.         // third记录中间数组的索引
  4.         int mid = center + 1;
  5.         int third = left;
  6.         int temp = left;
  7.         while (left <= center && mid <= right) {
  8.             // 从左右两个数组找出最小的数存入tempArr数组
  9.             if (k[left] < k[mid]) {
  10.                 tempArr[third++] = k[left++];
  11.             } else {
  12.                 tempArr[third++] = k[mid++];
  13.             }
  14.         }
  16.         // 剩余部分依次放入中间数组
  17.         while (mid <= right) {
  18.             tempArr[third++] = k[mid++];
  19.         }
  21.         while (left <= center) {
  22.             tempArr[third++] = k[left++];
  23.         }
  24.         // 将中间数组中的内容复制回原数组
  25.         while (temp <= right) {
  26.             k[temp] = tempArr[temp++];
  27.         }
  28.     }
  30. }

递归版 的源码实现如下

  1. //下面是递归版的
  2. package com.xujun.mergesort;
  4. public class MergeSort {
  6.     static int[] a = new int[] { 20, 9, 3, 5, 26, 100, 8, -1, 7, 50, -5 };
  8.     public static void main(String[] args) {
  9.         System.out.println("before sort");
  10.         ArrayUtils.printArray(a);
  11.         mergeSort(a);
  12.         System.out.println("after sort");
  13.         ArrayUtils.printArray(a);
  15.     }
  17.     private static void mergeSort(int[] k) {
  18.         mSort(k, 0, k.length - 1);
  19.     }
  21.     private static void mSort(int[] k, int left, int right) {
  22.         int center
  23.         // 递归退出条件，及left》=right的时候
  24.         if (left < right) {
  25.             // 找出中间索引
  26.             center = (left + right) / 2;
  27.             // 对左边数组进行递归
  28.             mSort(k, 0, center);
  29.             // 对右边数组进行递归
  30.             mSort(k, center + 1, right);
  31.             // 合并
  32.             merging(k, left, center, right);
  34.         }
  35.     }
  37.     private static void merging(int[] k, int left, int center, int right) {
  38.        // 存放数据的数组
  39.         int tempArr[] = new int[k.length];
  40.         // third记录中间数组的索引
  41.         int mid = center + 1;
  42.         int third = left;
  43.         int temp = left;
  44.         while (left <= center && mid <= right) {
  45.             // 从左右两个数组找出最小的数存入tempArr数组
  46.             if (k[left] < k[mid]) {
  47.                 tempArr[third++] = k[left++];
  48.             } else {
  49.                 tempArr[third++] = k[mid++];
  50.             }
  51.         }
  53.         // 剩余部分依次放入中间数组
  54.         while (mid <= right) {
  55.             tempArr[third++] = k[mid++];
  56.         }
  58.         while (left <= center) {
  59.             tempArr[third++] = k[left++];
  60.         }
  61.         // 将中间数组中的内容复制回原数组
  62.         while (temp <= right) {
  63.             k[temp] = tempArr[temp++];
  64.         }
  65.     }
  67. }

下面说一下分递归版的实现思路

  1. 从归并段的长度为1开始，一次使归并段的长度变为原来的2倍。
  2. 在每趟归并的过程中，要注意处理归并段的长度为奇数和 最后一个归并段的长度和前面的不等的情况，需要做一下处理
  1.    // 程序边界的处理非常重要
  2.         while (len <= t.length) {
  3.             for (int i = 0; i + len <= t.length - 1; i += len * 2) {
  4.         //    System.out.println("len="+len);
  5.                 low = i;
  6.                 mid = i + len - 1;
  7.                 high = i + len * 2 - 1;
  8.                 if (high > t.length - 1)
  9.                     high = t.length - 1;
  10.                 merge(t, i, mid, high);
  11.             }
  12. //长度加倍
  13.             len += len;
  14.         }
  15.         return true;
  16.     }

源码如下：

  1. package com.xujun.mergesort1;
  3. public class MergeSort2 {
  4.     /**
  5.      * 二路归并排序的递归算法-入口
  6.      * 
  7.      * @param <T>
  8.      * @param t
  9.      * @return
  10.      */
  11.     public static <T extends Comparable> boolean mergeSortRecursive(T[] t) {
  12.         if (t == null || t.length <= 1)
  13.             return true;
  15.         MSortRecursive(t, 0, t.length - 1);
  17.         return true;
  18.     }
  20.     /**
  21.      * 二路归并排序的递归算法-递归主体
  22.      * 
  23.      * @param <T>
  24.      * @param t
  25.      * @param low
  26.      * @param high
  27.      * @return
  28.      */
  29.     private static <T extends Comparable> boolean MSortRecursive(T[] t,
  30.             int low, int high) {
  31.         if (t == null || t.length <= 1 || low == high)
  32.             return true;
  34.         int mid = (low + high) / 2;
  35.         MSortRecursive(t, low, mid);
  36.         MSortRecursive(t, mid + 1, high);
  37.         merge(t, low, mid, high);
  39.         return true;
  40.     }
  43.     public static <T extends Comparable> boolean mergeSortNonRecursive(T[] t) {
  44.         if (t == null || t.length <= 1)
  45.             return true;
  47.         int len = 1;
  48.         int low = 0;
  49.         int mid;
  50.         int high;
  51.         // 程序边界的处理非常重要
  52.         while (len <= t.length) {
  53.             for (int i = 0; i + len <= t.length - 1; i += len * 2) {
  54.         //    System.out.println("len="+len);
  55.                 low = i;
  56.                 mid = i + len - 1;
  57.                 high = i + len * 2 - 1;
  58.                 if (high > t.length - 1)
  59.                     high = t.length - 1;
  60.                 merge(t, i, mid, high);
  61.             }
  62. //长度加倍
  63.             len += len;
  64.         }
  65.         return true;
  66.     }
  68.     /**
  69.      * 将两个归并段合并成一个归并段
  70.      * 
  71.      * @param <T>
  72.      * @param t
  73.      * @param low
  74.      * @param mid
  75.      * @param high
  76.      * @return
  77.      */
  78.     private static <T extends Comparable> boolean merge(T[] t, int low,
  79.             int mid, int high) {
  80.         T[] s = t.clone();// 先复制一个辅助数组
  82.         int i, j, k;// 三个指示器，i指示t[low...mid]，j指示t[mid+1...high]，k指示s[low...high]
  83.         for (i = low, j = mid + 1, k = low; i <= mid && j <= high; k++) {
  84.             if (t[i].compareTo(t[j]) <= 0) {
  85.                 s[k] = t[i++];
  86.             } else {
  87.                 s[k] = t[j++];
  88.             }
  89.         }
  91.         // 将剩下的元素复制到s中
  92.         if (i <= mid) {
  93.             for (; k <= high; k++) {
  94.                 s[k] = t[i++];
  95.             }
  96.         } else {
  97.             for (; k <= high; k++) {
  98.                 s[k] = s[j++];
  99.             }
  100.         }
  101.         for (int m = low; m <= high; m++) {// 将辅助数组中的排序好的元素复制回原数组
  102.             t[m] = s[m];
  103.         }
  105.         return true;
  106.     }
  108.     public static void main(String[] args) {
  109.         Integer[] arr = new Integer[] { 2, 3, 6, 8, 9, 2, 0, 1 };
  110.         long startTime = System.currentTimeMillis(); // 获取开始时间
  111.         mergeSortRecursive(arr);
  112.         long endTime = System.currentTimeMillis(); // 获取开始时间
  113.         System.out.println("执行时间：" + (endTime - startTime));
  114.         for (int i : arr) {
  115.             System.out.println(i);
  116.         }
  117.         startTime = System.currentTimeMillis(); // 获取开始时间
  118.         mergeSortNonRecursive(arr);
  119.         endTime = System.currentTimeMillis(); // 获取开始时间
  120.         System.out.println("执行时间：" + (endTime - startTime));
  121.         for (int i : arr) {
  122.             System.out.println(i);
  123.         }
  124.     }
  125. }

关于二分查找的，可以参考我的这篇博客二分查找的相关算法题

关于归并排序的的，可以参考我的这篇博客归并排序 递归版和非递归版的实现（java）

转载请注明原博客地址： http://write.blog.csdn.net/postedit/51292207

源码下载地址： http://download.csdn.net/detail/gdutxiaoxu/9565965

添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注