排序算法（2）- 归并、快速

归并排序的原理

采用分治思想，每次将数组从中间分成两部分，分别对两部分进行排序，直到不能继续分解为止

merge_sort.png

def merge_sort(array):
    """
    归并排序：适合大规模数据
    :param array:
    """
    def _merge_sort(start, end):
        if start >= end:
            return
        mid = (start+end) // 2
        _merge_sort(start, mid)
        _merge_sort(mid+1, end)
        _merge(start, mid, end)

    def _merge(start, mid, end):
        i = start
        j = mid + 1
        temp = []
        while i <= mid and j <= end:
            if array[i] < array[j]:
                temp.append(array[i])
                i += 1
            else:
                temp.append(array[j])
                j += 1
        remaining_start = i
        remaining_end = mid
        if j <= end:
            remaining_start = j
            remaining_end = end

        while remaining_start <= remaining_end:
            temp.append(array[remaining_start])
            remaining_start += 1
        for idx in range(end-start+1):
            array[start+idx] = temp[idx]

    count = len(array)
    _merge_sort(0, count-1)

归并排序的性能分析

1. 是否是稳定的排序算法，要看merge函数，如果从start->mid和mid->end两个区间的存在值相同的元素，那么在合并的时候可以将start->mid先放入数组，这样就保证了值相同的元素前后顺序不变，所以是一个稳定的排序算法
2. 关于时间复杂度的分析，这里涉及到了递归调用，
   如果我们定义求解问题a的事件是T(a)，求解问题b、c的时间分别是T(b)和T(c)，那么可以得到这样的递推公式：
   T(a) = T(b) + T(c) + K
   K是将两个子问题合并所消耗的时间。
   假设对n个元素进行归并排序需要的时间是T(n)，那分解成两个子数组排序的的时间就是T(n/2)。merge合并两个子数组的时间复杂度是O(n)。
   那么归并排序的时间复杂度的计算公式就是：

T(1) = C;   n=1
T(n) = 2*T(n/2) + n;    n>1
进一步分解得到：
T(n) = 2*T(n/2) + n
     = 2*(2*T(n/4) + n/2) + n = 4*T(n/4) + 2*m
     = 4*(2*T(n/8) + n/4) + 2*n = 8*T(n/8) + 3*n
     = 8*(2*T(n/16) + n/8) + 3*n = 16*T(n/16) + 4*n
     ...
     = 2^k * T(n/2^k) + k*n

当T(n/2^k) = T(1)时，也就是n/2^k=1，得到k=log2(n)，将k带入上面的公式，得到T(n) = Cn + nlog2(n)。
所以 T(n) = O(nlogn)

3. 空间复杂度。每次合并两个子数组的时候，都会创建一个临时数组，合并结束即销毁。所以临时空间最大不会超过n个数据的大小，为O(n)。

快速排序的原理

和归并排序相似，都是用到了分治思想，但是实现却是完全不同。
快速排序是要在start和end之间找一个任意的元素pivot（分区点），遍历数组，将小于pivot的元素放在左边，大于pivot的元素放在右边，结束后，整个数组就被分为了三个部分，小于pivot的start->pivot_idx-1，pivot，大于pivot的pivot_idx+1->end。

quick_sort.png

def quick_sort(array):
    """
    快速排序
    :param array:
    """
    def _quick_sort(start, end):
        if start >= end:
            return

        pivot_idx = _partition(start, end)
        _quick_sort(start, pivot_idx-1)
        _quick_sort(pivot_idx+1, end)

    def _partition(start, end):
        pivot = array[end]
        i = start
        for j in range(start, end):
            if array[j] < pivot:
                array[i], array[j] = array[j], array[i]
                i += 1
        array[i], array[end] = array[end], array[i]
        return i

    count = len(array)
    if count <= 1:
        return
    _quick_sort(0, count-1)

归并排序的分治思想是先分，后治，先拆分到最后，在合并子数组。而快速排序更像是先治后分，先将比pivot小和大的元素分别排到左右两边，在拆分子数组继续找pivot继续排，直到最后不能排为止。

merge_quick_sort.png

快速排序的性能分析

1. 快速排序是一种原地（交换部分没有用到额外的空间）、不稳定的排序算法
2. 如果每次分区操作，都能把数组分成大小相等的两个小区间，那快排的时间复杂度递推公式跟归并是相同的，所以快排的时间复杂度也是O(nlogn)。如果排序的数组已经是有序，那么每次分区得到的两个区间都是不均等的，需要进行大约n次分区操作，每次分区平均扫描大于n/2的元素，这种情况下，时间复杂度就退化成了O(n^2)。

总结

快排和归并都是通过分治思想、递归调用方式来实现，但是归并排序虽然是一种在任何情况下时间复杂度都比较稳定的排序算法，但是也存在致命缺点，即不是原地排序算法，空间复杂度比较高（O(n)），因此也没有快排应用的广泛。
快排的时间复杂度最快情况是O(n^{2)，但是平均时间复杂度是O(nlogn)，而且退化到O(n}2)的概率非常小，也可以合理地选择pivot来避免这种情况。

来自 https://leejnull.github.io/2020/01/14/2020-01-14-01/