排序之快排

相比于冒泡排序、插入排序、选择排序这种时间复杂度为O(n2)的排序算法，快速排序的时间复杂度更快，它运用了分治的思想，进行排序，在这期间，也运用了递归的思想。

下面给出一组数字，来作为样例进行示范。

不过既然是递归，那么就要遵循我们写递归程序的思想以及写递归时要避免的坑。

6 1 2 7 9 3 4 5 10 8

我们选择一个基准数用来排序。然后设置两个哨兵，分别指向待排串的最左边和最右边，然后从右边开始，让右边的哨兵值和基准数比较，向左移动，直到哨兵值比基准数小，就停下；然后让左边的哨兵向右移动，直到哨兵值比基准数大，就停下。这时就交换两个数。

初始状态 找到待交换值 交换

待第一次交换完毕后，即i和j相遇后，就需要第二次交换，这时候，我们可以发现规律，即下面的交换和第一次交换的动作时一样的，所以我就可以使用递归来解决。

i和j两个哨兵相遇 交换 第一次交换完成

下面就可以递归实现了，分别对 3 1 2 5 4 和 9 7 10 8 继续上面相同的操作。

下面给出代码

/**

* 进行递归排序

*

* @param array 待排序

* @param left  左哨兵

* @param right 右哨兵

*/

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

if (left > right) {

return;

}

int base = array[left];//  选择基准数

    int i = left, j = right;

while (i < j) {

if (array[j] >= base && i < j) {

j--;

}

if (array[i] <= base && i < j) {

i--;

}

if (i < j) {

int temp = array[j];

array[j] = array[i];

array[i] = temp;

}

}

array[left] = array[i];

array[i] = base;

quickSort(array, left, i -1);

quickSort(array, i +1, right);

}