Python归并排序算法

相比起初级排序算法,高级排序算法往往有更加复杂的逻辑,但也会有更高的时间或空间效率。其中有些高级排序算法是由初级排序算法优化而来的。在处理大量数据时,高级排序算法的一般更加常用。

本节教程介绍的第一种高级排序算法是归并排序。“归并”一词,意为“合并”。顾名思义,归并排序算法就是一个先把数列拆分为子数列,对子数列进行排序后,再把有序的子数列合并为完整的有序数列的算法。它实际上采用了分治的思想,之后我们会深度讲解分治思想。

归并排序的平均时间复杂度是 O(nlgn),最好情况下的时间复杂度是 O(nlgn),最坏情况下的时间复杂度也是 O(nlgn)。它的空间复杂度是 O(1)。另外,归并排序还是一个稳定的排序算法。

以升序排序为例,归并算法的流程如图 1 所示。
归并排序
图 1:归并排序

原始数组是一个有 8 个数的无序数组。一次操作后,把 8 个数的数组分成两个 4 个数组成的无序数组。接下来的每次操作都是把无序数组不停分成两半,直到每个最小的数组里都只有一个元素为止。当数组里只有一个元素时,这个数组必定是有序的。

然后,程序开始把小的有序数组每两个合并成为大的有序数组。先是从两个 1 个数的数组合并成 2 个数的数组,再到 4 个数然后 8 个数。这时,所有的有序数组全部合并完成,最后产生的最长的有序数组就排序完成了。

归并排序代码:
#归并排序
nums = [5,3,6,4,1,2,8,7]
def MergeSort(num):
    if(len(num)<=1):        #递归边界条件
        return num         #到达边界时返回当前的子数组
    mid = int(len(num)/2)      #求出数组的中位数
    llist,rlist = MergeSort(num[:mid]),MergeSort(num[mid:])#调用函数分别为左右数组排序
    result = []
    i,j = 0,0
    while i < len(llist) and j < len(rlist): #while循环用于合并两个有序数组
        if rlist[j]<llist[i]:
            result.append(rlist[j])
            j += 1
        else:
            result.append(llist[i])
            i += 1
    result += llist[i:]+rlist[j:]  #把数组未添加的部分加到结果数组末尾
    return result         #返回已排序的数组
print(MergeSort(nums))
运行程序,输出结果为:

[1,2,3,4,5,6,7,8]


在 MergeSort( ) 函数中,首先进行的是边界条件判断。当传入函数的数组长度只有 1 时,每一个数独立存在于一个数组中,因此数组已经被分到最小。这时候,递归分解数组的任务已经完成,只需要把分解后的数组返回到上一层递归就可以了。

如果未排序数组的长度仍然大于 1,那么使用变量 mid 来存储数组最中间的下标,把未排序数组分成左右两个子数组。然后,新建两个数组,用于存储排好序的左右子数组。这里使用了递归的思想。我们只把 MergeSort( ) 函数视为一个为列表排序的函数,尽管在 MergeSort( ) 函数内部,也可以调用函数本身对两个子数组进行排序。

随后,使用 while 循环合并两个已经有序的数组。由于不能确定两个数组中元素的相对大小,所以我们采用 i 和 j 两个变量分别标记在左子数组和右子数组中等待加入的元素的位置。当 while 循环结束时,可能一个子数组的末尾还剩余一些最大的元素没有被添加到 result 列表中,所以 result+=llist[i:]+rlist[j:] 语句是为了防止漏掉这些元素。数组合并完成后,函数输出有序数组。