图解数据结构和算法(四) · 归并排序(Merge Sort) java实现

图解数据结构和算法(四) · 归并排序(Merge Sort) java实现

java实现归并排序

简介

归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。

定义

归并排序是指将两个或两个以上有序的数列(或有序表),合并成一个仍然有序的数列(或有序表)。这样的排序方法经常用于多个有序的数据文件归并成一个有序的数据文件。

时间复杂度 O(n logn)

改进归并排序在归并时先判断前段序列的最大值与后段序列最小值的关系再确定是否进行复制比较。如果前段序列的最大值小于等于后段序列最小值,则说明序列可以直接形成一段有序序列不需要再归并,反之则需要。所以在序列本身有序的情况下时间复杂度可以降至O(n)

插入过程

图解

left数组依次与right数组对比,每次取小的放入新数组中。过程如下

  • i(0)=2 < j(0)=3 ==选择小的i(0) ==> k(0)=i(0)=2 i往上移动一格变为1,k往右移动一格变为1,j不变为0 i=1 k=1 j=0

  • i(1)=7 > j(0)=3 ==选择小的j(0) ==> k(1)=j(0)=3 j往上移动一格变为1,k往右移动一格变为2,i不变为1 i=1 k=2 j=1

  • j(1)=9 > i(1)=7 ==选择小的i(1) ==> k(2)=i(1)=7 i往上移动一格变为2,k往右移动一格变为3,j不变为1 i=2 k=3 j=1

  • i(2)=12 > j(1)=9 ==选择小的j(1) ==> k(3)=j(1)=9 j往上移动一格变为2,k往右移动一格变为4,i不变为2 i=2 k=4 j=2

  • j(2)=12 > i(2)=10 ==选择小的i(2) ==> k(4)=i(2)=10 i往上移动一格变为3,k往右移动一格变为5,j不变为2 i=3 k=5 j=2

  • i(3)=11 < i(2)=12 ==选择小的i(3) ==> k(5)=i(3)=11 这时候 i 已经达到最大值。

  • 将right数组中剩余的2个元素(12)和(18)拷贝到新数组中

使用java实现以上的合并逻辑

    public static void merge(Integer[] data, int L, int M, int R) {
        int LEFT_SIZE = M - L;//切割后,左边数组的长度
        int RIGHT_SIZE = R - M + 1;//右边数组的长度

        Integer[] leftArray = new Integer[LEFT_SIZE];  //初始左边化数组
        Integer[] rightArray = new Integer[RIGHT_SIZE];//初始化右边数组

        //计算切割后的左边数组
        for (int i=L; i<M; i++){
            leftArray[i - L] = data[i];
        }

        //右边数组
        for (int i=M; i<=R; i++) {
            rightArray[i - M] = data[i];
        }

        //生成新的临时数组 newArray
        Integer[] newArray = new Integer[LEFT_SIZE + RIGHT_SIZE];
        int i = 0 //left数组索引初始值
           ,j = 0 //right数组初始索引值
           ,k = 0;//新数组初始索引值

        //循环比较,
        while (i<LEFT_SIZE && j<RIGHT_SIZE){
            if(leftArray[i] < rightArray[j]){
                //说明left数组中的值小,将值赋值给newArray
                newArray[k] = leftArray[i];
                //同时左边游标上移动一格
                i++;
            }else{
                //说明right数组中的值小,将值赋值给newArray
                newArray[k] = rightArray[j];
                //同时右边游标上移动一格
                j++;
            }
            //每次比较完毕,newArray都需要右移动一格
            k++;
        }

        //如果左边数组还存在值,直接拷贝到newArray中
        while (i < LEFT_SIZE){
            newArray[k] = leftArray[i];
            k++;
            i++;
        }

        //如果右边数组还存在值,直接拷贝到newArray中
        while (j < RIGHT_SIZE) {
            newArray[k] = rightArray[j];
            j++;
            k++;
        }
}

如何才能让拆分过后的left和right数组都已排好序了呢?

答案很简单。让left和right数组中都只存在一个元素即可,因为只存在一个元素的话,本身就是已排序的数组

