数据结构和算法-14-归并排序

傷城~ 2022-01-07 03:07 200阅读 0赞

前面一篇快速排序用到了递归，接下来的归并排序也需要使用递归思想。

**1.归并排序介绍**

归并排序（MergeSort）是才有分治法的一个非常典型的应用。归并排序的思想就是先递归分解数组，再合并数组。

将数组分解最小之后，然后合并两个有序数组，基本思路是比较两个数组的最前面的数，谁小先把谁取出来，取了之后相应的指针往后移一位，然后再比较，直到一个数组为空，最后把另外一个数组的剩余部分复制过来即可。

**2.分析和图解**

这里我网上找到一个动态效果图，先来看看效果。

![640_wx_fmt_gif_tp_webp_wxfrom_5_wx_lazy_1][]

一开始拆分了多个组，橙色，红色，浅黄色，淡蓝色，绿色，蓝色。每组继续拆分之后只剩下一个元素，然后开始进行合并，先左边几个组合并成一个大的红色组，小的数排前面，大的数排后面。然后右侧合并成一个大组，最后左右两个大组合并成一个完整序列。

**3.代码实现**

python代码实现

# coding:utf-8
    
    
    def merge_sort(alist):
        """归并排序"""
        n = len(alist)
    
        # 拆分到每个数列只有一个元素
        if n <= 1:
            return alist
        # 每次对半长度拆分
        mid = n // 2
    
        # left 部分 采用归并排序后形成的新的有序数列，递归调用
        left_li = merge_sort(alist[:mid])
        # right 部分 采用归并排序后形成的新的有序数列，递归调用
        right_li = merge_sort(alist[mid:])
    
        # 将两个有序子序列合并成一个新的整体，merge(left_li, right_li)
        # 定义两个游标，分别用来确定左边和右边序列最小数
        left_pointer, right_pointer = 0, 0
        # 一个空列表用来装合并的数列
        result = []
    
        while left_pointer < len(left_li) and right_pointer < len(right_li):
            # 从左边和右边拿出第一个元素来比较，取最小的出来
            if left_li[left_pointer] < right_li[right_pointer]:
                # 最小的元素添加到result数列中,游标移动
                result.append(left_li[left_pointer])
                left_pointer += 1
            else:
                result.append(right_li[right_pointer])
                right_pointer += 1
        # 不断合并前面拆分小组数列到result中，先左边再右边
        result += left_li[left_pointer:]
        result += right_li[right_pointer:]
        return result
    
    
    if __name__ == "__main__":
        li = [54, 26, 93, 17, 77, 31, 44, 55, 20]
        print(li)
        li_new = merge_sort(li)
        print(li_new)

运行结果：

[54, 26, 93, 17, 77, 31, 44, 55, 20]
    [17, 20, 26, 31, 44, 54, 55, 77, 93]

Java代码实现

import java.util.Arrays;
    import java.util.Collections;
    import java.util.List;
    import java.util.ArrayList;
    
    
    public class MergeSort {
    
        public static void main(String[] args){
            int[] arr = {17, 20, 93, 54, 77, 32, 45, 226};
            System.out.println(Arrays.toString(arr));
            int[] result = mergeSort(arr);
            System.out.println(Arrays.toString(result));
        }
    
        public static int[] mergeSort(int[] alist){
            int n = alist.length;
            // 拆分到每个数列只有一个元素
            if (n <= 1) {
                return alist;
            }
            // 每次对半长度拆分
            int mid = n / 2;
    
            // left 部分 采用归并排序后形成的新的有序数列，递归调用
            int[] left_li = mergeSort(Arrays.copyOfRange(alist, 0, mid));
            // right 部分 采用归并排序后形成的新的有序数列，递归调用
            int[] right_li = mergeSort(Arrays.copyOfRange(alist, mid, alist.length));
    
             // 将两个有序子序列合并成一个新的整体，merge(left_li, right_li)
             // 定义两个游标，分别用来确定左边和右边序列最小数
            int left_pointer = 0;
            int right_pointer = 0;
             // 一个空列表用来装合并的数列,java中数组是没有添加元素的方法，所以这里选择list集合
            List<Integer> result =new ArrayList<Integer>();
    
            while (left_pointer < left_li.length  && right_pointer < right_li.length){
                // 从左边和右边拿出第一个元素来比较，取最小的出来
                if (left_li[left_pointer] < right_li[right_pointer]) {
                    // 最小的元素添加到result数列中,游标移动
                    result.add(left_li[left_pointer]);
                    left_pointer += 1;
                } else {
                    result.add(right_li[right_pointer]);
                    right_pointer += 1;
                }
            }
    
            // 不断合并前面拆分小组数列到result中，先左边再右边
            for(int i = left_pointer; i < left_li.length; i++) {
                result.add(left_li[i]);
            }
    
            for(int i = right_pointer; i < right_li.length; i++) {
                result.add(right_li[i]);
            }
    
            // 把list类型转换成int[] 数组返回
            int[] result_end = new int[result.size()];
            for(int i=0; i < result.size(); i++) {
                result_end[i] = result.get(i);
            }
            return result_end;
        }
    }

上面在获取子序列中，建议还是不要使用Arrays.copyOfRange的方法，可以多写两个for循环来代替。

运行结果和上面python是一样的

**4.常见排序算法的效率比较**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE1NDE5NDY_size_16_color_FFFFFF_t_70][]

总结：一般来说，面试过程中可能问你知道哪些排序方法，然后你选择一个你会的写出来。一般来说，如果你选择写冒泡排序是会人鄙视。总的来说，我们前面学习过的6中排序，我们基本上会写其中三种，重点是快速排序，归并排序确实比较难理解。推荐重点掌握，快速排序，冒泡排序，选择排序。插入排序。

[640_wx_fmt_gif_tp_webp_wxfrom_5_wx_lazy_1]: /images/20211227/1f99b81a306b4ef98fdce3b854ab0897.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE1NDE5NDY_size_16_color_FFFFFF_t_70]: /images/20211227/a0571950df094e069f9bf6534f2d217d.png