数据结构的快速排序也称为拆分交换排序，它将按一次排序排序的数据拆分为两个独立的部分。 其中一个部分的所有数据都小于其他部分的所有数据，用这种方法分别对两个部分的数据进行快速排序。 整个排序过程是递归的，整个数据是有序序列。
步骤是从数列中选择一个称为“标准”的元素。 对数列进行排序，所有元素小于基准值的放在基准之前，所有元素大于基准元素的放在基准元素之后。 同样的数量配置在哪里都可以。 此划分结束后，基准位于数列的中间位置。 这称为分区操作。 对小于基准值的元素的子数列和大于基准值的元素的子数列进行递归排序。 递归的底部形状是数列的大小为0或1，即可以永远排序。 虽然还在继续递归，但这个算法总是会结束。 因为每次迭代，至少有一个元素位于其最后位置。
快速排序算法分析综述：首先从数列中提取一个数作为基准数。 分区过程将大于此数量的所有数字放在右侧，将所有小于此数量的数字放在左侧。 对左右区间重复步骤2，直到每个区间只有一个数。
其原理是将排序后数据按一次排序分割成独立的两个部分，其中一个部分的所有数据小于其他部分的所有数据，然后用该方法分别高速地对两个部分的数据进行排序，从而递归地进行整个排序过程
简单来说，相对于数组中的任意一个元素，通常相对于第一个元素，通过逐一比较，找到该基准元素的适当位置。 也就是说，基准元素左侧的元素比它小，右侧的元素比它大。 此时，将数组左右分开，继续上述操作，直到不能再分开为止。 此时，排序也完成。
快速排序算法实现方法1 :
defquick_sort(Li，first，last ) :“”快速排序“”#参数first，last:指定序列排序的开始位置和结束后缀#，其中first为last 此时，元素移动到一个if first=last 3360 returnlielse : mid _ value=Li [ first ] low=first high=lastwhilelowhigh 3360 # high左侧：high-=1li[low]=Li[high]#此时Li[low]的值小于或等于mid _ value # low向右移动whilelowhighandmid _ valueli [ low ] low对high li[low]=mid_value #对first，low - 1 ) low右侧的列表进行快速排序quick_sort(Li，low 1，last ) if _ name _=
方法2 :
defquick_sort(Li ) :“”快速排序“”#必须为返回，否则right和left都为Nonetype (数组长度为2时除基准len=1外) list(iflen ) Li )=1: returnlimid _ value=Li [0] # left=list ) right=list ) (forinLi ) )找不到用于存储大于或小于基线的值的两个列表。3360 if mid _ value=I : right.appenent 如果在快速排序每个right left后，将li[0]与合并为一个排序后的list #合并，则所有这些都是必需的，因此，将基准元素与list类型returnquick_sort(left ) [ mimit ]
前：', li) new_li = quick_sort(li) print('排序后：', new_li)运行结果：
对比两种方法的运算速度：
示例代码：
from timeit import Timerdef quick_sort(li, first, last): """快速排序""" # 参数first,last:指定序列排序的位置起始和终止下标 # 只有当first小于last时才退出排序，此时元素只有一个 if first >= last: return li else: mid_value = li[first] low = first high = last while low < high: # high 左移 while low < high and mid_value <= li[high]: high -= 1 li[low] = li[high] # 此时li[low]的值已经小于或等于mid_value # low 右移 while low < high and mid_value > li[low]: low += 1 li[high] = li[low] # 从循环退出时，low等于high li[low] = mid_value # 对low左边的列表进行快速排序 quick_sort(li, first, low - 1) # 对low右边的列表进行快速排序 quick_sort(li, low + 1, last)def quick_sort2(li): """快速排序""" # 必须return 否则right和left 都是Nonetype(当数组长度为2时候除去基准len=1,for时候会找不到执行list) if len(li) <= 1: return li mid_value = li[0] # 定义两个列表用于存放大于或小于基准的值 left = list() right = list() for i in li[1:]: if mid_value <= i: right.append(i) else: left.append(i) # 对right left分别快速排序后与 li[0]拼接为一个排序后的list # 合并时，需要都是list类型，所以需将基准元素变成list类型 return quick_sort2(left) + [mid_value] + quick_sort2(right)if __name__ == '__main__': li = [54, 26, 93, 17, 77, 31, 44, 50, 20] li2 = [54, 26, 93, 17, 77, 31, 44, 50, 20] print('排序前：', li) time1 = Timer('quick_sort([54, 26, 93, 17, 77, 31, 44, 50, 20], 0, 8)', 'from __main__ import quick_sort') quick_sort(li, 0, len(li) - 1) print('方法1排序后：', li) print('running time is :', time1.timeit(10)) time2 = Timer('quick_sort2([54, 26, 93, 17, 77, 31, 44, 50, 20])', 'from __main__ import quick_sort2') new_li = quick_sort2(li2) print('方法2排序后：', new_li) print('running time is :', time2.timeit(10))运行结果：