归并排序

Merge Sort 排序算法——归并排序

基本介绍

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

思路图解

分很简单，就是将数组中的数据，依次慢慢分开

这里的合，不光是将分好后的数据合起来，在合起来后的小数组进行排序调换，具体内容见图二。

图一

图二

代码

算法代码

代码部分有两块，第一块是分，通过递归，最终将数组最终分为单个元素，然后在顺着分的倒过来路线来合，通过治的方法，来比较大小，将排列好的数据给temp，temp最终将这段排好顺序的数组copy到原来这段的arr的位置。通过递归来分，接着递归的回溯来进行”治“从而在回溯完后数组的顺序也排完了。

    //分+合的方法
    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 );
        }
    }

    //合并方法

    /**
     *
     * @param arr 排序的原始数组
     * @param left 左边有序序列的初始索引
     * @param mid 中间索引
     * @param right 右边索引
     * @param temp 做中转数组
     */
    public static void Merge ( int[] arr, int left, int mid, int right, int[] temp ) {

        int i = left;  //初始化i,
        int j=mid+1; //
        int t = 0; //temp索引

        //一
        //先把左右两边（有序）的数据按照规则填充到temp数组
        //直到左右两边的有序序列，有一边处理完成
        while (i <= mid && j <= right) { //继续
            //如果左边的有序序列的当前元素，小于等于右边的有序序列当前元素
            //即将左边的当前元素填充到temp数组里
            // 然后t++,i++
            if ( arr[i]<=arr[j] ) {
                temp[ t ] = arr[ i ];
                t++;
                i++;
            }
            else{  //反之将右边添加进去
                temp[ t ] = arr[ j ];
                t++;
                j++;

            }
        }
        //二把剩余数据的一边全部填入temp
        while (i <= mid) {  //说明左边元素还有剩余，将全部填充到temp
            temp[ t ] = arr[ i ];
            i++;
            t++;
        }
        while (j <= right) {
            temp[ t ] = arr[ j ];
            j++;
            t++;
        }
        //三
        //将temp数组的元素拷贝到arr
        //注意，并不是每次拷贝所有
        t = 0;
        int templeft = left;
        //第一合并0->1
        //最后一次合并就是0->arr.length-1
//        System.out.println ("templeft:"+templeft+"right:"+right );
        while (templeft <= right) {
            arr[ templeft ] = temp[ t ];
            t++;
            templeft++;
        }
    }

性能测试

在强大的算法前之前的8万数据已经无法在检验它的性能，直接上8000万

public class MergetSort {
    public static void main ( String[] args ) {
/*        int arr[] = {8, 4, 5, 1, 3, 6, 2,10,11,9,-2};
        int temp[] = new int[ arr.length ];  //归并排序需要额外的空间
        mergeSort ( arr,0,arr.length-1,temp );
        System.out.println ("归并排序"+ Arrays.toString(arr) );*/
        int arr[] = new int[ 80000000 ];
        int temp[] = new int[ arr.length ];  //归并排序需要额外的空间
        randomArr ( arr );
        System.out.println ( "归并排序8000万数据所用时间" );
        String date1String = Date ( );
        System.out.println ( "排序前时间是：" + date1String );
        mergeSort ( arr,0,arr.length-1,temp );
        String date2String = Date ( );
        System.out.println ( "排序后时间是：" + date2String );
    }

    //分+合的方法
    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 );
        }
    }

    //合并方法

    /**
     *
     * @param arr 排序的原始数组
     * @param left 左边有序序列的初始索引
     * @param mid 中间索引
     * @param right 右边索引
     * @param temp 做中转数组
     */
    public static void Merge ( int[] arr, int left, int mid, int right, int[] temp ) {

        int i = left;  //初始化i,
        int j=mid+1; //
        int t = 0; //temp索引

        //一
        //先把左右两边（有序）的数据按照规则填充到temp数组
        //直到左右两边的有序序列，有一边处理完成
        while (i <= mid && j <= right) { //继续
            //如果左边的有序序列的当前元素，小于等于右边的有序序列当前元素
            //即将左边的当前元素填充到temp数组里
            // 然后t++,i++
            if ( arr[i]<=arr[j] ) {
                temp[ t ] = arr[ i ];
                t++;
                i++;
            }
            else{  //反之将右边添加进去
                temp[ t ] = arr[ j ];
                t++;
                j++;

            }
        }
        //二把剩余数据的一边全部填入temp
        while (i <= mid) {  //说明左边元素还有剩余，将全部填充到temp
            temp[ t ] = arr[ i ];
            i++;
            t++;
        }
        while (j <= right) {
            temp[ t ] = arr[ j ];
            j++;
            t++;
        }
        //三
        //将temp数组的元素拷贝到arr
        //注意，并不是每次拷贝所有
        t = 0;
        int templeft = left;
        //第一合并0->1
        //最后一次合并就是0->arr.length-1
//        System.out.println ("templeft:"+templeft+"right:"+right );
        while (templeft <= right) {
            arr[ templeft ] = temp[ t ];
            t++;
            templeft++;
        }
    }

    private static void randomArr ( int[] arr ) {
        for ( int i = 0 ; i < arr.length ; i++ ) {
            arr[ i ] = (int) ( Math.random ( ) * 8000000 );  //会生成【0，8000000）直接的数
        }
    }

    /**
     * 将此时调用函数的时间格式化打出来
     *
     * @return 年-月-日 时-分秒
     */
    private static String Date ( ) {
        Date date1 = new Date ( );  //调函数的当前时间
        SimpleDateFormat simpleFormatter = new SimpleDateFormat ( "HH:mm:ss" );//格式化
        return simpleFormatter.format ( date1 );
    }
}

结果