快速排序算是我接触的第一个排序速度比较快的算法，之前一直也没有写快排的博客，闲来无事，就算温习一下了。
快排的原理
快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为较小和较大的2个子序列，然后递归地排序两个子序列。(来自wiki百科)
quick_sort.gif
我们首先设置一个哨兵，为了方便，就设置第一个为哨兵（这里哨兵的设置对快排的性能也有影响），然后设置两个指针，分别指向数组的首地址和尾地址，这两个数分别和哨兵进行比较，比哨兵大的放它右边，比哨兵小的放它左边，最终不仅能确定这个哨兵在该数组的位置，并且将数组分割成三部分，一个是排好序的，另外分别是比哨兵大的和比哨兵小的三部分。然后再用递归，对未排序好的两部分做同样的操作。
quick_sort1.jpg
实现代码
public int change(int[] arr,int l,int r){
/**
* 设置哨兵
*/
int guard = arr[l];
/**
* 设置指针指向数组的首尾元素
*/
int i = l, j = r;
while(i<j){
/**
* 先从j开始比较
*/
while (i < j && arr[j] >= guard){
j--;
}
/**
* 当j指向的元素比哨兵大的时候，将j指向的元素
* 赋值给i指向的位置,i++,但是要保证i<j
*/
if (i<j){
arr[i++] = arr[j];
}
/**
* 现在开始从i指向的位置与哨兵比较
*/
while(i < j && arr[i] < guard){
i++;
}
if(i < j){
arr[j--] = arr[i];
}
}
/**
* 将哨兵的值赋给最后一个空缺的位置
*/
arr[i] = guard;
return i;
}
public void quick_sort(int[] arr, int l,int r){
if (l<r){
int boundry;
boundry = change(arr,l,r);
quick_sort(arr,l,boundry-1);
quick_sort(arr,boundry+1,r);
}
}
这里需要解释的是change()函数里为什么要这么多,因为有一些特殊情况需要应对。
举个例子，比如[1 2 3 4 5 6],这是已经排好序的数组了，当执行比较的while循环时，如果不限制,会下标越界。
时间复杂度
在change函数里，对数据进行一次排序，需要,而又需要递归，所以得出下面的递推公式：
这里证明太过复杂，使用递归树可能比较好理解，想要了解复杂度的话，知乎上有大佬证明。
