前言
無論是日後面試還是筆試的，排序在數據結構與算法中有著舉足輕重的地位，所以還是決定把數據結構這個專題好好寫寫，多研究研究！今天和大家一起學習交換類排序——冒泡和快排詳解！
在排序中，冒泡和快排是考察最多的了，當然在實行上面冒泡要相比快排簡單很多。理解起來也算得上是最簡單的排序算法，而快排的話很多面試筆試都是要求手撕的，所以重要性不言而喻！當然，對於排序算法我當初首次接觸學習的時候只是萌萌懂懂的，只是大概瞭解，死記了模板，能將快排手寫出來，刷題用。後來我發現我太傻吊了，，java中明明有Arrays.sort()這個api可以直接調用我為啥要憨呼呼的手寫？多個條件排序重寫下comparator接口就OK為啥還要憨呼呼的手寫？。。。自此，就踏上了不手寫快排的不歸路。。。
後來，漸漸的，這個排序思想用的少，被我成功的遺忘。。現如今，被我重新拾起，深入理解下，防止哪一天又那個大佬讓我手撕下不會就尷尬了哈哈，把學習過程分享給大家！
冒泡排序
介紹
冒泡排序，又稱起泡排序。他是一種基於交換的排序典型，也是快排思想的基礎。對於冒泡排序名字的由來，百度百科這麼說：
這個算法的名字由來是因為越小的元素會經由交換慢慢“浮”到數列的頂端（升序或降序排列），就如同碳酸飲料中二氧化碳的氣泡最終會上浮到頂端一樣，故名“冒泡排序”。
當然，冒泡排序是一種穩定排序算法，時間複雜度位O(n^2^).基本思想是：從前往後把大元素往後調(或者從後向前把小元素往前調)。
分析
具體思想為(把大元素往後調)：
- 從第一個元素開始往後跑，每到一個位置判斷是否比後面的元素大，如果比後面元素大，那麼就交換兩者大小，然後繼續向後，否則就直接向後前進，這樣的話進行一輪之後就可以保證最大的那個數一直被交換交換到最末的位置可以確定。
- 那麼第二次同樣從開始起向後判斷著前進，如果當前位置比後面一個位置更大的那麼就和他後面的那個數交換。但是有點注意的是，這次並不需要判斷到最後，只需要判斷到倒數第二個位置就行(因為第一次我們已經確定最大的在倒數第一，這次的目的是確定倒數第二)
- 同理，後面的操作也是如此，直到第一個元素使得整個元素有序。
拿個例子來說，比如2，8，9，3，7，6，12，4這個序列的冒泡排序來說。會有多趟(7)排序，每一趟要執行多(8-k)次。
對於它的第一趟排序來說是這樣的：
而多次排序每次的結果是這樣的：
它的動態執行順序為：
代碼
在具體實現的時候，要分清是從小到大還是從大到小，還有次數也要注意，謹防越界！
至於冒泡排序的關鍵代碼為：
<code>
private
static
void
maopaosort
(
int
[] a) {for
(int
i=a.length-1
;i>=0
;i--) {for
(int
j=0
;jif(a[j]>a[j+1
]) {int
team=a[j]; a[j]=a[j+1
]; a[j+1
]=team; } } } } /<code>
快速排序
介紹
快速排序是對冒泡排序的一種改進，採用遞歸分治的方法進行求解。而快排相比冒泡是一種不穩定排序,時間複雜度最壞是O(n^2^),平均時間複雜度為O(nlogn),最好情況的時間複雜度為O(nlogn)。
分析
對於快排來說，基本思想是這樣的
快排需要將序列變成兩個部分，就是序列左邊全部小於一個數，序列右面全部大於一個數，然後利用遞歸的思想再將左序列當成一個完整的序列再進行排序，同樣把序列的右側也當成一個完整的序列進行排序。
其中這個數在這個序列中是可以隨機取的，可以取最左邊，可以取最右邊，當然也可以取隨機數。但是通常我們取最左邊的那個數。當然，為了實現這個目標，實現方式可能不一樣，但是我這裡採取的是大眾常規的方式和方法。！
這裡的一個難題就是如何處理將比第一個數K小的全部放左面，把比K大的全部放右面！如果沒有什麼技巧，直接硬性往裡面塞，你肯定要一個額外存儲空間先把整個先存了。然後遍歷比較然後放入目標區域。當然這樣太浪費空間內存了。我們為了節省計算機資源，採取這樣的方法：
- 先用一個空間標記這個最左側的數K。然後先從右往左high--先找到一個比這個K小的數a[high]，把這個a[high]放到a[low]位置(因為這個a[low]的初始K已經被額外空間記錄過，不用擔心)。
- 這樣右側不符合要求小於K的已經調到最左側了，我們再從左側向右low++一直到a[low]>K.也就是找到第一個比K大的數，它在左側不符合要求所以我們把它移動到右側，而我們剛剛所說的a[high]已經被賦值移到左側，所以我們把這個a[low]大於K的數值移動到右端a[high]處，這樣又保證high右側全部大於K，low左側全部小於K。
- 就又開始重複第一步啦一直到low>high為止(即所有左側都小於K，右側都大於K)。
對於一個序列的2,8,3,7,6,9,4,12來說，它的執行過程圖解大致是這樣的：
1 . 首先2是最小的，採用遞歸分治時候左側相當於為空，只需要把右側再進行排序。
2 .對於右側序列來說，先用K儲存a[low]=8我們先從右側找到第一個小與8的數字4。
3 .我們將它放到low位置替換，然後從low位置向右找到第一個大於k=8的再同樣放到右側。我們找到9，把9賦值給high位置。
4 .重複上面步驟直到high
5 .就這樣重複下去，直到整個序列有序即可！
代碼
在書寫代碼的時候，要注意一些順序，防止數組越界情況，可以寫好debug一遍其實就很好理解了！當寫代碼遇到錯誤時候，不要急著就去找正確答案，能有時間自己發現錯誤，可以藉助斷點查看程序執行流程，這樣對自己的收益是最大的！
至於快排的代碼，是這樣的：
<code>private
static
void
quicksort
(
int
[] a,int
left,int
right) {int
low=left;int
high=right;if
(low>high)return
;int
k=a[low];while
(low/<code>
測試與總結
對於完整的代碼，為
<code>package
八大排序;import
java.util.Arrays;public
class
交換類排序 {public
static
void
main
(String[] args)
{int
a[]= {2
,8
,9
,3
,7
,6
,12
,4
}; maopaosort(a); System.out.println(Arrays.toString(a));int
b[]= {2
,8
,9
,3
,7
,6
,12
,4
}; quicksort(b,0
, b.length-1
); System.out.println(Arrays.toString(b)); }private
static
void
maopaosort
(
int
[] a) {for
(int
i=a.length-1
;i>=0
;i--) {for
(int
j=0
;jif(a[j]>a[j+1
]) {int
team=a[j]; a[j]=a[j+1
]; a[j+1
]=team; } } } }private
static
void
quicksort
(
int
[] a,int
left,int
right) {int
low=left;int
high=right;if
(low>high)return
;int
k=a[low];while
(lowwhile(low=k) { high--; } a[low]=a[high];while
(low1); quicksort(a, low+1
, right); } } /<code>
運行結果：
好了這個交換類排序就總結到這裡了。總之，冒泡是很基礎和容易，但是要注意這種簡單排序所屬的範疇(交換類)要和插入類等做好區分；而快排板子很好記，深入理解需要點時間消化吧。一次不行再來第二次，不行再來第三次，。。。
當然，如果感覺不錯或者對你有所幫助，歡迎點贊收藏轉發哈！如果感覺有問題或者紕漏還請指正哈！當然，筆者長期致力於<>這個專欄的更新和維護，歡迎大家關注一波哈！
最後，歡迎關注筆者微信公眾號(bigsai)，頭條號(一直碼農一直爽)！
