本文共 3662 字，大约阅读时间需要 12 分钟。

排序算法——归并排序

1. 基本介绍：mergeSort，是利用归并的思想实现的排序算法，该算法采用经典的分治策略，简而言之就是用递归实现分治，

• 分：是将大的问题分成一些小的问题，然后进行递归求解，
• 治：是将分的阶段得到的答案，整合在一起，得到最终的答案。
  思路分析图：
  
  

2. 思想分析：借用辅助数组进行中转，将原始数组一级一级不断划分，直到划分只剩两个，然后不能再分了，对两个进行中转操作，两个在回溯，四个，不断回溯，直到所有的排序过之后。
3. 代码实现：
   教程代码：

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);            //由于+1的存在,使得他会在仅仅只有一个元素的时候进行终止,然后运行组合语句            //项右递归            merge(arr,left,mid,right,temp);            //组合的是你当前分的范围,当前分了两个,那索引之内就只有这两个元素.        }    }    /**     *整个是两个数组合并为演示过程开始的     * @param arr  是为原始的需要排序的数组     * @param left  左边有序序列的初始索引,初始数组的头     * @param mid   mid = (right + left) / 2,是中间值,,左半边的尾,兼右半边的头     * @param right  右边有序数列的最终索引,初始数组尾,右半边的尾     * @param temp    做中转的数组     */    public static void merge(int[] arr,int left,int mid,int right,int[] temp){
           int i = left;        //与快排相同,是左边的开始的索引        int j = mid + 1;        //是右边开始的索引        int t= 0;        //这就是中转数组的存放索引        //(一)        //先把左右两边的数组,通过相互比较,依次放到中转数组中去,通过t的索引        //直到某一半放完为止,那就完完全全没有比较的必要了        while (i <= mid && j <= right){
               if (arr[i] <= arr[j]){
                   temp[t] = arr[i];                t ++;                i ++;                //复制过去是分为两步的,第一步是按照索引赋值,第二步是移动索引,等待下一步赋值            }else{
                   temp[t] = arr[j];                t ++;                j ++;            }        }        //(二)        //再把左边或者是右边剩下的,有序数组剩下部分,完完全全放到中转数组中去        //必须分为两个过程,不同于第一个过程,在这里是没有比较的        //while (i == mid && j < right){
           //不需要我这样写,因为经过上面的过程,已经是到达循环了        while (j <= right){
               temp[t] = arr[j];            t ++;            j ++;        }        //while (j == right && i < mid){
           while (i <= mid){
               temp[t] = arr[i];            t ++;            i ++;        }        //(三)        //再把中转数组中的所有的数据完完全全转移到原始数组中去,涉及到把l重置了//        int templeft = left;        t = 0;        while (templeft <= right){
               arr[templeft] = temp[t];            t ++;            templeft ++;        }    }

总结与分析：

• 概括：整个过程分为两个部分，第一部分为分，将数据多次划分到最终线；第二部分是合，从最终线开始数据逐渐合成原始的已经排序过的数据。
• 个人心得：设置固定座标和移动坐标，固定索引是left和right，作为遍历参考，l和r是遍历索引，随着遍历而移动。遍历索引与固定索引的相对位置决定着遍历的进程。整个归并的过程也是固定坐标和遍历索引的相互转化。

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);        }    }

分的过程中，结合开始索引和终止索引的中值，    不断对半分，直到划分之后的组中仅仅只有一个元素位置。     if (arr[i] <= arr[j]){
                   //总共也就三种情况,大于小于等于,等于移动谁都可以                temp[t] = arr[i];                t ++;                i ++;                //复制过去是分为两步的,第一步是按照索引赋值,第二步是移动索引,等待下一步赋值            }else{
                   temp[t] = arr[j];                t ++;                j ++;

}

• 借用外变量的方式存储值时，分为两步，复制原来的值，然后同时移位。

if (arr[i] <= arr[j]){
                   //总共也就三种情况,大于小于等于,等于移动谁都可以                temp[t] = arr[i];                t ++;                i ++;                //复制过去是分为两步的,第一步是按照索引赋值,第二步是移动索引,等待下一步赋值            }else{
                   temp[t] = arr[j];                t ++;                j ++;            }

• 问：每一次将数据由中转数组复制到原始数组中去，为什么把中转数组的初始变量设置为0，t = 0；
• 答：在每一次进行组合的过程中都会将中转数组的初始值化为0，即t = 0；然后完全复制遍历完之后，再用该情况下的中转数组实现值的完全转移。所以再从头遍历，不是完全读取中转数组中的值，而是由调用该方法时传入的左右限决定的。

int templeft = left;        t = 0;        while (templeft <= right){
               arr[templeft] = temp[t];            t ++;            templeft ++;        }    }

转载地址：http://gmgpb.baihongyu.com/