? ? 快速排序算法是對(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位相鄰元素開始進(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酷鸦，排序開始的時(shí)候：i=0饰躲，j=N-1；
（2）以第一個(gè)數(shù)組元素作為關(guān)鍵數(shù)據(jù)臼隔，賦值給key属铁，即key=A[0]；
（3）從j開始向前搜索躬翁，即由后開始向前搜索(j--)焦蘑，找到第一個(gè)小于key的值A(chǔ)[j]，將A[j]和A[i]互換盒发；
（4）從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司蔬，排序開始的時(shí)候：i=0，j=4姨蝴；
（2）以第一個(gè)數(shù)組元素作為關(guān)鍵數(shù)據(jù)俊啼，賦值給key，即key=A[0]=14左医；
（3）從j開始向前搜索授帕，即由后開始向前搜索(j--)，找到第一個(gè)小于key=14的值A(chǔ)[3]浮梢，將A[3]和A[0]互換得：7跛十，22，15秕硝，14芥映，39；
（4）從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)定的排序算法。
