算法小记：归并排序

一、思想

归并排序：将一个数组排序，可以先（递归地）将它分成两半部份分别排序，然后将结果归并起来；

二、概念

• 归并：将两个有序的数组归并成一个更大的有序数组；

  三、特点

  • 优点：能够保证将任意长度为N的数组排序所需要的时间和NlogN成正比；

  • 缺点：需要额外的空间和N成正比；

    四、实现方法

    • 将两个不同的有序数组归并到第三个数组中；

    • 先将前半部分排序，在将后半部分排序，然后在数组中移动元素而不需要使用额外的空间；

      五、代码

      /** 
       * 归并排序 
       *  
       * @author pengcx 
       *  
       */ 
      public class Merge extends Sort { 
          /** 归并所需的辅助数组 */ 
          private static Comparable[] aux; 
       
          public static void main(String[] args) { 
              String[] a = { "d", "a", "w", "b", "q" }; 
              Merge.sort(a); 
              show(a); 
          } 
       
          public static void sort(Comparable[] a) { 
              aux = new Comparable[a.length]; 
              sort(a, 0, a.length - 1); 
          } 
       
          /** 
          * 排序数组的a[lo]至a[hi]元素 
          *   
          * @param a 
          *            数组a 
          * @param lo 
          *            最小元素位置lo 
          * @param hi 
          *            最大元素位置hi 
          */ 
          private static void sort(Comparable[] a, int lo, int hi) { 
              if (hi <= lo) { 
                  return; 
              } 
       
              // 计算数组中间位置 
              int mid = lo + (hi - lo) / 2; 
              // 排序数组a左边的元素 
              sort(a, lo, mid); 
              // 排序数组a右边的元素 
              sort(a, mid + 1, hi); 
              // 合并数组a左边和右边的元素  
              merge(a, lo, mid, hi); 
          } 
       
          /** 
          *  将数组a的a[lo]至a[mid]的元素与a[mid]至a[hi]的元素合并 
          *  
          * @param a 
          *            合并的数组a 
          * @param lo 
          *            最小数组元素lo 
          * @param mid 
          *            中间元素位置mid 
          * @param hi 
          *            最大元素位置hi 
          */ 
          public static void merge(Comparable[] a, int lo, int mid, int hi) { 
              int i = lo, j = mid + 1; 
       
              for (int k = lo; k <= hi; k++) { 
                  aux[k] = a[k]; 
              } 
       
              for (int k = lo; k <= hi; k++) { 
                  // 如果左边的元素用尽，取右边的元素 
                  if (i > mid) { 
                      a[k] = aux[j++]; 
                  } 
                  // 如果右边的元素用尽，取左边的元素 
                  else if (j > hi) { 
                      a[k] = aux[i++]; 
                  } 
                  // 如果右半边的当前元素小于左半边的当前元素，取右半边元素 
                  else if (less(aux[j], aux[i])) { 
                      a[k] = aux[j++]; 
                  } 
                 // 如果右半边的当前元素大于等于左半边的当前元素，取左半边元素 
                  else { 
                      a[k] = aux[i++]; 
                  } 
              } 
          } 
      }