算法思想

快速排序利用了分治的策略。而分治的基本基本思想是：将原问题划分为若干与原问题类似子问题，解决这些子问题，将子问题的解组成原问题的解。

那么如何利用分治的思想对数据进行排序呢？假如有一个米素集合A：

• 选择A中的任意一个米素pivot，该米素作为基准

• 将小于基准的米素移到左边，大于基准的米素移到右边（分区操作）

• A被pivot分为两部分，继续对剩下的两部分做同样的处理

• 直到所有子集米素不再需要进行上述步骤

可以看到算法思想比较简单，然而上述步骤实际又该如何处理呢？

如何选择基准

实际上无论怎么选择基准，都不会影响排序结果，

但是不同的选择却可能影响整体排序时间

，因为基准选择不同，会导致分割的两个集合大小不同，如果分割之后，两个集合大小是几乎相等的，那么我们整体分割的次数显然也会减少，这样整体耗费的时间也相应降低

。我们来看一下有哪些可选择策略。

选择第一个或者最后一个

如果待排序数是随机的，那么选择第一个或者最后一个作基准是没有什么问题的，这也是我们最常见到的选择方案。但如果待排序数据已经排好序的，就

会产生一个很糟糕的分割

。几乎所有的数据都被分割到一个集合中，而另一个集合没有数据。这样的情况下，

时间花费了，却没有做太多实事

。而它的时间复杂度就是最差的情况O(N^2)。

因此这种策略是绝对不推荐的

。