代码小工蚁的#《算法图解》#学习笔记-C4快速排序
C4 快速排序quicksort
一、递归式问题的解决方法
递归式问题的解决方法：分而治之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(n2)
平均情况(也是最佳情况)为：O(n * logn)
进一步理解大O表示法
合并排序（归并排序merge sort）是分治法（D&C）的典型应用。
合并排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。[1]
最坏时间复杂度：O(n * logn)
最好时间复杂度：O(logn)
空间复杂度：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 * logn)时，快速排序要比合并排序快。
实验：快速排序与合并排序的用时对比数据
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
