动画｜经典的归并排序究竟怎么玩儿？

作者 | 菠了个菜
责编 | 郭芮

由于LeetCode上的算法题很多涉及到一些基础的数据结构&＃xff0c;为了更好的理解后续更新的一些复杂题目的动画&＃xff0c;推出一个新系列——《图解数据结构》&＃xff0c;主要使用动画来描述常见的数据结构和算法&＃xff0c;本文分析归并排序。

归并排序&＃xff08;Merge sort&＃xff09;是建立在归并操作上的一种有效的排序算法&＃xff0c;该算法是采用分治法&＃xff08;Divide and Conquer&＃xff09;的一个非常典型的应用。

作为一种典型的分而治之思想的算法应用&＃xff0c;归并排序的实现有两种方法&＃xff1a;

• 自上而下的递归&＃xff08;所有递归的方法都可以用迭代重写&＃xff0c;所以就有了第 2 种方法&＃xff09;&＃xff1b;

• 自下而上的迭代&＃xff1b;

和选择排序一样&＃xff0c;归并排序的性能不受输入数据的影响&＃xff0c;但表现比选择排序好的多&＃xff0c;因为始终都是 O(nlogn) 的时间复杂度&＃xff0c;代价是需要额外的内存空间。

算法步骤

• 申请空间&＃xff0c;使其大小为两个已经排序序列之和&＃xff0c;该空间用来存放合并后的序列&＃xff1b;

• 设定两个指针&＃xff0c;最初位置分别为两个已经排序序列的起始位置&＃xff1b;

• 比较两个指针所指向的元素&＃xff0c;选择相对小的元素放入到合并空间&＃xff0c;并移动指针到下一位置&＃xff1b;

• 重复步骤 3 直到某一指针达到序列尾&＃xff1b;

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

来源&＃xff1a;https://github.com/hustcc/JS-Sorting-Algorithm。

算法演示

排序动画过程解释&＃xff1a;

• 首先&＃xff0c;将数字分割成两片区域&＃xff1b;

• 再将数字分割成两片区域&＃xff1b;

• 依次划分

• 直到每片区域只有一个元素

• 分割完成

• 接下来&＃xff0c;将分割的每片区域进行合并组合

• 合并时&＃xff0c;按照数字的升序移动&＃xff0c;使得合并后的数字在组内按升序排列

• 当合并包含多个数字的组时&＃xff0c;比较开头的数字&＃xff0c;移动其中较小的数字

• 比如在动画中&＃xff0c;比较开头的 4 和 3

• 其中 4 大于 3&＃xff0c; 因此移动 3

• 按照同样的逻辑去比较该列剩余的头数

• 4 小于 7 &＃xff0c;所以移动 4

• 同样的逻辑去进行接下来的操作

• 递归的重复组的合并操作&＃xff0c;直到所有数字都在一个组中。

• 完成归并排序。

代码实现

为了更好的让读者用自己熟悉的编程语言来理解动画&＃xff0c;笔者将贴出多种编程语言的参考代码&＃xff0c;代码全部来源于网上。

Java代码实现&＃xff1a;

public class MergeSort implements IArraySort {

    &＃64;Override
    public int[] sort(int[] sourceArray) throws Exception {
        // 对 arr 进行拷贝&＃xff0c;不改变参数内容
        int[] arr &＃61; Arrays.copyOf(sourceArray, sourceArray.length);

        if (arr.length < 2) {
            return arr;
        }
        int middle &＃61; (int) Math.floor(arr.length / 2);

        int[] left &＃61; Arrays.copyOfRange(arr, 0, middle);
        int[] right &＃61; Arrays.copyOfRange(arr, middle, arr.length);

        return merge(sort(left), sort(right));
    }

    protected int[] merge(int[] left, int[] right) {
        int[] result &＃61; new int[left.length &＃43; right.length];
        int i &＃61; 0;
        while (left.length > 0 && right.length > 0) {
            if (left[0] <&＃61; right[0]) {
                result[i&＃43;&＃43;] &＃61; left[0];
                left &＃61; Arrays.copyOfRange(left, 1, left.length);
            } else {
                result[i&＃43;&＃43;] &＃61; right[0];
                right &＃61; Arrays.copyOfRange(right, 1, right.length);
            }
        }

        while (left.length > 0) {
            result[i&＃43;&＃43;] &＃61; left[0];
            left &＃61; Arrays.copyOfRange(left, 1, left.length);
        }

        while (right.length > 0) {
            result[i&＃43;&＃43;] &＃61; right[0];
            right &＃61; Arrays.copyOfRange(right, 1, right.length);
        }

        return result;
    }

}


