排序算法（Sorting algorithm）是计算机科学最古⽼、最基本的课题之⼀。要想成为合格的程序员，就必须理解和掌握各种排序算法。其中”快速排序”（Quicksort）使⽤得最⼴泛，速度也较快。它是图灵奖得主C. A. R. Hoare(托尼·霍尔)于1960时提出来的。
⼀、快速排序（Quicksort）
快速排序(quick sort)的采⽤了分治的策略。由C. A. R. Hoare在1962年提出。它的基本思想是：通过⼀趟排序将要排序的数据分割成独⽴的两部分，其中⼀部分的所有数据都⽐另外⼀部分的所有数据都要⼩，然后再按此⽅法对这两部分数据分别进⾏快速排序，整个排序过程可以进⾏，以此达到整个数据变成有序。 齿槽转矩1、原理
1. 在数列之中，选择⼀个元素作为”基准”（pivot），或者叫⽐较值。
2. 数列中所有元素都和这个基准值进⾏⽐较，如果⽐基准值⼩就移到基准值的左边，如果⽐基准值⼤就移到基准值的右边 防水之乡
云南猪人
3. 以基准值左右两边的⼦列作为新数列，不断重复第⼀步和第⼆步，直到所有⼦集只剩下⼀个元素为⽌。
举个例⼦，假设我现在有⼀个数列需要使⽤快排来排序：[11, 99, 33 , 69, 77, 88, 55, 11, 33, 36,39, 66, 44, 22]，我们来看看使⽤快排的详细步骤： 1. 选取中间的66作为基准值（基准值可以随便选）
2. 数列从第⼀个元素11开始和基准值66进⾏⽐较，⼩于基准值，那么将它放⼊左边的分区中，第⼆个元素99⽐基准值66⼤，把它放⼊右
边的分区中。
3. 然后依次对左右两个分区进⾏再分区，直到最后只有⼀个元素
4. 分解完成再⼀层⼀层返回，返回规则是：左边分区+基准值+右边分区
青藤碱
2、代码
代码⽤jupyternotebook实现
def quick_sort(b):
图灵奖
2 """快速排序"""
3 if len(b) < 2:
4 return arr
舞弊三角理论5 # 选取基准，随便选哪个都可以，选中间的便于理解
6 mid = arr[len(b) // 2]
7 # 定义基准值左右两个数列
8 left, right = [], []
9 # 从原始数组中移除基准值
10 b.remove(mid)
11 for item in b:
12 # ⼤于基准值放右边
13 if item >= mid:
14 right.append(item)
15 else:
16 # ⼩于基准值放左边
17 left.append(item)
18 # 使⽤迭代进⾏⽐较
19 return quick_sort(left) + [mid] + quick_sort(right)
例
b = [11, 99, 33, 69, 77, 88, 55, 11, 33, 36, 39, 66, 44, 22]
quick_sort(b)
#返回：[11, 11, 22, 33, 33, 36, 39, 44, 55, 66, 69, 77, 88, 99]
⾼逼格（⼀⾏代码表⽰）：
quick_sort = lambda array: array if len(array) <= 1 else quick_sort([
2 item for item in array[1:] if item <= array[0]
3 ]) + [array[0]] + quick_sort([item for item in array[1:] if item > array[0]])
4
5 quick_sort([2,5,9,3,7,1,5])
6 #返回[1, 2, 3, 5, 5, 7, 9]
3、特点
1. 稳定性：快排是⼀种不稳定排序，⽐如基准值的前后都存在与基准值相同的元素，那么相同值就会被放在⼀边，这样就打乱了之前的
相对顺序
2. ⽐较性：因为排序时元素之间需要⽐较，所以是⽐较排序
3. 时间复杂度：快排的时间复杂度为O(nlogn)
4. 空间复杂度：排序时需要另外申请空间，并且随着数列规模增⼤⽽增⼤，其复杂度为：O(nlogn)
5. 归并排序与快排：归并排序与快排两种排序思想都是分⽽治之，但是它们分解和合并的策略不⼀样：归并是从中间直接将数列分成两
个，⽽快排是⽐较后将⼩的放左边⼤的放右边，所以在合并的时候归并排序还是需要将两个数列重新再次排序，⽽快排则是直接合并不再需要排序，所以快排⽐归并排序更⾼效⼀些，可以从⽰意图中⽐较⼆者之间的区别。
6. 快速排序有⼀个缺点就是对于⼩规模的数据集性能不是很好。
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议