专栏首页nnngu算法04 七大排序之:归并排序

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

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

首先来看一下归并排序(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("********展示结束********");
    }
}

运行结果:

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 算法01 七大排序之:冒泡排序和快速排序

    排序是我们生活中经常会面对的问题。同学们做操时会按照从矮到高排列;老师查看上课出勤情况时,会按学生学号顺序点名;高考录取时,会按成绩总分降序依次录取等。排序是数...

    nnngu
  • 算法03 七大排序之:直接插入排序和希尔排序

    上一篇总结了直接选择排序和堆排序,这一篇要总结的是插入排序中的直接插入排序和希尔排序,我们主要从以下几点进行总结。 1、直接插入排序及算法实现 2、希尔排序及算...

    nnngu
  • 算法02 七大排序之:直接选择排序和堆排序

    上一篇总结了交换排序的冒泡排序和快速排序。这一篇要总结的是选择排序,选择排序分为直接选择排序和堆排序,主要从以下几点进行总结。 1、直接选择排序及算法实现 2、...

    nnngu
  • P3183 [HAOI2016]食物链

    题目描述 如图所示为某生态系统的食物网示意图,据图回答第1小题现在给你n个物种和m条能量流动关系,求其中的食物链条数。物种的名称为从1到n编号M条能量流动关系形...

    attack
  • 让视频压制更简单

      一直待在一个美剧字幕组做后期压制工作,也经常被问到“要怎么压制?”这种即使用一二十句话都无法说清的问题。

    胡尐睿丶
  • 【HDU 2604】Queuing

      f和m两种字母组成字符串,fmf 和 fff 这种为不安全的字符串,现在有2*L个字母,问你有多少安全的字符串。答案mod M。

    饶文津
  • 魔法少女【动态规划问题】——NYOJ1204

    CN_Simo
  • POJ2236 (并查集)

    An earthquake takes place in Southeast Asia. The ACM (Asia Cooperated Medical te...

    dejavu1zz
  • python—多任务版udp聊天机器人

    py3study
  • android贝塞尔曲线实现波浪效果

    本文实例为大家分享了android贝塞尔曲线实现波浪效果的具体代码,供大家参考,具体内容如下

    砸漏

扫码关注云+社区

领取腾讯云代金券