思想
快速排序是排序算法中比较有名的一个，他的主要思想是，用一趟排序找到一个数，将数组分组两个部分，左边的部分都比这个数大，右边的部分都比这个数小。
然后再分别对左右两边的数组进行此种操作，直到被分割的数组长度是1，整个数组就达到了有序。
例子
一般，我们选择数组的第一个数作为基准进行比较，左边的比这个数小，右边的比这个数大。
例子，如下图所示，开始从右边扫描，直到一个数比基准数小，就交换这两个数的位置，接下来就从左边开始扫描，找到一个数比基准数大，就交换这两个数， 直到左右两个指针重合。
代码
package test;
import java.util.Arrays;
public class QuickSort {
public static void main(String [] args){
QuickSort sort = new QuickSort();
int [] array = {1, 3, 4, 5, 2, 6, 9, 7, 8, 0};
sort.quickSort(array, 0, array.length - 1);
System.out.println(Arrays.toString(array));
}
public void quickSort(int [] array,int left,int right){
if (left < right) {
// 分割数组，找到下次分割的基准数
int base = division(array, left, right);
// 对左边的数组进行快排
quickSort(array, left, base - 1);
// 对右边的数组进行快排
quickSort(array, base + 1, right);
}
}
public int division(int [] array,int left,int right){
int base ;
while(left < right){
// 从右边开始进行比较
while(array[left] < array[right]){
right --;// 右边的数比基准数大，右指针前移
}
// 右边的数比基准数的小，交换两个数
base = array[left];
array[left] = array[right];
array[right] = base;
// 从左边开始比较
while(array[left] < array[right]){
left ++;// 左边的数比基准数小，左指针右移
}
// 左边的数比基准数大，交换两个数
base = array[left];
array[left] = base;
array[left] = array[right];
array[right] = base;
}
return left;
}
}
复杂度分析
最好时间复杂度：O(nlogn);
最坏时间复杂度：O(n2);
平均时间复杂度：O(nlogn);
空间复杂度：O(1)
