数据算法排序之归并排序

在你渐渐迷失在你的人生道路上的时候，千万不要因为走的太久，而忘记了我们为什么出发，做码农，也要清楚自己如何才能用有效的土地种植出 出色的产品，于是细节就需要把握一下。

排序是一个非常经典的问题，它以一定的顺序对一个数组（或一个列表）中的项进行重新排序（可以进行比较，例如整数，浮点数，字符串等）（增加，非递减，递减， 增加，词典等）。
有许多不同的排序算法，每个都有其自身的优点和局限性
引用于 https://visualgo.net/zh

归并排序，是创建在归并操作上的一种有效的排序算法。算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

• 算法复杂度：O（nlogn）

• 核心思想：分治

如我这里有一组数据，归并排序过程描述如下：

我们把上面的流程图合到一起就是如下：

---

分割的过程中其实可理解为就是以二分法将数组分割成最小单元，如下图所示分析了一下最后一步的合并过程

  //归并排序  @Test  public void mergeSortFunction2(){    //待排序数组    int arr[]={6,5,3,1,8,7,2,4};    int len = arr.length;    //临时数组    int[] result = new int[len];    //排序    sort(arr,result);
    System.out.println(Arrays.toString(result));  }

public static void sort(int []arr,int []temp ){    sort(arr,0,arr.length-1,temp);  }

private static void sort(int[] arr,int left,int right,int []temp){    if(left<right){      int mid = (left+right)/2;      //左边归并排序，使得左子序列有序      sort(arr,left,mid,temp);      //右边归并排序，使得右子序列有序      sort(arr,mid+1,right,temp);      //将两个有序子数组合并操作      merge(arr,left,mid,right,temp);    }  }

  private static void merge(int[] arr,int left,int mid,int right,int[] temp){    int i = left;//左序列指针    int j = mid+1;//右序列指针    int t = 0;//临时数组指针    while (i<=mid && j<=right){      if(arr[i]<=arr[j]){        temp[t++] = arr[i++];      }else {        temp[t++] = arr[j++];      }    }    while(i<=mid){//将左边剩余元素填充进temp中      temp[t++] = arr[i++];    }    while(j<=right){//将右序列剩余元素填充进temp中      temp[t++] = arr[j++];    }    t = 0;    //将temp中的元素全部拷贝到原数组中    while(left <= right){      arr[left++] = temp[t++];    }  }