算法面经--归并排序

归并排序（递归合并）

一、算法思路

该算法采用经典的分治（****divide-and-conquer） 策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修 补"在一起，即分而治之)。

归并排序的实现：这个其实就是层次的问题，把一个很长的数组分段排好序，然后用比较插入的方式一次遍历把两个排好序的数组合并成一个。就这样递归最后整个数组排好序了。

示意图：

归并排序1.png 归并排序2.png

[图片上传失败...(image-aabb53-1591968533004)]

二、代码实现

 public class MergetSort {
  public static void main(String[] args) {
  int arr[]={8,4,5,7,1,3,6,2};

  int temp[] = new int[arr.length];   //归并排序需要一个额外的空间
  mergeSort(arr,0,arr.length-1,temp);
  System.out.println("归并排序后=" + Arrays.toString(arr));
  }

  //分解方法
  public static void mergeSort(int[] arr,int left,int right,int[] temp ){

  if(left >= right) return ;  //递归退出条件
  //if(left < right){
  int mid = (left + right)/2; //中间索引
  //向左递归进行分解
  mergeSort(arr,left,mid,temp);
  //向右递归进行分解
  mergeSort(arr,mid +1,right,temp);
  //合并
  merge(arr,left,mid,right,temp);

  //}
  }

  //合并算法
  public static void merge(int[] arr, int left, int mid, int right, int[] temp){
  int i = left;  //初始化i,左边有序序列的初始索引
  int j = mid+1;  //初始化j，右边有序序列的初始索引
  int t = 0; //指向temp数组的当前索引

  //(一)
  //先把左右两边（有序）的数据按照规则填充到temp数组中
  //直到左右两边的有序序列，又一遍处理完毕为止
  while(i<=mid && j<=right){  //继续
  //如果左边的有序序列的当前元素，小于等于右边有序序列的当前元素
  //即将左边的当前元素，填充到 temp数组 
  //然后 t++, i++
  if(arr[i]<=arr[j]){
  temp[t] = arr[i];
  i+=1;
  }else{  //反之，将右边有序序列的当前元素，填充到temp数组中
  temp[t] = arr[j];
  j+=1;
  }
  t+=1;
  }
  //（二）
  //把有剩余数据的一边的数据依次全部填充到temp
  while( i <= mid) { //左边的有序序列还有剩余的元素，就全部填充到temp
  temp[t++] = arr[i++];
  } 

  while( j <= right) { //左边的有序序列还有剩余的元素，就全部填充到temp
  temp[t++] = arr[j++];
  }
  //（三）
  //将temp数组的元素拷贝到arr
  //注意，并不是每次到拷贝所有
 //  t = 0;
 //  int tempLeft = left;
 //  //第一次合并 tempLeft = 0,right = 1 //tempLeft = 2,right = 3//tL=0 ri=3
 //  //最后一次 tempLeft = 0，right =7
 //  while(tempLeft <= right){
 //  arr[tempLeft] = temp[t];
 //  t+=1;
 //  tempLeft +=1;
 //  }
  //for循环实现将temp元素(left~right)拷贝到arr
  for(int tempLeft = left;tempLeft <= right;tempLeft++){
  arr[tempLeft] = temp[tempLeft -left];
  }
  }
 ​
 }