...
 Algorithms

『Merge Sort 』详解「归并排序」的Python实现

...
hokyo
发布于 4 年, 8 ヶ月 之前
2935
0

归并排序

1.分治思想 divide and conquer

这个概念网上有很多，维基百科：分治法。

在计算机科学中，分治法是建基于多项分支递归的一种很重要的算法范式。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。
这个技巧是很多高效算法的基础，如排序算法（归并排序、快速排序）、傅立叶变换（快速傅立叶变换）。

我总结起来大概就是。

a. 一个很复杂的事情
b. 分解成若干的小事情
c. 然后重新组合

就比较像日常生活中造飞机，车等组件一样。是一个分开，然后重组的过程。

2.归并排序概念

主要是通过分割和重组进行的一种分治思想的算法。
大概有递归和迭代2种实现方式。

这里我也是参考了维基百科对于归并排序的理解。维基百科：归并排序
下面把主要精力放在代码实现上面。

3. 代码实现

3-1 写之前的我

首先我知道原理是这样的，就是把一个数组进行2分，一直分到不能再分的时候进行对于大小。
大概实现应该是分和比较然后合并。那么就应该是2个函数。

  • 数组分为左右2段
  • 左右2段分别排序(递归)
  • 排序好的数组进行合并

3-2 开始写的我

不会写。。主要思路是没有。放入什么进去，放入什么出来呢。
这个时候我看了网上写的办法，然后进行了一定的参考，通过回忆写出来。
现在我先来实现2个有序列表进行组成1个有序列表。
思路就是取2个数组从头开始的指针，相互对比，小的那么就添加进新的列表。 

"""  
合并2个有序数组  
方法1：通用方法  
"""  
def merge_two_sorted_array(arrA, arrB):  
    arrA_index, arrB_index = 0, 0  
    sorted_array = []  
    while arrA_index < len(arrA) and arrB_index < len(arrB):  
        if arrA[arrA_index] < arrB[arrB_index]:  
            sorted_array.append(arrA[arrA_index])  
            arrA_index += 1  
        else:  
            sorted_array.append(arrB[arrB_index])  
            arrB_index += 1  
    while arrA_index < len(arrA):  
        sorted_array.append(arrA[arrA_index])  
        arrA_index += 1  

    while arrB_index < len(arrB):  
        sorted_array.append(arrB[arrB_index])  
        arrB_index += 1  
    return sorted_array  

arrA = [ -5, 1, 3, 8, 9]  
arrB = [ 0, 3, 9, 16, 33]  
print(merge_two_sorted_array(arrA, arrB))  

# result  
# [-5, 0, 1, 3, 3, 8, 9, 9, 16, 33]  

"""  
合并2个有序数组  
方法1：python切片  
"""  
def merge_two_sorted_array_slice(arrA, arrB):  
    arrA_index, arrB_index = 0, 0  
    sorted_array = []  
    while arrA_index < len(arrA) and arrB_index < len(arrB):  
        if arrA[arrA_index] < arrB[arrB_index]:  
            sorted_array.append(arrA[arrA_index])  
            arrA_index += 1  
        else:  
            sorted_array.append(arrB[arrB_index])  
            arrB_index += 1  
    sorted_array += arrA[arrA_index:]  
    sorted_array += arrB[arrB_index:]  

    return sorted_array  

arrA = [ -5, 1, 3, 8, 9]  
arrB = [ 0, 3, 9, 16, 33]  
print(merge_two_sorted_array_slice(arrA, arrB))  

# result  
# [-5, 0, 1, 3, 3, 8, 9, 9, 16, 33]

4. 实现排序

既然实现了2个有序数组的排序，那么下面最重要的就是分割。
然后结合 分割+合并 的思想进行实现。 

def merge_sort(arr):  

    n = len(arr)  
    if n <= 1:  
        return arr  
    mid = n // 2  

    arrA = merge_sort(arr[:mid])  
    arrB = merge_sort(arr[mid:])  
    # 直到这里都是分割  

    # 接下来才是比较合并  
    arrA_index, arrB_index = 0, 0  
    sorted_array = []  
    while arrA_index < len(arrA) and arrB_index < len(arrB):  
        if arrA[arrA_index] < arrB[arrB_index]:  
            sorted_array.append(arrA[arrA_index])  
            arrA_index += 1  
        else:  
            sorted_array.append(arrB[arrB_index])  
            arrB_index += 1  
    sorted_array += arrA[arrA_index:]  
    sorted_array += arrB[arrB_index:]  

    return sorted_array  

arr = [ 12, 34, 54, 2, 3, -1, 0, -16]   
print(merge_sort(arr))  

# result  
# [-16, -1, 0, 2, 3, 12, 34, 54]

5. 最后要说的

归并写到最后还是一个递归的用法。递归不懂，即使明白了归并也是写不出来的。

所以好好学习递归才是最重要的！

#Python #算法

共有评论(0)

登陆即可评论哦