算法与数据结构（python）：快速排序

提示：专栏解锁后，可以查看该专栏所有文章。





---

文章目录

• 快速排序
• 改进后的快速排序

---

快速排序

      快速排序名字可不是盖的，很多程序语言标准库实现的内置排序都有它的身影，我们就直奔主题吧。

和归并排序一样， 快排也是一种分而治之(divide and conquer)的策略。

归并排序把数组递归成只有单个元素的数组，之后再不断两两合并，最后得到一个有序数组。

这里的递归基本条件就是只包含一个元素的数组，当数组只包含-一个元素的时候，我们可以认为它本来就是有序的(当然空数组也不用排序) .快排的工作过程其实比较简单，三步走:

`

1. 选择基准值pivot将数组分成两个子数组:小于基准值的元素和大于基准值的元素.这个过程称之为partition
2. 对这两个子数组进行快速排序。
   

   
   

3. 合并结果

      根据这个想法我们可以快速写出快排的代码，简直就是在翻译上边的描述:

import random #导入随机数
def quicksort(array