归并排序算法 #

1. 归并排序算法原理
2. 归并排序算法的实现

收获 #

学完本节内容，可以初步理解并掌握归并排序算法。

归并排序算法原理 #

归并排序的原理如下：

1. 假设有两个已经有序的列表，设定两个指针分别指向这两个列表的起始元素，申请内存空间新建一个空列表，比较两个指针指向的元素大小，将较小的元素添加到新列表中，然后将该指针向该列表的下一个元素偏移，继续比较两个指针指向的元素和添加较小的到新列表中。直到其中一个列表的数据全部被添加完时，把另一个列表中剩下的数据按顺序添加到新列表中。这就实现了将两个有序列表合并成一个新的有序列表的方法。
2. 对待排序列表进行拆分，递归地拆分直到子列表中只有一个元素。
3. 只有一个元素的子列表一定是有序的，使用1中的方法对有序的子列表进行合并。第一次合并后新列表是有两个元素的有序列表，递归地往回合并，直到所有数据都合并到一个新的有序列表中，列表排序完成。

归并排序算法的实现 #

python实现代码如下：

def merge_sort(array):
    if len(array) == 1:
        return array
    left_array = merge_sort(array[:len(array) // 2]) #递归，直到array中只有1个值时，开始层层返回
    right_array = merge_sort(array[len(array) // 2:]) #同上
    return merge(left_array, right_array)
    # 可以输出（left_array,right_array）看一下：以元组形式,依次递归返回(left,right)
    #return (left_array, right_array) #((([10], [17]), ([50], [7])), (([30], [15]), ([5], ([38], [21]))))

def merge(left_array, right_array):
    left_index, right_index, merge_array = 0, 0, list() #list()创建一个空的列表
    while left_index < len(left_array) and right_index < len(right_array):
        if left_array[left_index] <= right_array[right_index]:
            merge_array.append(left_array[left_index])
            left_index += 1
        else:
            merge_array.append(right_array[right_index])
            right_index += 1
    merge_array = merge_array + left_array[left_index:] + right_array[right_index:] #比较完成后，left或者right列表肯定会有剩余，因此相加
    return merge_array

if __name__ == '__main__':
    a=[10,17,50,7,30,15,5,38,21]#共9个
    print(merge_sort(a))

小结 #

理解并掌握归并排序算法的原理
掌握归并排序的代码实现

习题 #

1. 习题1：画出归并排序算法的流程图
2. 习题2：使用归并排序算法，对列表[10, 17, 50, 7, 30, 24, 27, 45, 15, 5, 36, 21]进行升序排列