快速排序（Quicksort）是对冒泡排序算法的一种改进。

快速排序由C. A. R. Hoare在1960年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

快速排序算法通过多次比较和交换来实现排序，其排序流程如下：

快速排序（QuickSort ）是一个分治算法（Divide and Conquer）。它选择一个元素作为枢轴元素（pivot），并围绕选定的主元素对给定数组进行分区（partition）。快速排序有很多不同的版本，它们以不同的方式选择枢轴。

1. 总是选择第一个元素作为 pivot。
2. 总是选择最后一个元素作为 pivot。
3. 随机选一个元素作为 pivot。
4. 选择中值作为 pivot。

QuickSort 中的关键步骤是 partition()。在数组中选择的一个元素为支点（pivot）, 把所有小于 pivot 的元素放到 pivot 左面, 大于 pivot 的放右边。这样数组 x[n] 会被划分成3个部分：

所有这应该是在线性时间内完成。
接下来，就是递归调用:

The logic is simple, we start from the leftmost element and keep track of index of smaller (or equal to) elements as i. While traversing, if we find a smaller element, we swap current element with arr[i]. Otherwise we ignore current element.

Pseudo code for partition()

Illustration of partition()