sort-07-merge sort 归并排序

简介: 这是一个关于排序算法的系列文章摘要。文章涵盖了多种排序算法的详细解释,包括冒泡排序、快速排序、选择排序、堆排序、插入排序、希尔排序、归并排序、计数排序、桶排序以及大文件外部排序。归并排序是一种效率为O(nlogn)的排序算法,基于分治法,将序列分成两半,分别排序后再合并。文章提供了Java实现的递归和迭代版本。在归并排序的递归实现中,代码通过不断拆分和合并子序列完成排序,而迭代实现则是通过逐步增大子序列长度并进行两两归并来排序。整个系列可在GitHub找到相关源码。

排序系列

sort-00-排序算法汇总

sort-01-bubble sort 冒泡排序算法详解

sort-02-QuickSort 快速排序到底快在哪里?

sort-03-SelectSort 选择排序算法详解

sort-04-heap sort 堆排序算法详解

sort-05-insert sort 插入排序算法详解

sort-06-shell sort 希尔排序算法详解

sort-07-merge sort 归并排序

sort-08-counting sort 计数排序

sort-09-bucket sort 桶排序

sort-10-bigfile 大文件外部排序

归并排序(英语:Merge sort,或mergesort)

是创建在归并操作上的一种有效的排序算法,效率为 O(nlogn)(大O符号)。1945年由约翰·冯·诺伊曼首次提出。

该算法是采用分治法(Divide and Conquer)的一个非常典型的应用,且各层分治递归可以同时进行。

概述

采用分治法:

分割:递归地把当前序列平均分割成两半。

集成:在保持元素顺序的同时将上一步得到的子序列集成到一起(归并)。

java 实现递归法

递归法(Top-down)

  1. 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列

  2. 设定两个指针,最初位置分别为两个已经排序序列的起始位置

  3. 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置

  4. 重复步骤3直到某一指针到达序列尾

  5. 将另一序列剩下的所有元素直接复制到合并序列尾

java 实现

实际上代码实现也不难,不过递归多多少少让人看起来不太习惯。

我们后面会结合测试日志,再进行讲解。

package com.github.houbb.sort.core.api;

import com.github.houbb.log.integration.core.Log;
import com.github.houbb.log.integration.core.LogFactory;

import java.util.ArrayList;
import java.util.List;

/**
 * 归并排序-递归实现
 *
 * @author binbin.hou
 * @since 0.0.7
 */
public class MergeRecursiveSort extends AbstractSort {
   

    private static final Log log = LogFactory.getLog(MergeRecursiveSort.class);

    @Override
    @SuppressWarnings("all")
    protected void doSort(List<?> original) {
   
        // 存放归并的结果
        // 直接将数组填满,避免 set 出现越界
        List<?> resultList = new ArrayList<>(original);
        sortRecursive(original, resultList, 0, original.size()-1);
    }

    /**
     * 递归排序
     * @param originalList 原始列表
     * @param resultList 存放结果的列表
     * @param startIx 开始
     * @param endIx 结果
     * @since 0.0.7
     */
    @SuppressWarnings("all")
    private void sortRecursive(List originalList,
                               List resultList,
                               int startIx,
                               int endIx) {
   
        // 循环结束
        if(startIx >= endIx) {
   
            return;
        }

        // 找到中间位置,将列表一分为二
        int midIx = (startIx+endIx) / 2;
        int leftStart = startIx;
        int leftEnd = midIx;
        int rightStart = midIx+1;
        int rightEnd = endIx;

        if(log.isDebugEnabled()) {
   
            log.debug("拆分:ls: {}, le: {}, rs: {}, re: {}",
                    leftStart, leftEnd, rightStart, rightEnd);
        }

        // 递归调用
        sortRecursive(originalList, resultList, leftStart, leftEnd);
        sortRecursive(originalList, resultList, rightStart, rightEnd);

        if(log.isDebugEnabled()) {
   
            log.debug("操作:ls: {}, le: {}, rs: {}, re: {}",
                    leftStart, leftEnd, rightStart, rightEnd);
        }

        // 这里需要通过 k 记录一下开始的位置
        int k = startIx;
        while (leftStart <= leftEnd && rightStart <= rightEnd) {
   
            //相对小的元素放入到合并空间,并移动指针到下一位置
            Comparable left = (Comparable) originalList.get(leftStart);
            Comparable right = (Comparable) originalList.get(rightStart);

            // 左边较小,则放入合并空间
            if(left.compareTo(right) < 0) {
   
                resultList.set(k++, left);
                leftStart++;
            } else {
   
                resultList.set(k++, right);
                rightStart++;
            }
        }

        // 如果列表比较结束,将剩下的元素,全部放入到队列中。
        while (leftStart <= leftEnd) {
   
            resultList.set(k++, originalList.get(leftStart++));
        }
        while (rightStart <= rightEnd) {
   
            resultList.set(k++, originalList.get(rightStart++));
        }

        // 将结果统一拷贝到原始集合中
        for(int i = startIx; i <= endIx; i++) {
   
            originalList.set(i, resultList.get(i));
        }
    }

}

