归并排序算法是在分治算法基础上设计出来的一种排序算法,它可以对指定序列完成升序(由小到大)或降序(由大到小)排序,对应的时间复杂度为O(nlogn)。

归并排序算法的思路是:

1) 将整个待排序序列划分成多个不可再分的子序列,每个子序列中仅有 1 个元素;

2) 所有的子序列进行两两合并,合并过程中完成排序操作,最终合并得到的新序列就是有序序列。

代码示例

1、子序列排序

例如:[14, 27, 35, 3, 10, 33],先分成 [14, 27, 35] 和 [3, 10, 33] 两部分,从左往右依次取值比较大小,小的存储在临时变量中,再移动指针,直至一边先结束,将另一边剩下的元素直接追加到临时变量中。

def merge(arr, low, high, mid):
    i = low
    j = mid + 1
    temp = []
    while i <= mid and j <= high:
        if arr[i] < arr[j]:
            temp.append(arr[i])
            i += 1
        else:
            temp.append(arr[j])
            j += 1
    # 有一边先结束,剩下的元素元素直接追加
    while i <= mid:
        temp.append(arr[i])
        i += 1
    while j <= high:
        temp.append(arr[j])
        j += 1
    arr[low:high+1] = temp

# lst = [14, 27, 35, 3, 10, 33]
# merge(lst, 0, 5, 2)

2、递归调用

def merge_sort(arr, low, high):
    if low < high:
        mid = (low + high) // 2
        merge_sort(arr, low, mid)
        merge_sort(arr, mid + 1, high)
        merge(arr, low, high, mid)

lst = [27, 13, 35, 10, 3, 33]
merge_sort(lst, 0, 5)
print(lst)

本文为 陈华 原创,欢迎转载,但请注明出处:http://edu.ichenhua.cn/read/212