快速排序

面试经常遇到的一个排序算法，采用分治的思想，通过不断的选取基准元素，将数组划分为更小的数组，直到不可划分，最终达到排序的目的。大多数情况下，快速排序比归并和堆排序效率要高一些，最好的时间复杂度和平均时间复杂度都是O(NlogN)，最坏的时间复杂度是O(N^2)。

算法的主要思路

1. 从数组中随机选择一个基准元素。
2. 将小于基准的元素放在基准元素的左边，大于基准的元素放在基准元素的右边。
3. 然后再对基准元素左边和右边的子数组执行1～3步操作，直到子数组中只有一个元素。

下面是数组[4, 1, 3, 6, 2, 3, 5]使用快速排序算法进行排序的过程。

关于快速排序，除了需要能够写出来之外，我们经常需要了解快速排序的时间复杂度以及什么最坏的情况，什么是最好的情况。

最好的情况 是每次我们选取的pivot，正好能够把当前递归中的子数组分为相等的两份，这种情况下递归调用的层数最少，为log2(N)，时间复杂度是O(NlogN)。

最坏的情况 是每次我们选取的pivot，对递归中的子数组划分非常不均衡，导致递归调用层数最多，为N-1，这样时间复杂度为O(N^2)。

快速排序在排序过程中并未使用额外的辅助空间，但是由于是递归调用，会消耗栈空间，最好的情况空间复杂度是O(logN)，最坏的情况是O(N)，同样也是受pivot的影响。

上面是快速排序的Java实现，在这个实现版本中，pivot取的是子数组中的第一个，这种做法在待数组是有序的情况下就会导致最坏的情况，即时间复杂度为O(N^2)，为了减少最坏情况发生的几率，povit应该随机选取。