算法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 条评论
登录 后参与评论

相关文章

来自专栏码云1024

JAVA 第二天 关键字

2917
来自专栏java一日一条

Java下static关键字用法详解

  本文章介绍了java下static关键字的用法,大部分内容摘自原作者,在此学习并分享给大家。

2143
来自专栏xx_Cc的学习总结专栏

OC-基础总结(一)

38811
来自专栏java达人

java中Comparator的用法

在java中,如果要对集合对象或数组对象进行排序,需要实现Comparator接口以达到我们想要的目标。 接下来我们模拟下在集合对象中对日期属性进行排序 一、实...

25410
来自专栏柠檬先生

es6 数组扩展方法

1.扩展运算符     含义: 扩展运算符,三个点(...),将一个数组转为用逗号分隔的参数顺序。       例如:         console.log(...

2329
来自专栏java初学

final关键字

37512
来自专栏Script Boy (CN-SIMO)

Java之继承、抽象类、接口篇

一、继承(extends) 什么是继承? 继承是对现实生活中的"分类"概念的一种模拟。 狮子拥有动物的一切基本特性,但同时又拥有自己的独特的特性,这就是"...

2300
来自专栏blackheart的专栏

[C#2] 5-迭代器

1.枚举数 枚举数是循环访问其关联集合的对象。它可被视作指向集合中任何元素的可移动的指针。 一个枚举数只能与一个集合关联,但一个集合可以具有多个枚举数。C#的f...

2005
来自专栏python3

python 集合

说明: 拿list_1每一个元素去list_2中查找,如果有,直接忽略,否则就直接输出。

1482
来自专栏博客园

.NET面试题解析(04)-类型、方法与继承

6. 在继承中new和override相同点和区别?看下面的代码,有一个基类A,B1和B2都继承自A,并且使用不同的方式改变了父类方法Print()的行为。测试...

1443

扫码关注云+社区

领取腾讯云代金券