Question

快速排序

Answer 1

递推公式
既然设计到递归。下意识就要想使用递归的两个必要条件

递推公式
递归退出条件
其实递推公式简单。如图所示。

如果要排序数组中下标从 startIndex 到 endIndex 之间的一组数据，我们选择 startIndex 到 endIndex 之间的任意一个数据作为 pivot（分区点）。通常情况下，选择数组最后一个元素。

我们遍历 startIndex 到 endIndex 之间的数据，将小于 pivot 的放到左边，将大于 pivot 的放到右边，将 pivot 放到中间。
经过这一步骤之后，数组 startIndex 到 endIndex 之间的数据就被分成了三个部分，前面都是小于 pivot 的，中间是 pivot，后面都是是大于 pivot 的。

根据分治、递归的处理思想，我们可以用递归排序下标从 startIndex 到 pivot-1 之间的数据和下标从 pivot+1 到 endIndex 之间的数据，直到区间缩小为 1，就说明所有的数据都有序了。

有了核心思想，现给出 递推公式 ，和 退出条件

T(n) = 2*T(n/2) + n
推导逻辑和归并排序一致。时间复杂度为: O(nlogn)

快速排序是原地排序，以交换的方式实现的移动，没有开额外的内存空间，空间复杂度为： O(1)

归并排序的处理过程是 由下到上 的，先处理子问题，然后再合并。
快排正好相反，它的处理过程是 由上到下 的，先分区，然后再处理子问题。
归并排序不是原地排序，需要开启额外的内存空间。
快速排序是原地排序。

https://github.com/handsomebai/arithmetic