經典的排序算法有八種，分別為：
- 冒泡排序
- 選擇排序
- 插入排序
- 歸併排序
- 希爾排序
- 快速排序
- 堆排序
- 基數排序
其中冒泡排序、選擇排序、插入排序稱為三大基本排序。
雖然這三大基本排序算法時間複雜度都是O(n2)，但是其實細細討論之下，還是有各自的特點的。
冒泡排序
冒泡排序法的思路
基本思路：
假設我們需要進行升序排列
進行N輪的比較，每一輪將相鄰的兩個元素依次比較，根據大小進行交換，每輪比較結束後，將最大的元素依次‘冒’到數組的末尾，經過幾輪比較後，數組就會呈現有序的狀態。
圖解：
假設對5個元素進行冒牌排序，先準備5個隨機元素：
1）第一輪中，將第一個元素（10）與相鄰的元素（20）進行比較，因為20比10大所以無需進行交換。再將第二個元素（20）與相鄰的元素（5）比較，因為20比5大，所以需要往上‘冒’，因此需要與5進行交換
接著將第三個元素（20）與相鄰的元素進行比較，這樣經過與14和1的比較之後，因為20最大，所以被冒到了最後的位置
2）後面每輪都按照此方法進行比較，但是需要注意，此後的每一輪都需要比前一輪少比較一次，因為前面已經確定了最大元素的位置，為了提高性能，可以不用再和後面確定了位置的元素進行比較。
3）由此可以確定，當數組的長度為N時，需要比較的輪數為N-1輪。每輪中從第一個元素開始相鄰元素兩兩進行比較，第一輪需要比較N-1次，第2輪需要比較N-2次，依次類推，實現整體排序
冒泡排序法的代碼實現
- 首先通過一個外層的for循環確定比較的輪數，循環元素數量-1輪。
- 內部通過一個for循環實現每輪的兩兩元素比較的效果。每輪需要比較的次數都會比上一輪減少一次，通過j
- 元素兩兩比較通過array[j] > array[j+1]來實現。
冒泡排序法優化
以上的冒泡排序法還有優化的空間。因為如果一個數組已經是完全有序的情況下，冒泡排序法仍然會進行逐輪的比較，這無疑是浪費性能的行為。因此我們可以確定，當冒泡的比較中，有一輪如果沒有發生交換，則可以確定當前數組已經完全有序，後面的輪數完全不必在進行。故做以下的調整：
通過定義一個標識符isSort，如果有一輪沒有發生任何交換，則isSort就會為true，下次直接break，後面的輪數就不用再進行比較了。
選擇排序
選擇排序的思路
基本思路：
選擇排序和冒泡排序不同，選擇排序會通過一輪比較，選出最小的那個元素的下標，然後和第一個元素進行交換，這樣第一個元素的位置就可以確定了。
第二輪如法炮製，從第二個元素開始依次比較，選出最小的元素的下標，和第二個元素交換位置，這樣第二小的元素位置就確定了。
後面依次類推，直到整個數組呈現有序狀態。
選擇排序法的代碼實現
- 選擇排序比較的輪數和冒泡排序比較的輪數是一樣的
- K表示當前最小值的下標，當前是第幾輪，k就先代表第幾個元素的下標，然後依次和後面的元素進行比較，如果發現比k位置元素小的元素時，改變k的下標，這樣一輪過後k代表的位置就是本輪最小的元素，和i進行交換即可
- 如果一輪過後k==i，則說明i本來就是最小的元素，則無需交換提高性能。
插入排序
插入排序的思路
基本思路
假設一個數組已經基本有序，則這個時候插入排序就是一個不錯的選擇。插入排序是先保證左邊元素是基本有序的，然後將後面的元素依次和左邊元素進行比較，如果比較到一個比自己小的元素時就可以停止比較了，因為左邊已經呈現有序狀態，找到比自己小的元素時，就不用再往後比較了。
插入排序的代碼實現
- 插入排序的輪數和冒泡排序一樣，但是i從1開始，因為我們假設第一個元素已經是呈現有序狀態了。
- 內部循環依次從當前位置開始，和前面元素進行比較，如果找到了比自己小的元素，則停止比較，直接退出本輪比較，進行下一輪比較
總結
- 雖然三種排序法的時間複雜度都是O(N2)，但是不同的場景還是會有不同的性能差異。
- 冒泡排序法是性能最差的算法，正式運用中，基本不會用冒泡排序法進行排序。
- 選擇排序將交換次數降到最低，但是比較次數仍然很大。當數據量小，並且交換耗時相對於比較耗時更多的情況下，選擇排序是個不錯的選擇。
- 基本有序的情況下，插入排序是最好的選擇，但是如果數據基本逆序的情況下，插入排序的性能和冒泡排序就基本一樣了。
- 從平均情況下來看，插入排序性能會比選擇排序略好一些。
閱讀更多 跟老司機學Java 的文章
