- 快速排序和归并排序的原理就不多讲，但网上的实现方法都比较繁琐，这里用更简短优美的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]))
