一、递归式问题的解决方法

递归式问题的解决方法：分而治之D&C（divide and conquer）
D&C思路（递归算法）：
(1)找出尽可能简单的基线条件；
(2)不断缩小问题的规模，直到其符合基线条件。

小提示：
编写涉及数组的递归函数时，基线条件通常是数组为空或只包含一个元素。

二、快速排序

对数组进行快速排序的D&C思路：
基线条件：数组为空或只包含一个元素。此时不用排序，直接返回数组即可。
缩小问题：
选择基准值；
将数组分成两个子数组（小于等于基准值的，大于基准值的）；
对两个子数组进行快速排序（递归操作，直至基线条件）。

快速排序代码：

#coding=utf-8

# 快速排序

def quick_sort(array):
    # 基线条件：数组为空或只有一个元素
    if len(array) < 2:
        return array
    else:
        # 设定基准值
        pivot = array[0]
        # 数组分成2个子数组
        less = [i for i in array[1:] if i <= pivot]
        greater = [i for i in array[1:] if i > pivot]
        # 递归操作
        return quick_sort(less) + [pivot] + quick_sort(greater)

demo = [2,5,1,9,12,8,77,56]
print(demo)
print(quick_sort(demo))

快速排序的时间复杂度：
最糟情况为：O(n²)
平均情况(也是最佳情况)为：O(n * logⁿ)

进一步理解大O表示法

合并排序（归并排序merge sort）是分治法（D&C）的典型应用。

合并排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。^[1]
最坏时间复杂度：O(n * logⁿ)
最好时间复杂度：O(logⁿ)
空间复杂度：O(N)

python代码实现合并排序:^[2]

#coding=utf-8

# 合并排序

import random

def merge_sort(array):
    if len(array) <= 1:
        # print('-'*30)
        return array
    mid = len(array) // 2
    left = merge_sort(array[:mid])
    right = merge_sort(array[mid:])
    # print('left=', left,'right=',right)
    return merge(left, right)

def merge(l_arr, r_arr):
    ret_arr = []
    i, j = 0, 0
    while i < len(l_arr) and j < len(r_arr):
        if l_arr[i] <= r_arr[j]:
            ret_arr.append(l_arr[i])
            i += 1
        else:
            ret_arr.append(r_arr[j])
            j += 1
    # print(l_arr[i:], r_arr[j:])
    ret_arr = ret_arr + l_arr[i:] + r_arr[j:]
    return ret_arr


if __name__=='__main__':
    demo_arr =[random.randint(1, 50) for i in range(1,7)]
    print(demo_arr)
    print(merge_sort(demo_arr))

在大O表示法O(n)中，n实际上指的是：C * n
其中C是算法所需要的固定时间量（常量）。
当两种算法的大O运行时间不同，常量通常不用考虑。
当两种算法的大O运行时间相同时，此时要考虑常量的问题。
快速排序的常量比合并排序的常量小，当快速排序与合并排序的大O时间都为O(n * logⁿ)时，快速排序要比合并排序快。

实验：快速排序与合并排序的用时对比数据
1000个随机整数500次排序用时对比：
快速排序：1.408736405354579
合并排序：2.8659359763556345

[1]百度百科：合并排序
https://baike.baidu.com/item/%E5%90%88%E5%B9%B6%E6%8E%92%E5%BA%8F/2669171?fr=aladdin

[2]Python排序搜索基本算法之归并排序
https://blog.csdn.net/littlethunder/article/details/9472301