快速排序算是我接觸的第一個(gè)排序速度比較快的算法于个，之前一直也沒有寫快排的博客，閑來無事降允，就算溫習(xí)一下了禁荸。
快排的原理
快速排序使用分治法（Divide and conquer）策略來把一個(gè)序列（list）分為較小和較大的2個(gè)子序列，然后遞歸地排序兩個(gè)子序列葫录。(來自wiki百科)
quick_sort.gif
我們首先設(shè)置一個(gè)哨兵着裹，為了方便，就設(shè)置第一個(gè)為哨兵（這里哨兵的設(shè)置對(duì)快排的性能也有影響）米同，然后設(shè)置兩個(gè)指針骇扇，分別指向數(shù)組的首地址和尾地址摔竿，這兩個(gè)數(shù)分別和哨兵進(jìn)行比較，比哨兵大的放它右邊少孝，比哨兵小的放它左邊继低，最終不僅能確定這個(gè)哨兵在該數(shù)組的位置，并且將數(shù)組分割成三部分稍走，一個(gè)是排好序的袁翁，另外分別是比哨兵大的和比哨兵小的三部分。然后再用遞歸婿脸，對(duì)未排序好的兩部分做同樣的操作粱胜。
quick_sort1.jpg
實(shí)現(xiàn)代碼
public int change(int[] arr,int l,int r){
/**
* 設(shè)置哨兵
*/
int guard = arr[l];
/**
* 設(shè)置指針指向數(shù)組的首尾元素
*/
int i = l, j = r;
while(i<j){
/**
* 先從j開始比較
*/
while (i < j && arr[j] >= guard){
j--;
}
/**
* 當(dāng)j指向的元素比哨兵大的時(shí)候，將j指向的元素
* 賦值給i指向的位置,i++,但是要保證i<j
*/
if (i<j){
arr[i++] = arr[j];
}
/**
* 現(xiàn)在開始從i指向的位置與哨兵比較
*/
while(i < j && arr[i] < guard){
i++;
}
if(i < j){
arr[j--] = arr[i];
}
}
/**
* 將哨兵的值賦給最后一個(gè)空缺的位置
*/
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()函數(shù)里為什么要這么多,因?yàn)橛幸恍┨厥馇闆r需要應(yīng)對(duì)狐树。
舉個(gè)例子焙压，比如[1 2 3 4 5 6],這是已經(jīng)排好序的數(shù)組了，當(dāng)執(zhí)行比較的while循環(huán)時(shí)抑钟，如果不限制,會(huì)下標(biāo)越界涯曲。
時(shí)間復(fù)雜度
在change函數(shù)里，對(duì)數(shù)據(jù)進(jìn)行一次排序味赃，需要,而又需要遞歸掀抹，所以得出下面的遞推公式：
這里證明太過復(fù)雜，使用遞歸樹可能比較好理解心俗，想要了解復(fù)雜度的話傲武，知乎上有大佬證明。
