归并排序理解与实例_归并排序生活中例子

如何从简单的排序理解归并排序

1. 两个有序数组的合并：
   假如给你两个已经从小到大排好序的整数数组，a1 = [1,3,5,7,9], a2 = [2,4,6,8], 使输出一个包含a1，a2所有元素的从小到大排好序的数组，当然我们视觉判断就能得出答案s = [1,2,3,4,5,6,7,8,9]
2. 合并的原理：
   现在稍加深入的想，这样的结果如何得到的，不难看出是依次从a1中拿一个数与从a2中拿一个比较，如果a1中的小就把a1中的数取出来，接着比较a1中下一个，再比较，如果a2中的小就把a2中的数取出来，直到a1 和a2中所有的数都取出来
3. 如何更形象地理解合并过程：
   因为我们最终的结果需要包含所有a1和a2中的元素，即结果中允许重复的数据，所以最终的数组s的长度是
   n = len(a1) + len(a2)
   想象一下我们新建长度为n的整型数组，我们只需要从 0 至 n-1 索引位 k 填充数据即可，而这个数据的来源就是第2步中比较后拿出来较小的数（或者两数相等时从任一数组取出都可的数）。
   第2步的过程中，我们肯定需要分别遍历a1和a2，那么遍历两个数组的索引 i 和 j 的和，就应该是s数组的索引k, 随着k的更新，我们只需要更新i 或 j的大小，更新i还是更新j，取决于第2步拿出的较小的数属于a1还是a2

基础代码框架

根据以上的分析我们可以得出一个简单的代码框架

def mergeSort(a1, a2):
    n = len(a1) + len(a2)
    s = [float('inf')] * n  # 定义保存结果的数组，长度是n，如果不理解float('inf'),也可以随便设置元素值，只做占位符的效果
    i = j = 0
    for k in range(0, n):  # 每循环一次都会为此位置的索引赋值
        if i>=len(a1) or (j<len(a2) and a1[i]>a2[j]):
    # 判断条件的含义：第一种情况：a1遍历完了，只能从a2中取；第二种情况：两个都没有遍历完，但是a2[j]<a1[i],也是从a2中取
            s[k] = a2[j]
            j += 1  # 因为从a2中取，所以更新j
        else:
    # 其它情况都从a1中取第i个位置的数，放入s[k]
            s[k] = a1[i]
            i += 1  # 因为从a1中取，所以更新i
    print(s)
    
if __name__ == '__main__':
    a1 = [1,3,5,7,9]
    a2 = [2,4,6,8]
    mergeSort(a1, a2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

算法的变种

以上基本已经解释了归并排序的原理，但我们遇到的实际情况不论是题目还是项目，都很难有那么好的先决条件：a1 和 a2都是从小到大有序的。更多情况是给出一个未排序的整型数组 a ，使用归并排序算法又该怎么处理呢？以上的思想还能不能使用呢？
答案当然是仍然按照以上的思想，只不过我们需要创造这样一个条件，给提供两个有序的数组a1，a2，怎么提供这两个有序的数组，视具体条件而定，一下给出两种场景，帮助你学会变通处理：

数组是从大到小的情况

class Solution:
    def mergeSort(self, a1, a2):
        n1 = len(a1)
        n2 = len(a2)
        s = [float('inf')] * (n1 + n2)
        i = 0
        j = -1
        for k in range(0, n1+n2):
            if i>=n1 or (-j<n2+1 and a1[i]>a2[j]):
                s[i-j-1] = a2[j]
                j -= 1
            else:
                s[i-j-1] = a1[i]
                i+=1
        print(s)


if __name__ == '__main__':
    s1 = [1, 1, 3, 4]
    s2 = [11, 8, 5, 3, 1]
    s = Solution()
    s.mergeSort(s1, s2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

以上代码很容易理解，基本就是将j变成从 -1 到 -n2，从后向前遍历而已

一个数组排序

一个数组我们如何使之变成两个？当然是拆分，拆分之后又如何使这两个有序？我们需要知道，比较a1和a2中的两个元素是我们最终决定取哪个值放在s中去的，所以最基本的就是a1 a2都是长度为1的数组时候，本身就是已经有序的了。而这种思想让我们想到了递归
递归就是从基本的两个长度都为1的数组开始，输出一个合并后的有序的数组，然后再将这个有序的合并后的作为a1，再与另一半有序的a2继续进行合并，以此类推，只不过我们需要将这个过程反过来通过代码实现

class Solution:
    def mergeSort(self, a, a1, a2):
        n1 = len(a1)
        n2 = len(a2)
        i = 0
        j = 0
        while i+j < len(a):  # 因为有递归的存在，此处不能再用固定长度的循环了，要根据a1 和a2的长度来定，这样更准确，当然可以更新到上面的递归框架，更严谨
            if i >= n1 or (j < n2 and a1[i] > a2[j]):
                a[i + j] = a2[j]
                j += 1
            else:
                a[i + j] = a1[i]
                i += 1

    def sort(self, a):
        if len(a) < 2:
            return
        mid = len(a) // 2
        a1 = a[:mid]
        a2 = a[mid:]
        self.sort(a1)
        self.sort(a2)
        self.mergeSort(a, a1, a2)


if __name__ == '__main__':
    a = [5, 2, 7, 4， 12, 4, 9]
    s = Solution()
    s.sort(a)
    print(a)
    # a 因为传递的是列表（属于可变参数）,只需更新a对应位置的元素即可，相当于一个全局变量
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

使用递归的方法可能较难理解，需要多练习自然就建立起了递归的思想。但归并的逻辑依然没有改变，只要用归并排序的方法，就离不开这个思路，后续遇到其它变种的样例会继续补充。