排序----归并排序

一、基本思想：

  归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
  归并过程为：比较a[i]和b[j]的大小，若a[i]≤b[j]，则将第一个有序表中的元素a[i]复制到r[k]中，并令i和k分别加上1；否则将第二个有序表中的元素b[j]复制到r[k]中，并令j和k分别加上1，如此循环下去，直到其中一个有序表取完，然后再将另一个有序表中剩余的元素复制到r中从下标k到下标t的单元。归并排序的算法我们通常用递归实现，先把待排序区间[s,t]以中点二分，接着把左边子区间排序，再把右边子区间排序，最后把左区间和右区间用一次归并操作合并成有序的区间[s,t]。

二、代码实现：

package Ex;
import java.util.ArrayList;

public class Test6 {
  public static void main(String[] args) {
      int array[] = { 1, 2, 3, 0 };
      mergeSort(array);
      for (int s : array) {
        System.out.println(s);
      }
  }
  public static void mergeSort(int[] array) {
      // 将数据分成不同的组
      sort(array, 0, array.length - 1);
  }

  public static void sort(int[] array, int left, int right) {
      // 如果left<right,则还可以继续拆分
      if (left < right) {
          // 折半
          int midle = (left + right) >> 1;
          sort(array, left, midle);// 递归拆分成最小
          sort(array, midle + 1, right);
          // 合并,低位，中间位，高位
          merge(array, left, midle, right);
      }
  }

  public static void merge(int[] array, int low, int mid, int high) {
      // 创建临时数组
      int[] temp = new int[array.length];
      int left = low;
      int right = mid + 1;
      int k = low;
      // 得到排序后的临时数组
      while (left <= mid && right <= high) {
          // 左半部分最小值 小于 右半部分最小值
          // temp最小下标为左半部分最小值，K++,left左半部分右移

          // 如果左半部分最小值大于右半部分最小值
          // 将右半部分最小值赋给temp,右半部分右移
          if (array[left] < array[right]) {
              temp[k++] = array[left++];
              /**
               * 等价于 temp[k] = array[left]; left++; k++;
               * */
          } else {
              temp[k++] = array[right++];
          }
      }
      // 处理左半部分未参与比较的数
      while (left <= mid) {
          temp[k++] = array[left++];
      }
      // 处理右半部分未参与比较的数
      while (right <= high) {
          temp[k++] = array[right++];
      }
      // 将临时数组赋给array
      while (low <= high) {
          array[low] = temp[low++];
      }
  }
}

三、实例详解

array [] = {1,2,3,0};
1.sort(array,0,3);left=0,right=3,midle=1;
----2.sort(array,0,1);left=0,right=1,midle=0;
    ----3.sort(array,0,0);left=0,right=0,midle=0;
    ----3.sort(array,1,1);left=1,right=1,midle=1;
    ----3.merge(array,0,0,1);即1,2归并
        ----详解merge内部实现：
            ----temp[4],low=0,mid=0,high=1;left=0,right=1,k=0;
            ----while(left<=mid && right<=high) left=0,mid=0,right=1,high=1;
                ----if(array[left]<array[right]) left=0,right=1;array[0]<array[1]即 1<2 成立，执行if条件
                    ----temp[k++]=array[left++];即temp[0]=array[0];k=1,left=1;
            ----while(left<=mid) left=1,mid=0;条件不成立
            ----while(right<=high) right=1,high=1;
                ----temp[k++]=array[right++];即temp[1]=array[1];k=2,right=2;循环结束
            ----将临时数组temp的值赋给array
            ----while(low<=high)low=0,high=1
                ----array[low]=temp[low++]即array[0]=temp[0],low=1;
                ----array[low]=temp[low++]即array[1]=temp[1],low=2;循环结束
        ----merge归并结束
----2.sort(array,2,3);left=2,right=3,midle=2;
    ----4.sort(array,2,2);left=2,right=2,midle=2;
    ----4.sort(array,3,3);left=3,right=3,midle=3;
    ----4.merge(array,2,2,3);即3,0归并
        ----详解merge内部实现：
            ----temp[4],low=2,mid=2,high=3;left=2,right=3,k=2;
            ----while(left<=mid && right<=high);left=2,mid=2,right=3,high=3;
                ----if(array[left]<array[high]）left=2,right=3;即array[2]<array[3],即3<0，不成立，执行else
                ----else
                    ----temp[k++]=array[right++];即temp[2]=array[3],k=3,right=4;循环结束
            ----while(left<=mid);left=2,mid=2;条件成立
                ----temp[k++]=array[left++];即tenp[3]=array[2];k=4,left=3;循环结束
            ----while(right<=high);right=4,high=3;条件不成立
            ----将临时数组temp的值赋给array
            ----while(low<=high)low=2,high=3;
                ----array[low]=temp[low++];即array[2]=temp[2],low=3;
                ----array[low]=temp[low++];即array[3]=temp[3],low=4;循环结束
----2.merge(array,0,1,3);left=0,right=3,mid=1;即(1,2)与（3,0）归并
    ----详解merge内部实现：
        ----temp[4],low=0,mid=1,high=3;right=0,right=2,k=0;
        ----while(left<=mid && right<=high);left=0,mid=1,right=2,high=3;
            ---if(array[left]<array[right]);left=0,right=2;即array[0]<array[2],即1<0，不成立，执行else
            ----else
                ----temp[k++]=array[right++];即temp[0]=array[2],k=1,right=3;
            ----if(array[left]<array[right])left=0,right=3,即array[0]<array[3],即1<3,成立，执行if
                ----temp[k++]=array[left++];即temp[1]=array[0],k=2,left=1,mid=1,right=3
            ----if(array[left]<array[right]);left=1,right=3;即array[1]<array[3],即2<3,成立，执行if
                ----temp[k++]=array[left++];即temp[2]=array[1];k=3,left=2;循环结束
        ----while(left<=mid);left=2,mid=1;条件不成立
        ----while(right<=high);right=3,high=3;
            ----temp[k++]=array[right++];即temp[3]=array[3];k=4,right=4;循环结束
        ----while(low<=high);low=0,high=3;
            ----array[low]=temp[low++];即array[0]=temp[0],low=1;
            ----array[low]=temp[low++];即array[1]=temp[1],low=2;
            ----array[low]=temp[low++];即array[2]=temp[2],low=3;
            ----array[low]=temp[low++];即array[3]=temp[3],low=4;循环结束;
    ----merge实现结束；
----排序结束；

图示说明排序：（引用http://blog.csdn.net/yinjiabin/article/details/8265827/）

待排序列(14,12,15,13,11,16)