Java 详细讲解分治算法如何实现归并排序

package Sort;

import java.util.Arrays;

/**

  * 归并排序：

  *

  * 利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，

  *

  * 而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。

  * @author lenovo

  *

  */

public class MergeSort {

     public static void main(String[] args) {

         int [] a= { 5 , 8 , 6 , 3 , 9 , 8 , 7 , 1 , 4 , 21 ,- 8 , 46 };

         int [] temp= new int [a.length];

         mergeSort(a, 0 , a.length- 1 , temp);

         System.out.println(Arrays.toString(a));

     }

     public static void mergeSort( int [] arr, int left, int right, int [] temp) {

         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 l=left; //左边序列的起始位置

         int r=mid+ 1 ; //右边序列的起始位置

         int t= 0 ; //中间数组的当前元素下标

         while (l<=mid &&r<=right ) { //左边或右边没结束

             //那边小就将那边的元素放入到临时数组中

             if (arr[l]<=arr[r]) {

                 temp[t++]=arr[l++];

             } else {

                 temp[t++]=arr[r++];

             }

         }

         //while循环结束，说明有一边已经遍历完毕，将另一边剩余的元素放入到临时数组中

         while (l<=mid) {

             temp[t++]=arr[l++];

         }

         while (r<=right) {

             temp[t++]=arr[r++];

         }

         //将临时数组中的有序序列copy到原数组中

         t= 0 ;

         int templeft=left;

         while (templeft<=right) {

             arr[templeft++]=temp[t++];

         }

     }

}