快速排序（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)。

稳定性

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

package com.rickie.sort;

import java.util.Arrays;

public class SortSample {

public static void main(String[] args) {

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

System.out.println(Arrays.toString(a));

quickSort(a, 0, a.length-1);

System.out.println(Arrays.toString(a));

}

public static void quickSort(int[] a, int left, int right){

if(left >= right)

return;

int pivot = a[left]; //定义基准值为数组第一个数

int i = left;

int j = right;

while(i<j){

while(pivot<=a[j] && i<j) //从右往左找比基准值小的数

j--;

while(pivot>=a[i] && i<j) //从左往右找比基准值大的数

i++;

// 交换值

if(i<j) {

int tmp = a[i];

a[i] = a[j];

a[j] = tmp;

}

}

a[left] = a[i]; // 把a[i] 放到a[left] 位置

a[i] = pivot; // 把基准值放到合适的位置

quickSort(a, left, i-1); // 对左边的子数组进行快速排序

quickSort(a, i+1, right); // 对右边的子数组进行快速排序

}

}

最优情况下时间复杂度

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

此时的时间复杂度公式则为：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 )