Python代码实现&＃xff1a;

def mergeSort(arr):
    import math
    if(len(arr)<2):
        return arr
    middle &＃61; math.floor(len(arr)/2)
    left, right &＃61; arr[0:middle], arr[middle:]
    return merge(mergeSort(left), mergeSort(right))

def merge(left,right):
    result &＃61; []
    while left and right:
        if left[0] <&＃61; right[0]:
            result.append(left.pop(0));
        else:
            result.append(right.pop(0));
    while left:
        result.append(left.pop(0));
    while right:
        result.append(right.pop(0));
    return result


Javascript代码实现&＃xff1a;

function mergeSort(arr) {  // 采用自上而下的递归方法
    var len &＃61; arr.length;
    if(len < 2) {
        return arr;
    }
    var middle &＃61; Math.floor(len / 2),
        left &＃61; arr.slice(0, middle),
        right &＃61; arr.slice(middle);
    return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right)
{
    var result &＃61; [];

    while (left.length && right.length) {
        if (left[0] <&＃61; right[0]) {
            result.push(left.shift());
        } else {
            result.push(right.shift());
        }
    }

    while (left.length)
        result.push(left.shift());

    while (right.length)
        result.push(right.shift());

    return result;
}


GO代码实现&＃xff1a;

func mergeSort(arr []int) []int {
    length :&＃61; len(arr)
    if length < 2 {
        return arr
    }
    middle :&＃61; length / 2
    left :&＃61; arr[0:middle]
    right :&＃61; arr[middle:]
    return merge(mergeSort(left), mergeSort(right))
}

func merge(left []int, right []int) []int {
    var result []int
    for len(left) !&＃61; 0 && len(right) !&＃61; 0 {
        if left[0] <&＃61; right[0] {
            result &＃61; append(result, left[0])
            left &＃61; left[1:]
        } else {
            result &＃61; append(result, right[0])
            right &＃61; right[1:]
        }
    }

    for len(left) !&＃61; 0 {
        result &＃61; append(result, left[0])
        left &＃61; left[1:]
    }

    for len(right) !&＃61; 0 {
        result &＃61; append(result, right[0])
        right &＃61; right[1:]
    }

    return result
}


如果你是iOS开发者&＃xff0c;可以在GitHub上 https://github.com/MisterBooo/Play-With-Sort-OC 获取更直观可调试运行的源码。

作者简介&＃xff1a;菠了个菜&＃xff0c;本文首发于个人公众号「五分钟学算法」。「五分钟学算法」是致力于通过各种动画的形式来描绘出各种数据结构&＃xff0c;并图解LeetCode原题的学习平台&＃xff0c;一起学习&＃xff0c;一起进步&＃xff01;

声明&＃xff1a;本文为作者投稿&＃xff0c;版权归其个人所有。

 热 文 推 荐 

春运车票为谁“秒空”&＃xff1f;第三方软件的困与危

编程 25 年后&＃xff0c;现实将我打回菜鸟程序员的起点

前方 Bug 出没&＃xff1f;盘他&＃xff01;

☞“离开360时&＃xff0c;它只给了我一块钱”

☞ 原子互换&＃xff1a;一统公链江湖的神来之笔

☞ AI找Bug&＃xff0c;一键快速预测

☞ 5G大规模商用来临之前&＃xff0c;你必须知道的几个知识点

☞ 女程序员&＃xff1a;我敲代码养家&＃xff0c;老公负责貌美如花&＃xff01;

print_r(&＃39;点个好看吧&＃xff01;&＃39;);
var_dump(&＃39;点个好看吧&＃xff01;&＃39;);
NSLog(&＃64;"点个好看吧&＃xff01;");
System.out.println("点个好看吧&＃xff01;");
console.log("点个好看吧&＃xff01;");
print("点个好看吧&＃xff01;");
printf("点个好看吧&＃xff01;\n");
cout << "点个好看吧&＃xff01;" << endl;
Console.WriteLine("点个好看吧&＃xff01;");
fmt.Println("点个好看吧&＃xff01;");
Response.Write("点个好看吧&＃xff01;");
alert("点个好看吧&＃xff01;")
echo "点个好看吧&＃xff01;"