經典的排序算法有八種,分別為:
冒泡排序選擇排序插入排序歸併排序希爾排序快速排序堆排序基數排序其中冒泡排序、選擇排序、插入排序稱為三大基本排序。
雖然這三大基本排序算法時間複雜度都是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次,依次類推,實現整體排序
冒泡排序法的代碼實現
冒泡排序法優化
以上的冒泡排序法還有優化的空間。因為如果一個數組已經是完全有序的情況下,冒泡排序法仍然會進行逐輪的比較,這無疑是浪費性能的行為。因此我們可以確定,當冒泡的比較中,有一輪如果沒有發生交換,則可以確定當前數組已經完全有序,後面的輪數完全不必在進行。故做以下的調整:
通過定義一個標識符isSort,如果有一輪沒有發生任何交換,則isSort就會為true,下次直接break,後面的輪數就不用再進行比較了。
選擇排序
選擇排序的思路
基本思路:
選擇排序和冒泡排序不同,選擇排序會通過一輪比較,選出最小的那個元素的下標,然後和第一個元素進行交換,這樣第一個元素的位置就可以確定了。
第二輪如法炮製,從第二個元素開始依次比較,選出最小的元素的下標,和第二個元素交換位置,這樣第二小的元素位置就確定了。
後面依次類推,直到整個數組呈現有序狀態。
選擇排序法的代碼實現
插入排序
插入排序的思路
基本思路
假設一個數組已經基本有序,則這個時候插入排序就是一個不錯的選擇。插入排序是先保證左邊元素是基本有序的,然後將後面的元素依次和左邊元素進行比較,如果比較到一個比自己小的元素時就可以停止比較了,因為左邊已經呈現有序狀態,找到比自己小的元素時,就不用再往後比較了。
插入排序的代碼實現
總結
雖然三種排序法的時間複雜度都是O(N2),但是不同的場景還是會有不同的性能差異。冒泡排序法是性能最差的算法,正式運用中,基本不會用冒泡排序法進行排序。選擇排序將交換次數降到最低,但是比較次數仍然很大。當數據量小,並且交換耗時相對於比較耗時更多的情況下,選擇排序是個不錯的選擇。基本有序的情況下,插入排序是最好的選擇,但是如果數據基本逆序的情況下,插入排序的性能和冒泡排序就基本一樣了。從平均情況下來看,插入排序性能會比選擇排序略好一些。