代码测试

List<Integer> list = RandomUtil.randomList(10);
System.out.println("开始排序:" + list);
SortHelper.mergeRecursive(list);
System.out.println("完成排序:" + list);

测试日志

为了让大家更加直观的理解整个拆分的过程,我们加了2行日志。

开始排序:[16, 90, 88, 27, 94, 99, 45, 66, 35, 33]
拆分:ls: 0, le: 4, rs: 5, re: 9    -- 0-9     拆分为:0-4, 5-9
拆分:ls: 0, le: 2, rs: 3, re: 4    -- 0-4 继续拆分为:0-2, 3-4 
拆分:ls: 0, le: 1, rs: 2, re: 2    -- 0-2 继续拆分为:0-1,2-2 
拆分:ls: 0, le: 0, rs: 1, re: 1    -- 0-1 继续拆分为:0-0, 1-1 
操作:ls: 0, le: 0, rs: 1, re: 1    -- 0-0 和 1-1 此时已经无法继续拆分,开始进行操作
操作:ls: 0, le: 1, rs: 2, re: 2
拆分:ls: 3, le: 3, rs: 4, re: 4
操作:ls: 3, le: 3, rs: 4, re: 4
操作:ls: 0, le: 2, rs: 3, re: 4
拆分:ls: 5, le: 7, rs: 8, re: 9
拆分:ls: 5, le: 6, rs: 7, re: 7
拆分:ls: 5, le: 5, rs: 6, re: 6
操作:ls: 5, le: 5, rs: 6, re: 6
操作:ls: 5, le: 6, rs: 7, re: 7
拆分:ls: 8, le: 8, rs: 9, re: 9
操作:ls: 8, le: 8, rs: 9, re: 9
操作:ls: 5, le: 7, rs: 8, re: 9
操作:ls: 0, le: 4, rs: 5, re: 9
完成排序:[16, 27, 33, 35, 45, 66, 88, 90, 94, 99]

这是 10 个元素的列表排序。

首先进行对半的拆分,当无法细分的时候,会对元素进行排序操作。

最后又会把拆分排序好的数组拼接起立。这样一个完整的数组就是有序的了。

当然这个排序也有一个很明显的缺点:那就是需要额外的空间复杂度。

java 迭代实现

相信很多小伙伴都知道迭代可以使得代码变得简洁,但是会让调试和理解变得复杂。

我们来一起学习一下迭代的实现方式。

迭代法(Bottom-up)

原理如下(假设序列共有 n 个元素):

  1. 将序列每相邻两个数字进行归并操作,形成 ceil(n/2) 个序列,排序后每个序列包含两/一个元素

  2. 若此时序列数不是1个则将上述序列再次归并,形成 ceil(n/4) 个序列,每个序列包含四/三个元素

  3. 重复步骤2,直到所有元素排序完毕,即序列数为1

迭代实现

相对递归,这个代码就要显得复杂很多。

不过这种迭代的方式性能更好,实现如下。

package com.github.houbb.sort.core.api;

import com.github.houbb.log.integration.core.Log;
import com.github.houbb.log.integration.core.LogFactory;
import com.github.houbb.sort.core.util.InnerSortUtil;

import java.util.ArrayList;
import java.util.List;

/**
 * 归并排序-迭代实现
 *
 * @author binbin.hou
 * @since 0.0.7
 */
public class MergeSort extends AbstractSort {
   

    private static final Log log = LogFactory.getLog(MergeSort.class);

    @Override
    protected void doSort(List<?> original) {
   
        // 存放归并的结果
        // 直接将数组填满,避免 set 出现越界
        List<?> resultList = new ArrayList<>(original);

        //起始,子序列长度为1。对长度为1的序列进行两两合并
        int k = 1;
        final int length = original.size();
        while (k < length) {
   
            mergePass(original, resultList, k, length);//将原先无序的数据两两归并入归并数组
            k = 2 * k;//子序列长度加倍
            mergePass(resultList, original, k, length);//将归并数组中已经两两归并的有序序列再归并回数组 original
            k = 2 * k;//子序列长度加倍
        }
    }

