快速排序（QuickSort）的Java实现

简介

快速排序，看这名字就知道这是一种很快的排序方法，实际上也是如此。快速排序属于分治法的一种，就是说通过把数据分成几部分来同时处理的一种算法。

快速排序的步骤

我们以数组int[]a={7,5,3,2,9,10,8,4,6,1};这个数组为例来说明一下快速排序到底是怎么进行的。

第1步：找基准值

所谓的基准值，顾名思义就是以它为基准进行比大小。通常来说，我们选取数组的第一个数为基准值。在数组a里基准值就是7。

第2步：比大小

先从数组的最右边开始往左边找比基准值小的第一个数，然后从数组的最左边开始往右找比基准值大的第一个数。那么为什么要这么找呢？因为现在我们要把数组从小到大排序，所以要找出比基准值小的数放到基准值的左边，找出比基准值的数放在基准值的右边。

那么在数组a里，从左往右找，第一个比7大的数就是9，我们把它的坐标记为i；从右往左找，第一个比7小的数就是1，我们把它的坐标记为j。

第3步：交换

找到之后，如果这个时候i<j，那么就交换这两个数，因为i=4,j=9，符合条件，将9和1进行交换。现在数组变成了int[]a={7,5,3,2, 1 ,10,8,4,6, 9 };

如果i>=j，那么不做处理。

为什么还要判断i和j的大小呢？就像第二步说的，我们要找出比基准值小的数放到基准值的左边，找出比基准值的数放在基准值的右边。所以如果i<j的话，交换就达到目的了，如果i>=j，比基准值小的数就在基准值的左边，比基准值大的数已经在基准值的右边了，这时候就没必要交换了。

第4步：继续查找

在i<j的前提下，继续向右查找比基准值大的数，往左找比基准值小的数，然后交换。

在我们的例子中，10和6、8和4都符合交换的条件，所以数组就变成了 int[]a={7,5,3,2,1,6,4,8,10,9};这时候i=6，j=7。

第5步：交换基准值到合适的位置

当查找继续进行，这时候i=j=6，已经不满足继续查找和交换的条件了，那么我们应该怎么办呢？答案就是把a[6]和基准值交换，因为i=j的时候说明已经到了一个分界线的位置，分界线左边的数比基准值小，分界线右边的数比基准值大，而这个分界线就是我们的基准值，所以把它和a[i]交换，这时候数组就变成：

int[]a={4,5,3,2,1,6,7,8,10,9};

第6步：重复

对基准值左右两边的两个子数组重复前面五个步骤直至排序完成。

复杂度

时间复杂度

从上面的步骤可以看出来快速排序的快慢取决于区域划分的次数，理想情况下是每次都等分，所以划分次数为logn（即 即log2n )。

最坏的情况就是每次划分之后，一边只有一个元素，另一边有n-1个元素，这样就得划n-1次，这时候时间复杂度为O(n2)。

平均的时间复杂度为O(nlogn)。

空间复杂度

不需要额外的空间，空间复杂度为O(1)。

稳定性

快速排序算法 的稳定性取决于和基准值交换的那个数的大小，时间性能取决于快速排序递归的深度，所以 快速排序是一种不稳定的排序方法 。

最优情况下时间复杂度

快速排序最优的情况就是每一次取到的元素都刚好平分整个数组。

此时的时间复杂度公式则为：T[n] = 2T[n/2] + f(n)；T[n/2]为平分后的子数组的时间复杂度，f[n] 为平分这个数组时所花的时间；

下面来推算下，在最优的情况下快速排序时间复杂度的计算(用迭代法)：

综上所述： 快速排序最优的情况下时间复杂度为：O( nlogn )

最差情况下时间复杂度

最差的情况就是每一次取到的元素就是数组中最小/最大的，这种情况其实就是 冒泡排序 了(每一次都排好一个元素的顺序)。

这种情况时间复杂度就好计算了，就是冒泡排序的时间复杂度：T[n] = n * (n-1) = n^2 + n;

综上所述：快速排序最差的情况下时间复杂度为：O( n^2 )