什么是快速排序？
快速排序由C. A. R. Hoare在1962年提出菌瘫。它的基本思想是：通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分肩祥，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序躯护，整個(gè)排序過程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列丽涩。
算法原理
單單看以上解釋還是有些模糊棺滞，可以通過實(shí)例來理解它，下面通過一組數(shù)據(jù)來進(jìn)行排序過程的解析：
原數(shù)組：{3矢渊，7继准，2，9矮男，1移必，4，6毡鉴，8崔泵，10，5}
期望結(jié)果：{1猪瞬，2憎瘸，3，4陈瘦，5幌甘，6，7，8锅风，9酥诽，10}
?
?
?
?
花了點(diǎn)時(shí)間擼了下面這張快速排序示意圖：
?
步驟解析：
1）一開始選定數(shù)組的最后一個(gè)元素5作為基準(zhǔn)值，也就是最終排序結(jié)果應(yīng)該是以5為界限劃分為左右兩邊皱埠。
2）從左邊開始盆均，尋找比5大的值，然后與5進(jìn)行調(diào)換(因?yàn)槿绻?小的值本來就應(yīng)該排在5前面漱逸，比5大的值調(diào)換之后就去到了5的后面)泪姨，一路過來找到了7，將7與5調(diào)換饰抒，結(jié)束此次遍歷肮砾。
3）從右邊開始，由于7已經(jīng)是上一輪排好序的便不再動(dòng)它袋坑，從10開始仗处，一路向左遍歷，尋找比5小的值枣宫，然后與5進(jìn)行調(diào)換(因?yàn)槿绻?大的值本來就應(yīng)該排在5后面婆誓，比5小的值調(diào)換之后就去到了5的后前面)，一路過來找到了4也颤，將4與5調(diào)換洋幻，結(jié)束此次遍歷。
4）從左邊開始翅娶，由于3和4都是前兩輪已經(jīng)排好序的便不再動(dòng)它文留，從2開始，一路向右遍歷竭沫，尋找比5大的值燥翅，然后與5進(jìn)行調(diào)換（道理同步驟2），一路過來找到了9蜕提，將9與5調(diào)換森书，結(jié)束此次遍歷。
5）從右邊開始谎势，由于排在9后面的那幾個(gè)數(shù)字都是上幾輪排好序的便不再動(dòng)它凛膏，從1開始，一路向右遍歷它浅，尋找比5小的值译柏，然后與5進(jìn)行調(diào)換(道理同步驟3)镣煮，一下子就找到了1姐霍，將1與5調(diào)換，結(jié)束此次遍歷。
6）這個(gè)時(shí)候镊折，發(fā)現(xiàn)5的左右兩邊都是排好序了的胯府，所以結(jié)束此輪排序，5的左右兩邊抽出來各自進(jìn)行下一輪的排序恨胚，規(guī)則同上骂因，直到無法再拆分下去，即完成了整體的快速排序赃泡。
?
算法實(shí)現(xiàn)
既然思路理清了,代碼就容易上手了：
/**
* 快速排序
* @author Android小Y
*/
public class QuickSort {
/**
* 將數(shù)組的某一段元素進(jìn)行劃分寒波，小的在左邊，大的在右邊
* @param a
* @param start
* @param end
* @return
*/
public static int divide(int[] a, int start, int end){
//每次都以最右邊的元素作為基準(zhǔn)值
int base = a[end];
//start一旦等于end升熊，就說明左右兩個(gè)指針合并到了同一位置俄烁，可以結(jié)束此輪循環(huán)。
while(start < end){
while(start < end && a[start] <= base)
//從左邊開始遍歷级野，如果比基準(zhǔn)值小页屠，就繼續(xù)向右走
start++;
//上面的while循環(huán)結(jié)束時(shí)，就說明當(dāng)前的a[start]的值比基準(zhǔn)值大蓖柔，應(yīng)與基準(zhǔn)值進(jìn)行交換
if(start < end){
//交換
int temp = a[start];
a[start] = a[end];
a[end] = temp;
//交換后辰企，此時(shí)的那個(gè)被調(diào)換的值也同時(shí)調(diào)到了正確的位置(基準(zhǔn)值右邊)，因此右邊也要同時(shí)向前移動(dòng)一位
end--;
}
while(start < end && a[end] >= base)
//從右邊開始遍歷况鸣，如果比基準(zhǔn)值大牢贸，就繼續(xù)向左走
end--;
//上面的while循環(huán)結(jié)束時(shí)，就說明當(dāng)前的a[end]的值比基準(zhǔn)值小镐捧，應(yīng)與基準(zhǔn)值進(jìn)行交換
if(start < end){
//交換
int temp = a[start];
a[start] = a[end];
a[end] = temp;
//交換后十减，此時(shí)的那個(gè)被調(diào)換的值也同時(shí)調(diào)到了正確的位置(基準(zhǔn)值左邊)，因此左邊也要同時(shí)向后移動(dòng)一位
start++;
}
}
//這里返回start或者end皆可愤估，此時(shí)的start和end都為基準(zhǔn)值所在的位置
return end;
}
/**
* 排序
* @param a
* @param start
* @param end
*/
public static void sort(int[] a, int start, int end){
if(start >= end){
//如果只有一個(gè)元素帮辟，就不用再排下去了
return;
}
else{
//如果不止一個(gè)元素，繼續(xù)劃分兩邊遞歸排序下去
int partition = divide(a, start, end);
sort(a, start, partition-1);
sort(a, partition+1, end);
}
}
}
?
采用幾組數(shù)據(jù)測(cè)試了下結(jié)果
public static void main(String[] args) {
int[] a = new int[]{2,7,4,5,10,1,9,3,8,6};
int[] b = new int[]{1,2,3,4,5,6,7,8,9,10};
int[] c = new int[]{10,9,8,7,6,5,4,3,2,1};
int[] d = new int[]{1,10,2,9,3,2,4,7,5,6};
sort(a, 0, a.length-1);
System.out.println("排序后的結(jié)果：");
for(int x : a){
System.out.print(x+" ");
}
}
?
?
算法優(yōu)缺點(diǎn)
快速排序最“快”的地方在于左右兩邊能夠快速同時(shí)遞歸排序下去玩焰，所以最優(yōu)的情況是基準(zhǔn)值剛好取在無序區(qū)的中間由驹，這樣能夠最大效率地讓兩邊排序，同時(shí)最大地減少遞歸劃分的次數(shù)昔园。此時(shí)的時(shí)間復(fù)雜度僅為O(NlogN)蔓榄。快速排序也有存在不足的情況默刚，當(dāng)每次劃分基準(zhǔn)值時(shí)甥郑，得到的基準(zhǔn)值總是當(dāng)前無序區(qū)域里最大或最小的那個(gè)元素，這種情況下基準(zhǔn)值的一邊為空荤西，另一邊則依然存在著很多元素(僅僅比排序前少了一個(gè))澜搅，此時(shí)時(shí)間復(fù)雜度為O(N*N)伍俘。快速排序的速度快慢關(guān)鍵在于基準(zhǔn)值的選取勉躺，它決定了劃分次數(shù)以及比較次數(shù)癌瘾，決定了快排的效率，因此饵溅，還有一些針對(duì)于基準(zhǔn)值選取的優(yōu)化方法妨退，例如“三數(shù)據(jù)取中法”等，能夠有效優(yōu)化快速排序存在的不足之處蜕企。
?
結(jié)語
如果將日常寫代碼比作擰螺絲咬荷，那數(shù)據(jù)結(jié)構(gòu)和算法就好比一個(gè)扳手，單純只是為了編碼而編碼轻掩，就好比徒手?jǐn)Q螺絲萍丐，有時(shí)候會(huì)特別吃力，而且擰完的效果也可能不佳放典，但如果借助扳手逝变，就可以更高效精準(zhǔn)地完成我們的工作。以上是本人對(duì)快速排序的一點(diǎn)淺見奋构，如果覺得寫得還不錯(cuò)的動(dòng)動(dòng)小手點(diǎn)個(gè)喜歡~~
?
