归并排序

归并排序

归并排序是利用归并的思想实现的排序方法，该方法采用经典的分治策略（分治法将问题分成一些小的问题然后递归求解，而治的阶段则将分的阶段得到的各答案“修补”在一起，即分而治之）

通俗一点就是
将数组分解到最小之后，然后合并两个有序数组，基本思路是比较两个数组的最前面的数，谁小就先取谁，取了后相应的指针就往后移一位。然后再比较，直至一个数组为空，最后把另一个数组的剩余部分复制过来即可。

时间复杂度：O(nlogn)
稳定度：稳定

实现思路

  /**
    * 分解操作
    *      先分解
    *      再合并
    * @param arr   排序的原始数组
    * @param left  无序序列的左边起始索引
    * @param right 无序序列的右边起始索引
    * @param temp  做中转的数组
    */
public static void mergeSort3(int[] arr,int left,int right,int[] temp){
       if (left < right) {
           int mid = (left + right) / 2;
           //左边分解
           mergeSort3(arr,left,mid,temp);
           //右边分解
           mergeSort3(arr,mid+1,right,temp);
           //合并
           merge3(arr,left,mid,right,temp);
       }
   }
/**
    * 合并
    * 
    * @param arr   排序的原始数组
    * @param left  左边有序序列的初始索引
    * @param mid   中间索引
    * @param right 右边索引
    * @param temp  做中转的数组
    */
   public static void merge3(int[] arr, int left, int mid, int right, int[] temp){

       int l = left;//初始化l，左边有序序列的初始索引
       int j = mid + 1;//初始化j，右边有序序列的初始索引
       int t = 0;//指向temp数组的当前索引

       //1、比较左右两组序列，将小的值填充到temp
       while(l <= mid && j <= right){
           if(arr[l] < arr[j]){
               temp[t] = arr[l];
               l++;
           } else {
               temp[t] = arr[j];
               j++;

           }
           t++;
       }
       //2、把剩下的没填充的数组填充
       while(l <= mid){
           temp[t] = arr[l];
           l++;
           t++;
       }
       while(j <= right){
           temp[t] = arr[j];
           j++;
           t++;
       }
       //3、copy数组temp到原数组
       t = 0;
       for(int i = left; i <= right;i++ ){
           arr[i] = temp[t];
           t++;
       }
   }