快速排序，正如它的名字所体现，是在实践中已知的最快的排序算法，平均运行时间为O(NlogN)，最坏的运行时间为O(N^2)。算法的基本思想很简单，然而想要写出一个高效的快速排序算法并不是那么简单。基准的选择，米素的分割等都至关重要，如果你不清楚如何优化快速排序算法，本文你不该错过。

算法思想

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

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

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

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

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

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

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

如何选择基准

实际上无论怎么选择基准，都不会影响排序结果，但是不同的选择却可能影响整体排序时间，因为基准选择不同，会导致分割的两个 *** 大小不同，如果分割之后，两个 *** 大小是几乎相等的，那么我们整体分割的次数显然也会减少，这样整体耗费的时间也相应降低。我们来看一下有哪些可选择策略。

选择之一个或者最后一个

如果待排序数是随机的，那么选择之一个或者最后一个作基准是没有什么问题的，这也是我们最常见到的选择方案。但如果待排序数据已经排好序的，就会产生一个很糟糕的分割。几乎所有的数据都被分割到一个 *** 中，而另一个 *** 没有数据。这样的情况下，时间花费了，却没有做太多实事。而它的时间复杂度就是最差的情况O(N^2)。因此这种策略是绝对不推荐的。