快速排序算法通過多次比較和交換來實(shí)現(xiàn)排序，其排序流程如下：
(1)首先設(shè)定一個(gè)分界值兢哭，通過該分界值將數(shù)組分成左右兩部分占调。?
(2)將大于或等于分界值的數(shù)據(jù)集中到數(shù)組右邊，小于分界值的數(shù)據(jù)集中到數(shù)組的左邊啥纸。此時(shí)，左邊部分中各元素都小于分界值婴氮，而右邊部分中各元素都大于或等于分界值斯棒。?
(3)然后盾致，左邊和右邊的數(shù)據(jù)可以獨(dú)立排序。對于左側(cè)的數(shù)組數(shù)據(jù)荣暮，又可以取一個(gè)分界值庭惜，將該部分?jǐn)?shù)據(jù)分成左右兩部分，同樣在左邊放置較小值渠驼，右邊放置較大值蜈块。右側(cè)的數(shù)組數(shù)據(jù)也可以做類似處理。
(4)重復(fù)上述過程迷扇，可以看出百揭，這是一個(gè)遞歸定義。通過遞歸將左側(cè)部分排好序后蜓席，再遞歸排好右側(cè)部分的順序器一。當(dāng)左、右兩個(gè)部分各數(shù)據(jù)排序完成后厨内，整個(gè)數(shù)組的排序也就完成了祈秕。
快速排序的重點(diǎn)在于用O(n)的時(shí)間復(fù)雜度把數(shù)組分為左右倆部分，一部分大雏胃，一部分小请毛，他們之間的分界是一開始取的分界值。
我們先定義一個(gè)數(shù)組int a[] = {93,27,30,2,8,12,2,8,30,89};我們?nèi)[0]作為分界值瞭亮，然后設(shè)置兩個(gè)變量方仿，一個(gè)從數(shù)組最左邊開始，另一個(gè)從數(shù)組最右邊開始统翩。我們先從右向左掃描仙蚜，如果發(fā)現(xiàn)元素比分界值小，就進(jìn)行交換厂汗，把小的元素扔到左邊過去委粉，這樣子第一次交換分界值a[0]就換到了右邊的位置，這時(shí)候我們就應(yīng)該從左往右掃描了娶桦，因?yàn)檫@時(shí)候分界值的右邊以及排序好了贾节，都是比分界值大的元素，然后再從右往左掃描衷畦，如此循環(huán)往復(fù)氮双，直到這兩個(gè)變量指針相遇為止。
這里有一個(gè)需要我們注意的點(diǎn)霎匈，如果我們把a(bǔ)[0]作為分界值，那么我們的第一次掃描應(yīng)該從右往左送爸，因?yàn)檫@時(shí)候分界值的左邊是默認(rèn)都比a[0]小的铛嘱。
從另一個(gè)角度理解暖释，我們其實(shí)也不一定要取數(shù)組的第一個(gè)元素或者最后一個(gè)元素作為分界值，我們可以隨便取中間的一個(gè)元素作為分界值墨吓，然后可以先從右邊掃描球匕，把小的元素都扔到數(shù)組左邊，然后再從數(shù)組左邊掃描帖烘，把大的元素放到分界值的右邊亮曹。但是這會(huì)造成一個(gè)問題，就是我們在第二次掃描的時(shí)候需要對分界值的位置進(jìn)行移動(dòng)秘症，其他數(shù)組元素的位置也跟著移動(dòng)照卦，這樣的時(shí)間復(fù)雜度就大了，這樣的代價(jià)是我們不能接受的乡摹。但是如果我們快速排序的不是數(shù)組役耕，而是鏈表里面的元素，就沒有這個(gè)問題了聪廉。
所以瞬痘，使用快速排序，如果是對于數(shù)組的話板熊，我們的分界符只能取數(shù)組的第一個(gè)元素或者最后一個(gè)元素框全。但是如果我們是對鏈表進(jìn)行快速排序的話，那么我們就無所謂取哪一個(gè)元素作為分界符了干签。
