第六课排序算法（二）¶

上一节课，我们学习了三种基本的排序算法：冒泡算法、选择算法和插入算法。这三种算法基本不需要额外的空间，但是它们的效率不高，平均计算复杂度都在\(O(n^2)\)，当遇到数量比较大的数据时，会耗费非常多的时间。

归并排序（Merge Sort）¶

归并排序是一种比前面三种排序要高效的算法。它基本的思想是应用“分治法”的思想，将排序问题分解成一个个小的排序问题。下面我们一步一步来理解如何实现归并排序。

算法思路与步骤¶

首先讨论一个问题。假设有两个已经排好序的整型数组arr1 和arr2，大家能够将它合并成一个有序的序列吗？回想课上练习题中的“合并两个有序链表”一题，其实思路是相似的，不同的时，链表我们不需要额外的空间，而此时需要一块额外的空间用来存储合并后的数组。很快有以下的思路：

使用两个指针i和j分别表明当前数组arr1和arr2的未合并的位置
先将他们放至到两个数组的第0个元素，即: i = 0, j = 0
将arr1的第i个元素与arr2的第j个元素进行比较，较小者选复制到新数组中，并且对应的指针往后移动1位;
重复步骤2直到其中某一个数组完全被合并；
将剩余未处理的数组直接复制到新数组末尾。

请看以下的图示：

merge

根据以上思路，可以很快得出下列的代码：

def merge(arr1: List[int], arr2: List[int]) -> List[int]:
    sorted = []

    i = 0
    j = 0
    while i < len(arr1) and j < len(arr2):
        if arr1[i] < arr2[j]:
            sorted.append(arr1[i])
            i += 1
        else:
            sorted.append(arr2[j])
            j += 1

    while i < len(arr1):
        sorted.append(arr1[i])
        i += 1

    while j < len(arr2):
        sorted.append(arr2[j])
        j += 1

    return sorted

有了将两个有序数组合并的基础，我们事实上可以把待排列的无序数组，首先从上往下进行细分，然后直至分成一个个序列，然后再将他们两两合并，再从下往上进行合并（两个数比较也可以看成两个长度为1的有序数组进行合并）。请看下面的动画：

merge_sort

现在我们可以写出以下的算法步骤：

首先将数组按中点分成两个子数组；
如果两个子数组长度分别为1，则直接返回；
对两个子数组分别重复步骤1；
得到将两个子数组得到排序后的数组按两个有序数组排列。

下面可以写出代码：

def merge_sort(array: List[int]):
    if len(array) < 2:
        return

    mid = len(array) // 2
    arr1 = array[0: mid]
    arr2 = array[mid: ]
    sorted1 = merge_sort(arr1)
    sorted2 = merge_sort(arr2)
    sorted = merge(arr1, arr2)
    for i in range(len(array)):
        array[i] = sorted[i]

算法性能分析¶

时间复杂度¶

归并排序的时间复杂度，由两部分构成，一个是将数组分成两个子序列的时间花销，以及将两个有序数组进行排列时的时间花销。对应到代码中，就是merge函数和merge_sort两个函数的时间复杂度。

简单可以得到，合并两个有序数组的时间复杂度为\(O(n)\)，那现在主要问题要求得merge函数的时间复杂度。因为他是一个递归调用，所以分析起来比较麻烦。设merge函数花费时间为\(T[n]\)，则可以得到：

\[T[n] = 2T[n/2] + O(n)\]

他的推导过程稍微复杂些，在这里不做要求，直接告诉大家平均时间复杂度为\(O(n\log n)\)

空间复杂度¶

空间复杂度主要体现在merge中，算法会将两个有序序列合并后存在一个临时数组中，那么这部分占用空间为 \(n\)。其实在递归调用时，会有额外一部分的数据占用，这部分空间大小是 \(\log n\)。所以最后归并算法的空间复杂度为\(O(n)\)

排序练习题¶

有一个数组，其由一对数构成。现需要将其按照以下顺序排列：第1位数从小到大进行升序排列，假如第1位数大小相等时，按第2位数从大到小进行降序排列。

比如输入[(1,2), (2, 1), (2, 2), (5, 3), (2, 3)]，则最后排序结果为[ (1, 2), (2, 3), (2, 2), (2, 1), (5, 3) ]

第六课 排序算法（二）¶