歸并排序的時間復(fù)雜度是：nlogn
主要是用到二路歸并排序，也就是把兩個有序集合合并為一個有序集合.
下面是我寫的一個遞歸二路歸并排序的算法：

public class MergeSort {
 // private static long sum = 0;
 
 /**
  * <pre>
  * 二路歸并
  * 原理：將兩個有序表合并和一個有序表
  * </pre>
  *
  * @param a
  * @param s
  *            第一個有序表的起始下標
  * @param m
  *            第二個有序表的起始下標
  * @param t
  *            第二個有序表的結(jié)束小標
  *
  */
 private static void merge(int[] a, int s, int m, int t) {
  int[] tmp = new int[t - s + 1];
 
  int i = s, j = m, k = 0;
  while (i < m && j <= t) {
   if (a[i] <= a[j]) {
    tmp[k] = a[i];
    k++;
    i++;
   } else {
    tmp[k] = a[j];
    // sum += (j - i) - (j - m);
    j++;
    k++;
   }
  }
  while (i < m) {
   tmp[k] = a[i];
   i++;
   k++;
  }
 
  while (j <= t) {
   tmp[k] = a[j];
   j++;
   k++;
  }
 
  System.arraycopy(tmp, 0, a, s, tmp.length);
 }
 
 /**
  *
  * @param a
  * @param s
  * @param len
  *            每次歸并的有序集合的長度
  */
 public static void mergeSort(int[] a, int s, int len) {
 
  int size = a.length;
  int mid = size / (len << 1);
  int c = size & ((len<<1) - 1);
 
  // -------歸并到只剩一個有序集合的時候結(jié)束算法-------//
  if (mid == 0)
   return;
 
  // ------進行一趟歸并排序-------//
  for (int i = 0; i < mid; ++i) {
   s = i * 2 * len;
   merge(a, s, s + len, (len << 1) + s - 1);
  }
 
  // -------將剩下的數(shù)和倒數(shù)一個有序集合歸并-------//
  if (c != 0)
   merge(a, size - c - 2 * len, size - c, size - 1);
  //
  // for (int i = 0; i < a.length; ++i) {
  // System.out.print(a[i] + " ");
  // }
  // System.out.println();
 
  // -------遞歸執(zhí)行下一趟歸并排序------//
  mergeSort(a, 0, 2 * len);
 }
 
 public static void main(String[] args) {
  // merge(new int[] { 4, 3, 6, 1, 2, 5 }, 0, 3, 5);
 
  int[] a = new int[] { 4, 3, 6, 1, 2, 5};
  mergeSort(a, 0, 1);
 
  for (int i = 0; i < a.length; ++i) {
   System.out.print(a[i] + " ");
  }
 
  // System.out.println("/n" + sum);
 }
 
}

標簽：

版權(quán)申明：本站文章部分自網(wǎng)絡(luò)，如有侵權(quán)，請聯(lián)系：west999com@outlook.com
特別注意：本站所有轉(zhuǎn)載文章言論不代表本站觀點！
本站所提供的圖片等素材，版權(quán)歸原作者所有，如需使用，請與原作者聯(lián)系。