?????????哇偶，上節(jié)被愚弄了呢旷太，可怕看幼。那這一節(jié)將功補過好了給大家介紹一種比較實用的方法--快速排序批旺。上一節(jié)所學的冒泡排序有效的解決了桶排序浪費的問題，不過算法的執(zhí)行效率非常的低诵姜。他的時間復雜度達到了O（N^2）汽煮。舉個栗子，聽好嘍棚唆。
????????假設(shè)我們的計算機每秒鐘可以運行10億多次暇赤，那么對1億個數(shù)進行排序，桶排序需要0.1秒宵凌，而冒泡排序則需要1000萬秒鞋囊，也就是115天。天了嚕瞎惫，電腦都得燒壞了溜腐。那可不可以既不用浪費空間又可以快一點的算法呢？Duang瓜喇，Duang逗扒，Duang，快速排序來了欠橘。哇矩肩，聽名字就覺得很快。
?????????接下來肃续，我們又有些小任務(wù)了黍檩，沒錯和前兩節(jié)一樣，我們要做的就是排序始锚。假設(shè)我們對“6刽酱，1,2,7,9,3,4，5,10,8”這10個數(shù)進行排序瞧捌。==之前不是排5個棵里，現(xiàn)在怎么讓我排10個了润文，加工資嗎。少廢話殿怜，快干活典蝌。
? ? ? ? 首先我們在這個序列中隨便找一個數(shù)作為基準數(shù)。有多隨便呢头谜？要你管骏掀。哇，那基準數(shù)是什么鬼柱告？別害怕截驮，基準數(shù)就是一個參照的數(shù)而已，就和我們初中物理學的參考系一個意思际度。what葵袭？好吧。
? ? ? ? 我們就把第一個數(shù)字6作為基準數(shù)吧乖菱，有意見嗎坡锡？沒意見沒意見，惹不起惹不起块请。接下來我們要怎么做呢娜氏？我們需要把上述10個序列中比6大的放在6的右邊，比6小的放在6的左邊墩新。那我們要怎樣才能實現(xiàn)這個目的呢贸弥？其實方法很簡單。
? ? ? ? 我們分別從序列“6海渊，1,2,7,9,3,4绵疲，5,10,8”的兩端開始查找。先從右往左找一個小于6的數(shù)臣疑，再從左到右找一個大于6的數(shù)盔憨，然后交換他們。此時我們可以用兩個變量i,j分別指向最左邊和最右邊讯沈。i指向6郁岩，j指向8。
????????由于我們的基準數(shù)設(shè)置的是6缺狠，是最左邊的數(shù)问慎，所以j先從右往左移動。j一個一個向左移動也就是j--挤茄，直到遇到一個小于6的數(shù)停下來如叼。接下來i再一個一個向右移動，直到遇到一個大于6的數(shù)停下來穷劈。最后j停在了5笼恰，i停在了7踊沸。然后i和j交換位置。此時交換后的序列就變成了6,1,2,5,9,3,4,,7,10社证，8逼龟。
? ? ? ? 接下來j繼續(xù)向左移動j--，發(fā)現(xiàn)了4猴仑，i繼續(xù)向右移動發(fā)現(xiàn)了9审轮，再進行交換肥哎，此時交換后的序列就變成了6,1,2,5,4,3,9,7,10,8
? ? ? ? 然后j繼續(xù)向右移動發(fā)現(xiàn)了3辽俗，i繼續(xù)向左移動也遇到了3，哇篡诽，我們兩個失散多年的兄妹終于相認了崖飘。此時我們將基準數(shù)6和3進行交換。交換后的序列變成了3,1,2,5,4,6,9,7,10,8
? ? ? ? 我們總結(jié)一下剛剛的過程：其實j的任務(wù)就是找到小于基準數(shù)的數(shù)杈女，i的任務(wù)就是要找到大于基準數(shù)的數(shù)朱浴，直到i和j相遇為止。
?????????現(xiàn)在我們可以以6為分界點拆成兩個序列达椰，左邊的序列是"3 1 2 5 4"翰蠢，右邊的序列是"9,7,10,8"，我們用上述的方法分別處理左右兩邊的序列
? ? ? ? 最終我們會得到這樣的序列：1,2,3,4,5,6,7,8,9,10啰劲。
? ? ??? 快速排序的每一輪處理其實就是將這一輪的基準數(shù)歸位梁沧，直到所有的數(shù)都歸位為止，排序就結(jié)束了蝇裤。
? ? ? ? 廢話不多說了來人廷支，上代碼。威栓辜。恋拍。。武藕甩。施敢。。
????????最后到了說復雜度的時候了狭莱，快速排序的最差時間復雜度和冒泡排序的一樣僵娃，都是O（N^2），它的平均時間復雜度是O（NlogN）
?
