美文网首页
算法04 七大排序之:归并排序

算法04 七大排序之:归并排序

作者: nnngu | 来源:发表于2018-01-21 05:42 被阅读19次

    作者:nnngu
    GitHub:https://github.com/nnngu
    博客园:http://www.cnblogs.com/nnngu
    简书:https://www.jianshu.com/users/1df20d76ea5c
    知乎:https://www.zhihu.com/people/nnngu/posts


    上一篇总结了直接插入排序和希尔排序,这一篇要总结的是归并排序,这也是七大排序的最后一种排序算法。

    首先来看一下归并排序(Merge Sort) 的基本原理。它的原理是假设初始序列有n个元素,则可以看成是n个有序的子序列,每个子序列的长度为1,然后两两归并,得到n/2个长度为2或1的有序子序列;再两两归并,…… ,如此重复,直至得到一个长度为n的有序序列为止,这种排序方法就称为归并排序。

    1、归并排序的示意图

    下面用示意图来说明归并排序的过程:

    图一:

    2、归并排序的代码

    MergeSort.java

    public class MergeSort {
        public static void main(String[] args) {
            int[] list = {50, 10, 90, 30, 70};
            System.out.println("************归并排序************");
            System.out.println("排序前:");
            display(list);
            System.out.println("");
    
            System.out.println("排序后:");
            mergeSort(list, new int[list.length], 0, list.length - 1);
            display(list);
        }
    
        /**
         * 归并排序算法
         *
         * @param list     待排序的列表
         * @param tempList 临时列表
         * @param head     列表开始位置
         * @param rear     列表结束位置
         */
        public static void mergeSort(int[] list, int[] tempList, int head, int rear) {
            if (head < rear) {
                // 取分割位置
                int middle = (head + rear) / 2;
                // 递归划分列表的左序列
                mergeSort(list, tempList, head, middle);
                // 递归划分列表的右序列
                mergeSort(list, tempList, middle + 1, rear);
                // 列表的合并操作
                merge(list, tempList, head, middle + 1, rear);
            }
        }
    
        /**
         * 合并操作(列表的两两合并)
         *
         * @param list
         * @param tempList
         * @param head
         * @param middle
         * @param rear
         */
        public static void merge(int[] list, int[] tempList, int head, int middle, int rear) {
            // 左指针尾
            int headEnd = middle - 1;
            // 右指针头
            int rearStart = middle;
            // 临时列表的下标
            int tempIndex = head;
            // 列表合并后的长度
            int tempLength = rear - head + 1;
    
            // 先循环两个区间段都没有结束的情况
            while ((headEnd >= head) && (rearStart <= rear)) {
                // 如果发现右序列大,则将此数放入临时列表
                if (list[head] < list[rearStart]) {
                    tempList[tempIndex++] = list[head++];
                } else {
                    tempList[tempIndex++] = list[rearStart++];
                }
            }
    
            // 判断左序列是否结束
            while (head <= headEnd) {
                tempList[tempIndex++] = list[head++];
            }
    
            // 判断右序列是否结束
            while (rearStart <= rear) {
                tempList[tempIndex++] = list[rearStart++];
            }
    
            // 交换数据
            for (int i = 0; i < tempLength; i++) {
                list[rear] = tempList[rear];
                rear--;
            }
        }
    
        /**
         * 遍历打印
         */
        public static void display(int[] list) {
            System.out.println("********展示开始********");
            if (list != null && list.length > 0) {
                for (int num :
                        list) {
                    System.out.print(num + " ");
                }
                System.out.println("");
            }
            System.out.println("********展示结束********");
        }
    }
    

    运行结果:

    相关文章

      网友评论

          本文标题:算法04 七大排序之:归并排序

          本文链接:https://www.haomeiwen.com/subject/ocxfaxtx.html