快速排序

介绍

快速排序 (Quick Sort)，也被称作快排， 其平均时间复杂度为 $O(n\log_{n})$， 最坏时间复杂度为 $O(n^{2})$， 最优空间复杂度为 $O(\log_{}{n})$， 最差空间复杂度为 $O(n)$。

思路

假设我们这里有一个数组 [9,2,3,8,4,5]， 我们可以在数组中随意挑选一个数字，作为 基准值 (Pivot)，比如选第一个或最后一个元素。

9	2	3	8	4	5

这里我选择最后一个元素。

之后，我们进行 分区 (Partition) 操作。 核心思想就是将比基准值小的数字放在基准值的左边，反之放在右边。

表格中越淡的颜色最先被移动。

2	3	4	5	9	8

之后，我们对左右两边的区域都进行同样操作，直到只剩下一个元素为止。

代码实现

快速排序主要分为 Hoare Partition 与 Lamuto Partition，本质上都没有什么区别。