    /**
     * 负责将数组中的相邻的有k个元素的字序列进行归并
     *
     * @param original 原始列表
     * @param results 结果列表
     * @param s  子序列长度
     * @param len 长度
     * @since 0.0.7
     */
    @SuppressWarnings("all")
    private static void mergePass(List original, List results, int s, int len) {
   
        int i = 0;

        // 写成(i + 2 * k - 1 < len),就会把(i+2*k-1)当做一个整体看待
        // 从前往后,将2个长度为k的子序列合并为1个。
        // 对于序列{3, 4, 2, 5, 7, 0, 9, 8, 1, 6},当k=8的时候,因为i>(len-2*k+1),所以根本没有进入while循环
        while (i < len - 2 * s + 1) {
   
            merge(original, results, i, i + s - 1, i + 2 * s - 1);//两两归并
            i = i + 2 * s;
        }

        // 将那些“落单的”长度不足两两merge的部分和前面merge起来。
        // (连接起来之前也是要进行排序的,因此有了下面的merge操作)
        if (i < len - s + 1) {
   
            merge(original, results, i, i + s - 1, len - 1);//归并最后两个序列
        } else {
   
            for (int j = i; j < len; j++) {
   //若最后只剩下单个子序列
                results.set(j, original.get(j));
            }
        }
    }

    /**
     * 将两个有序数组合并成一个有序数组
     * @param original 原始
     * @param result 结果
     * @param low 开始
     * @param mid 中间
     * @param high 结束
     * @since 0.0.7
     */
    @SuppressWarnings("all")
    private static void merge(List original, List result, int low, int mid, int high) {
   
        int j, k, l;

        // 将记录由小到大地放进temp数组
        for (j = mid + 1, k = low; low <= mid && j <= high; k++) {
   
            if (InnerSortUtil.lt(original, low, j)) {
   
                result.set(k, original.get(low++));
            } else {
   
                result.set(k, original.get(j++));
            }
        }

        //接下来两循环是为了将剩余的(比另一边多出来的个数)放到temp数组中
        if (low <= mid) {
   
            for (l = 0; l <= mid - low; l++) {
   
                result.set(k + l, original.get(low + l));
            }
        }
        if (j <= high) {
   
            for (l = 0; l <= high - j; l++) {
   
                result.set(k + l, original.get(j + l));
            }
        }
    }

}

测试

List<Integer> list = RandomUtil.randomList(10);
System.out.println("开始排序:" + list);
SortHelper.merge(list);
System.out.println("完成排序:" + list);

日志如下:

开始排序:[38, 31, 7, 91, 25, 73, 3, 84, 70, 96]
完成排序:[3, 7, 25, 31, 38, 70, 73, 84, 91, 96]

开源地址

为了便于大家学习,上面的排序已经开源,开源地址:

https://github.com/houbb/sort

欢迎大家 fork/star,鼓励一下作者~~

小结

希望本文对你有帮助,如果有其他想法的话,也可以评论区和大家分享哦。

各位极客的点赞收藏转发,是老马持续写作的最大动力!

相关文章
|
7月前
|
存储
归并排序 merge_sort
归并排序 merge_sort
30 0
|
7月前
|
搜索推荐 算法 Java
sort-05-insert sort 插入排序算法详解
这是一个关于排序算法的系列文章总结,包括冒泡排序、快速排序、选择排序、堆排序、插入排序等10种排序算法的详细讲解和Java实现。插入排序是一种简单直观的排序算法,通过构建有序序列并逐个插入新元素来排序。提供的Java代码展示了插入排序的实现过程,并附有测试示例。所有算法已开源在GitHub项目[https://github.com/houbb/sort](https://github.com/houbb/sort)中。
|
7月前
|
存储 分布式计算 搜索推荐
sort-10-bigfile sort 大文件外部排序
这是一个关于排序算法系列的概述,包括冒泡排序、快速排序、选择排序、堆排序、插入排序、希尔排序、归并排序、计数排序、桶排序和大文件外部排序。大文件排序通过文件拆分、独立排序、合并排序和优化合并步骤实现,尤其适用于不能一次性加载到内存中的数据。该方法的时间复杂度为O(n log n),空间复杂度为O(n)。文章提供了一个Java实现的`BigFileSort`类,用于大文件的排序操作。代码中使用了归并排序的策略进行合并,并考虑了磁盘I/O的影响。完整代码可在GitHub的开源项目中找到。
|
搜索推荐 C++
C++利用sort进行排序
C++利用sort进行排序
|
7月前
|
搜索推荐 数据库 C++
带用排序等法sort讲解
带用排序等法sort讲解
44 0
|
7月前
|
C++
C++如何进行sort的使用——C++如何进行排序
C++如何进行sort的使用——C++如何进行排序
126 0
|
NoSQL Redis
SORT
SORT
106 0
|
搜索推荐 算法 数据可视化
【基础篇】9 # 排序:冒泡排序(Bubble Sort)、插入排序(Insertion Sort)、选择排序(Selection Sort)
【基础篇】9 # 排序:冒泡排序(Bubble Sort)、插入排序(Insertion Sort)、选择排序(Selection Sort)
119 0
【基础篇】9 # 排序:冒泡排序(Bubble Sort)、插入排序(Insertion Sort)、选择排序(Selection Sort)
|
存储 搜索推荐
十大排序之Merge Sort 归并排序
十大排序之Merge Sort 归并排序