经典快排
首先任意选取一个数据作为关键数据，然后将所有比它小的数都放到它左边，所有比它大的数都放到它右边，这个过程称为一趟快速排序。然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归的进行直到整个数组有序。可以发现其实每一趟快速排序都是在做一次荷兰国旗的划分。关于荷兰国旗问题可以查看这里。
算法实现
在这里我们每次都选取序列的最后一个值作为划分的关键数据。
算法实现不是很难，先对数组进行划分，然后对数组左侧进行递归，对数组右侧进行递归。代码如下：
public static void quickSort(int[] arr,int left,int right) {
if(left < right) {
int[] p = partition(arr,left,right); //划分
quickSort(arr,left,p[0]-1); //左递归
quickSort(arr,p[1],right); //右递归
}
}
/*
* 这里是荷兰国旗的划分，且以arr数组的最后一个数arr[right]作为划分的值。
* */
private static int[] partition(int[] arr,int left, int right) {
int less = left - 1;
int more = right + 1;
while(left < more) {
if(arr[left] < arr[right]) {
swap(arr,++less,left++);
}else if(arr[left] > arr[right]) {
swap(arr,--more,left);
}else {
left++;
}
}
return new int[] {less+1,more};
}
private static void swap(int[] arr,int i,int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
时间复杂度
排序的效率与数组的数据状况有关。
在极端的数据状况下，例如：1 2 3 4 5 6 7 8 9。我们每次一最后一个数据作为划分值，则每次只搞定最后一个数据，而每一次执行partition函数都要付出O(N)的时间代价，一共有N个数据，则时间复杂度为O(N^2)；
在最理想的数据状况下，如下所示：等于划分值的区域在中间，其两侧被划分为等规模的样本空间，其花费时间为T(N) = 2T(N/2) + O(N);其最终求得的时间复杂度为O(N.logN)。关于递归行为时间复杂度的分析
_____________________________________
| N/2 | =X | N/2 |
|_______________|____|________________|
稳定性
多个相同的值的相对位置也许会在划分过程中产生变动，所以快速排序不是一种稳定的排序算法。
