转载

排序算法之归并排序

设计思想

归并排序算法完全遵循分治法模式。分治法的思想：将原问题分解为几个规模较小但类似于原问题的子问题，递归地求解这些子问题，然后再合并这些子问题的解来建立原问题的解。

分治模式在每层递归都有三个步骤：

分解原问题为若干个子问题，这些子问题是原问题的规模较小的实例。

解决这些子问题，递归求解各个子问题。然而，若子问题的规模足够小，则直接求解。

合并这些子问题的解成原问题的解。

归并排序的分治策略：

分解：分解待排序的n个元素的序列成各具n/2个元素的两个子序列。

解决：使用归并排序递归地排序两个子序列。

合并：合并两个已排序的子序列已产生已排序的答案。

在解决这步中，递归调用递归排序，不断的将子序列一分为二，当待排序的序列长度为1时，递归“开始回升”，在这种情况下不要做任何工作，因为长度为1的每个序列都已有序。

归并排序算法的关键步骤是合并步骤中两个已排序序列的合并。

动态演示图

排序算法之归并排序

源代码

public class MergeSort {  /**   * @description MergeSort   * @param a array   */  public static void sort(int[] a) {   sort(a, 0, a.length - 1);  }  /**   * @description MergeSort   * @param a array   * @param s start   * @param e end   */  public static void sort(int[] a, int s, int e) {   if(s < e) {    int m = (s + e) / 2;    sort(a, s, m);    sort(a, m + 1, e);    merge(a, s, m, e);   }  }  /**   * @description merge two sorted sequence a[s...m] a[m+1...e]   * @param a array   * @param s start   * @param m medium   * @param e end   */  private static void merge(int[] a, int s, int m, int e) {   //左侧数组   int[] left = new int[m - s + 1];   //右侧数组   int[] right = new int[e - m];   for (int i = 0; i < m - s + 1; i++)     left[i] = a[s + i];   for (int j = 0; j < e - m; j++)     right[j] = a[m + j + 1];   //k = s !!!   int i = 0, j = 0, k = s;   //合并   while (i < left.length && j < right.length) {    if (left[i] <= right[j])     a[k++] = left[i++];    else      a[k++] = right[j++];   }   while (i < left.length)    a[k++] = left[i++];   while (j < right.length)    a[k++] = right[j++];  } }

测试

测试代码

public static void main(String[] args) {  int[] a = {6, 5, 3, 1, 8, 7, 2, 4};  MergeSort.sort(a);  for(int i = 0; i < a.length; i++) {   System.out.print(a[i] + " ");  } }

测试结果

时间复杂度

分治算法运行时间的递归式来自基本模式的三个步骤。如前所述，假设T(n)是规模为n的一个问题的运作时间。若问题规模足够小，如对某个常量c，n<=c，则直接求解需要常量时间，将其记作 Θ( 1)。假设把原问题分解成a个子问题，每个子问题的规模是原问题的1/b。(对于归并排序，a和b，然而，在许多分治算法中，a！= b)为了求解一个规模为n/b的子问题，需要T(n/b)的时间，所以需要aT(n/b)的时间来求解a个子问题。如果分解问题成子问题需要时间D(n)，合并子问题的解成原问题的解需要时间C(n)，那么得到递归式：

排序算法之归并排序