拆分数组

    /**
     * 递归进行拆分,直到拆分为所有元素数组长度为1为止
     * @param data  源数组
     * @param L     起点索引
     * @param R     终点索引
     */
    private static void sortAndMerge(Integer[] data,int L,int R){
        //如果起始索引位置一样,则说明只存在一个元素,递归开始回溯
        if(L == R){
            return;
        }
        int M = (R + L) / 2;   // 这儿默认向下取整,后面合并时需要加1
        sortAndMerge(data,L,M);
        sortAndMerge(data,M + 1,R);
        /**
         * 这儿的M为什么要加1  ???
         * 如上图所示,L=0 R=7 M=4
         * 这里的 ( R + L)/2 默认向下取整,算出来实际为3 所以需要加1
         */
        merge(data,L,M + 1,R);
    }

完整代码实现

package sort;

public class MergeSort {

    private static Integer[] sortArrays = {3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};
    private static int sortCnt= 0;

    public static void main(String[] args) {
        sortAndMerge(sortArrays,0,sortArrays.length - 1);
    }

    /**
     * 递归进行拆分,直到拆分为所有元素数组长度为1为止
     * @param data  源数组
     * @param L     起点索引
     * @param R     终点索引
     */
    private static void sortAndMerge(Integer[] data,int L,int R){
 
        if(L == R){
            return;
        }
        int M = (R + L) / 2;   // 这儿默认向下取整,后面合并时需要加1
        sortAndMerge(data,L,M);
        sortAndMerge(data,M + 1,R);
        /**
         * 这儿的M为什么要加1  ???
         * 如上图所示,L=0 R=7 M=4
         * 这里的 ( R + L)/2 默认向下取整,算出来实际为3 所以需要加1
         */
        merge(data,L,M + 1,R);
    }

    /**
     * 合并
     * @param data        原始数组
     * @param L           数组初始索引
     * @param M           中间切割数组的索引
     * @param R           终点索引
     */
    public static void merge(Integer[] data, int L, int M, int R) {
        int LEFT_SIZE = M - L;//切割后,左边数组的长度
        int RIGHT_SIZE = R - M + 1;//右边数组的长度

        Integer[] leftArray = new Integer[LEFT_SIZE];  //初始左边化数组
        Integer[] rightArray = new Integer[RIGHT_SIZE];//初始化右边数组

        //计算切割后的左边数组
        for (int i=L; i<M; i++){
            leftArray[i - L] = data[i];
        }

        //右边数组
        for (int i=M; i<=R; i++) {
            rightArray[i - M] = data[i];
        }

        //生成新的临时数组 newArray
        Integer[] newArray = new Integer[LEFT_SIZE + RIGHT_SIZE];
        int i = 0 //left数组索引初始值
           ,j = 0 //right数组初始索引值
           ,k = 0;//新数组初始索引值

        //循环比较,
        while (i<LEFT_SIZE && j<RIGHT_SIZE){
            if(leftArray[i] < rightArray[j]){
                //说明left数组中的值小,将值赋值给newArray
                newArray[k] = leftArray[i];
                //同时左边游标上移动一格
                i++;
            }else{
                //说明right数组中的值小,将值赋值给newArray
                newArray[k] = rightArray[j];
                //同时右边游标上移动一格
                j++;
            }
            //每次比较完毕,newArray都需要右移动一格
            k++;
        }

        //如果左边数组还存在值,直接拷贝到newArray中
        while (i < LEFT_SIZE){
            newArray[k] = leftArray[i];
            k++;
            i++;
        }

        //如果右边数组还存在值,直接拷贝到newArray中
        while (j < RIGHT_SIZE) {
            newArray[k] = rightArray[j];
            j++;
            k++;
        }

        //拷贝到原数组 从L为开始索引
        for (Integer integer : newArray) {
             data[L] = integer;
             L++ ;
        }

        System.out.println("第" + sortCnt++ + "次:");

        for (Integer datum : data) {
            System.out.print(datum + "\t");
        }
        System.out.println();
    }

}

上一章(图解数据结构与算法 · 冒泡排序 java实现)

# 算法  java  排序 

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×