快速排序

一、引入

快速排序是所有排序算法中最高效的一种。它采用了分治的思想：先保证列表的前半部分都小于后半部分，然后分别对前半部分和后半部分排序。

二、递归

在开始之前我们在复习一下递归

1. 在此之前先了解一下分治法（Divide-and-ConquerMethod、D&C）

   分治法的基本思想是：将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。

2. 什么是递归？

   简单的说递归就是自己调用自己，递归可以分为两部分，即基线条件与递归条件，递归条件是指函数自己调用自己，而基线条件指的是函数不在调用自己，如果递归没有基线条件，那么函数将会形成无限循环，无法返回。

3. 写一个小例子

   1. 现在有一个数组：[1, 2, 3, 4, 5]，那么请问我们不用循环如何计算出它的和？

      现在我们用递归来做这个题，首先我们要找出基线条件，即让函数不在调用自己的条件，慢慢想一下，如果当数组中只有一个元素或者是没有元素时，计算总和将会变得很容易吧（都不用算就知道了），OK，现在基线条件找到了，那么我们再找一下递归条件，很简单就能想到应该是列表中除第一个数字外的其他数字。

   2. review一下我的代码

      def sum(aar):
      	if len(aar) < 2:
      		return aar[0]
      	else:
      		return aar.pop() + sum(aar)
      
      print(sum([1, 2, 3, 4, 5]))

三、快速排序

1. 基准值

   先保证列表的前半部分都小于后半部分，然后分别对前半部分和后半部分排序。用来区分前半部分与后半部分的数值叫基准值。

2. 基线条件

   当数组为空或者只有一个元素时，这种情况只需要原样返回数组即可

3. 分区

   如果不满足基线条件，我们对数组进行分区，分为[小于基准值的数组]，[基准值]，[大于基准值的数组]

4. 递归

   分区之后的数据仍然是无序的，我们通过递归循环解决

5. 示例代码

def quicksort(array):
	if len(array) < 2:
		return array
	else:
		# 基准值
		pivot = array.pop()
		# 小于等于基线条件的数组
		less = [i for i in array if i <= pivot]
		# 大于基线条件的数组
		greater = [i for i in array if i > pivot]

		return quicksort(less) + [pivot] + quicksort(greater)

print(quicksort([8, 1, 2, 5, 3, 6, 9, 4, 7]))
```