? ? 快速排序算法是對(duì)冒泡算法的改進(jìn)。所以我們首先來(lái)簡(jiǎn)單的談?wù)劽芭菟惴ā?/p>
1.冒泡算法
冒泡排序（Bubble Sort），是一種計(jì)算機(jī)科學(xué)領(lǐng)域的較簡(jiǎn)單的排序算法。
? ? 它重復(fù)地走訪過(guò)要排序的數(shù)列，一次比較兩個(gè)元素，如果他們的順序錯(cuò)誤就把他們交換過(guò)來(lái)。走訪數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換，也就是說(shuō)該數(shù)列已經(jīng)排序完成。
? ? 這個(gè)算法的名字由來(lái)是因?yàn)樵叫〉脑貢?huì)經(jīng)由交換慢慢“浮”到數(shù)列的頂端，故名“冒泡排序”。
步奏：
（1）有一數(shù)組，n個(gè)元素，從n=0位和n=1位相鄰元素開(kāi)始進(jìn)行比較，如果第一個(gè)比第二個(gè)大，就交換他們兩個(gè)，反之不做操作；
（2）對(duì)相鄰的元素做（1）中相同操作。直到最后一對(duì)相鄰元素比較結(jié)束，留在數(shù)組的最后一個(gè)元素為最大數(shù)；
（3）對(duì)除最后一位元素外重復(fù)以上的步驟，直到?jīng)]有任何一對(duì)數(shù)字需要比較，即排序結(jié)束。
時(shí)間復(fù)雜度：
（1）如果數(shù)組的原始狀態(tài)就是有小到大排序的，使用冒泡算法只需要進(jìn)行一趟排序即可，時(shí)間復(fù)雜度為O（n）；
（2）如果數(shù)組的原始狀態(tài)就是有大到小排序的，使用冒泡算法需要進(jìn)行n-1趟排序，每趟需要進(jìn)行n-i次比較(1≤i≤n-1)，時(shí)間復(fù)雜度為O（n^2）；
算法的穩(wěn)定性：
? ? 如果在排序過(guò)程中，遇到相鄰的兩個(gè)相同元素則不需要進(jìn)行位置操作；如果兩個(gè)相等的元素沒(méi)有相鄰，那么即使通過(guò)前面的兩兩交換把兩個(gè)相鄰起來(lái)，這時(shí)候也不會(huì)交換，所以相同元素的前后順序并沒(méi)有改變，所以冒泡排序是一種穩(wěn)定排序算法。
2.快速排序算法
? ? 快速排序由C. A. R. Hoare在1962年提出。它的基本思想是：通過(guò)一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過(guò)程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列。
步奏：
（1）設(shè)置兩個(gè)變量i、j，排序開(kāi)始的時(shí)候：i=0，j=N-1；
（2）以第一個(gè)數(shù)組元素作為關(guān)鍵數(shù)據(jù)，賦值給key，即key=A[0]；
（3）從j開(kāi)始向前搜索，即由后開(kāi)始向前搜索(j--)，找到第一個(gè)小于key的值A(chǔ)[j]，將A[j]和A[i]互換；
（4）從i開(kāi)始向后搜索，即由前開(kāi)始向后搜索(i++)，找到第一個(gè)大于key的A[i]，將A[i]和A[j]互換；
（5）重復(fù)第3、4步，直到i=j；(3,4步中，沒(méi)找到符合條件的值，即3中A[j]不小于key,4中A[i]不大于key的時(shí)候改變j、i的值，使得j=j-1，i=i+1，直至找到為止。找到符合條件的值，進(jìn)行交換的時(shí)候i，j指針位置不變。另外，i==j這一過(guò)程一定正好是i+或j-完成的時(shí)候，此時(shí)令循環(huán)結(jié)束)。這個(gè)過(guò)程是一趟快速排序。
（6）第一遍快速排序不會(huì)直接得到最終結(jié)果，只會(huì)把比k大和比k小的數(shù)分到k的兩邊。為了得到最后結(jié)果，需要再次對(duì)兩邊的數(shù)組分別執(zhí)行此步驟，然后再分解數(shù)組，直到數(shù)組不能再分解為止（只有一個(gè)數(shù)據(jù)），才能得到正確結(jié)果。
舉例：
有一組元素：14，22，15，7，39
（1）設(shè)置兩個(gè)變量i、j，排序開(kāi)始的時(shí)候：i=0，j=4；
（2）以第一個(gè)數(shù)組元素作為關(guān)鍵數(shù)據(jù)，賦值給key，即key=A[0]=14；
（3）從j開(kāi)始向前搜索，即由后開(kāi)始向前搜索(j--)，找到第一個(gè)小于key=14的值A(chǔ)[3]，將A[3]和A[0]互換得：7，22，15，14，39；
（4）從i開(kāi)始向后搜索，即由前開(kāi)始向后搜索(i++)，找到第一個(gè)大于key=14的A[1]，將A[1]和A[3]互換得：7，14，15，22，39；
（5）重復(fù)第3、4步，直到i=j碰頭；本例經(jīng)過(guò)一次快速排序即碰頭：7，14，15，22，39。
時(shí)間復(fù)雜度：
（1）最壞的情況下，發(fā)生在每次劃分過(guò)程產(chǎn)生的兩個(gè)區(qū)間分別包含n-1個(gè)元素和1個(gè)元素的時(shí)候，時(shí)間復(fù)雜度是O(n^2);
（2）最好的情況下，如果每次劃分過(guò)程產(chǎn)生的區(qū)間大小都為n/2，時(shí)間復(fù)雜度是O（nlogn）；
（3）平均時(shí)間復(fù)雜度是O（nlogn）；
算法的穩(wěn)定性：
? ? 在快速排序算法中，多個(gè)相同的值的相對(duì)位置也許會(huì)在算法結(jié)束時(shí)產(chǎn)生變動(dòng)，所以快速排序不是一種穩(wěn)定的排序算法。
