...

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

归并排序

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. 最后要说的

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

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

共有评论(0)

登陆即可评论哦