归并排序与快速排序python简洁实现

• 快速排序和归并排序的原理就不多讲，但网上的实现方法都比较繁琐，这里用更简短优美的python来实现上述算法.

#! /usr/bin/env python
# -*- coding: utf-8 -*-

"""
@Author:_defined
@Time:  2020/3/10 16:53
@Description: 
"""


# 实现快速排序和归并排序

def quick_sort(arr: list):
    """
    快速排序，最快O(nlogn), 最坏O(n^2)
    :param arr:
    :type arr:
    :return:
    :rtype:
    """
    if len(arr) < 2:
        return arr
    else:
        privot = arr[0]  # 递归条件
        less = [i for i in arr[1:] if i <= privot]  # 所有小于基准值的元素组成的数组
        greater = [i for i in arr[1:] if i > privot]  # 所有大于基准值得元素组成的数组
        return quick_sort(less) + [privot] + quick_sort(greater)  # 分别递归调用并拼接结果


def merge_sort(arr: list):
    """
    归并排序, 稳定的排序算法，时间复杂度为O(nlogn)
    :param arr:
    :type arr:
    :return:
    :rtype:
    """
    if len(arr) < 2:
        return arr
    mid = len(arr) // 2
    res = []  # 存放结果
    left_arr = merge_sort(arr[:mid])
    right_arr = merge_sort(arr[mid:])
    lp, rp = 0, 0
    while lp < len(left_arr) and rp < len(right_arr):
        if left_arr[lp] <= right_arr[rp]:
            res.append(left_arr[lp])
            lp += 1
        else:
            res.append(right_arr[rp])
            rp += 1
    # 因为left_arr 和 right_arr 的长度不一定一样长，所以执行上一步while循环后，left_arr或者right_arr还有剩余的数据，
    # 而这部分数据已经有序且是比已经放到res中的元素大，因此需要把这边剩余的数据放到res中。
    res.extend(left_arr[lp:])
    res.extend(right_arr[rp:])
    print('left: ', left_arr, '\tright: ', right_arr, '\tres: ', res)
    return res


print('快速排序结果：', quick_sort([1, 3, 4, 2, 9, 7, 5, 7, 8]))
print('归并排序结果：', merge_sort([1, 3, 4, 2, 9, 7, 5, 7, 8]))