快速排序
实现步骤：
-
右指针往左找，找到一个<=枢轴值的值时停下
-
左指针往右找，找打一个>枢轴值的值时停下
-
判断左右指针是否重合：
- 未重合：将左右指针指向的值互换，继续重复步骤1
- 重合：将枢轴值与重合点的值互换，结束。
执行完一次上述步骤后，枢轴值被排序到正确位置，此时数组呈现：
- 枢轴值左边的值全部<=枢轴值
- 枢轴值右边的值全部>枢轴值
接下来，把对左右两部分的值进行同样的操作，递归结束后，即可即可实现将数组排序。
递归的结束条件：
- 子数组为空
- 或枢轴值等于右指针（子数组只有一个值）
实现代码：
def partition(ls, left, right):"""划分实现枢轴值左边<=它,右边>它"""# 注意python中函数参数传递的是引用，在函数内修改列表，外面的列表也会变# 所以只需要将枢轴值的位置返回即可# 枢轴值pivot = leftwhile left != right:# 右指针左移，寻找一个小于等于pivot的值while (left < right) and (ls[right] > ls[pivot]):right -= 1# 左指针右移，寻找一个大于pivot的值while (left < right) and (ls[left] <= ls[pivot]):left += 1if left < right:# 左右指针没有相遇# 将左右指针的值交换，继续移动ls[left], ls[right] = ls[right], ls[left]# 当左右指针相遇时，将枢轴值与交汇点交换if pivot != left:# 将枢轴值与相遇点交换，实现枢轴值左边<=ta,右边>tals[pivot], ls[left] = ls[left], ls[pivot]# 返回枢轴值位置return leftdef quick_sort(ls, left, right):""" 快速排序 """if left > right:# 当子数组为空或只有一个值时，结束递归return# 移动左右指针，使枢轴值左边<=它，右边>它pivot = partition(ls, left, right)# 继续对左边数组和右边数组进行快速排序quick_sort(ls, left, pivot - 1)quick_sort(ls, pivot + 1, right)
需要注意的是，python中对函数参数的传递时引用传递，所以函数内部对列表的操作会直接影响外面的列表，所以在进行递归以及划分时，不需要将改变后的数组返回。
另一种实现方法（非原地排序）：
def quick_sort2(ls):""" 快速排序 """if len(ls) < 2:# 递归结束条件，空数组或只有一个值的数组时有序的return lspivot = ls[0]# 获取小于等于枢轴值的数组成的数组less_ls = [i for i in ls[1:] if i <= pivot]greater_ls = [i for i in ls[1:] if i> pivot]return less_ls + [pivot] + greater_ls
值得一提的是，第二种方法比第一种方法运行时间更短，虽然它创造了新的列表，空间占用较大，但更具AI的解释，第二种方法使用的是列表推导式，列表推导式底层是C实现的，速度很快，而第一中方法中涉及较多的if判读以及元素交换，所以速度慢。