寫程式的基本功-排序演算法(Sorting Algorithm)


這裡所稱的排序(Sorting),是指將一串不規則的數值資料(如陣列資料)依照遞增或是遞減的方式重新編排。要將一串不規則的數值資料遞增或是遞減排列,方法當然不會只有一種,而不同方法排列資料的難易度、速度和其它特性自然也會有所不同。排序演算法(Sorting Algorithm)就是排列資料的方法,目前已知的方法有很多,在這篇文章中將會介紹比較實用的六種排序演算法,分別是氣泡排序(bubble sort)、交換排序(exchange sort)、選擇排序(selection sort)、插入排序(insertion sort)、快速排序(quick sort)和合併排序(merge sort)。

氣泡排序法(Bubble Sort)

氣泡排序法的概念

氣泡排序法(又稱泡沫排序法)是最常見的排序演算法,因為它簡單、易懂、容易撰寫,在優化過後的效能也不算太差。所謂「氣泡」,顧名思義,就是它的排序方式如同氣泡一般,不斷將最大的元素擠出(移動)到陣列最尾端,當所有元素都如同氣泡般被被擠出後,排序就完成了!

氣泡排序法的過程

假設現在有個陣列資料,內容如下:

要如何將它遞增排列呢?

一開始,要將重點聚焦於陣列最尾端的位置,因為我們要先將整個陣列的最大值移動到陣列的最尾端。那麼,該如何從陣列中找到最大值並將其移動到最尾端呢?

從陣列最前方開始,逐次兩兩比較元素的大小,將兩個元素中較大的元素排在後面,即可逐漸將最大的元素從陣列前方擠到陣列後方。這就像是沉在水中的大氣泡,像要漂浮到水面上前,必須擠開其他的小氣泡一樣。

所以,若要擠出陣列的最大值至陣列的最尾端,位於陣列最前端的的69,要跟之後的元素(81)比大小,如下表:

69比81小,所以不用換位置。然後再比81和30的大小,如下表:

81比30大,所以81會擠開30,與30交換,排在30之後。

然後再比81和38的大小,如下表:

81比38大,所以81會擠開38,與38交換,排在38之後。

繼續判斷大小並移動,直到最大值被擠到陣列最尾端:

陣列的最大元素「81」成功被擠出至最尾端,接著用同樣的方法繼續找出第二大的元素,並將其擠出至尾端第二個位置,再找出第三大的元素,並將其擠出至尾端第三個位置。直到所有元素都被擠出為止,陣列就排序完成了!過程如下:

氣泡排序法的程式實作

氣泡排序法優化

從上面氣泡排序法的排序例子中,可以看到陣列在排序的過程中早就已經明顯排好了,但程式依然必須要執行完整的迴圈後才會停止。所以我們可以在每次從陣列最前端擠出最大元素至尾端的時候,記錄是否有元素被擠出,如果沒有,表示陣列已經排列完成了,就不用再嘗試擠出所有的元素了。利用記錄陣列是否有元素被擠出的方式優化之後的氣泡排序法可以改寫如下:

雖然在上面氣泡排序法的排序例子中不明顯,但氣泡排序法還存在著另外一個問題,那就是當陣列最前端的幾個元素若不小心早就在過程中排序好了,在擠出最大元素至尾端的時候又會再次重複比較大小,會浪費許多時間在做同一件事情上。因此,可以改良一下氣泡排序法,使其能夠將最大元素從最前端擠到尾端,也可以將最小元素從最尾端擠到前端,雙管齊下。改良後的氣泡排序法程式如下:

氣泡排序法的複雜度

最差時間複雜度:O(n2)

最佳時間複雜度:O(n) (排序正序的陣列)

平均時間複雜度:O(n2)

額外最差空間複雜度:O(1)

交換排序法(Exchange Sort)

交換排序法的概念

交換排序是最簡單的排序方法。從陣列最前端開始尋找最小的元素放置於最前端中,接著再從陣列次前端的位置開始尋找最小的元素放置於次前端中,在尋找最小元素的過程中,遇到比目前更小的元素就進行交換,最後就可以換成最小的元素。

交換排序法的過程

假設現在有個陣列資料,內容如下:

要如何將它遞增排列呢?

一開始,要將重點聚焦於陣列最前端的位置,因為我們要先將整個陣列的最小值移動到陣列的最前端。那麼,該如何從陣列中找到最小值並將其移動到最前端呢?

從陣列最前端開始,與陣列之後的元素比大小,若找到比最前端還小的元素,就進行交換,如下表:

69比81小,所以不用換位置。然後再比69和30的大小,如下表:

69比30大,所以會與30交換。

繼續判斷大小並交換,直到判斷至最尾端:

判斷至最尾端後,最前端的元素即可確定是陣列中最小的元素,接著用同樣的方法繼續找出第二小的元素,並將其交換至前端第二個位置,再找出第三小的元素,並將其交換至前端第三個位置。直到所有元素位置都被確認過之後,陣列就排序完成了!過程如下:

交換排序法的程式實作

交換排序法的優化

從上面的例子中,可以發現交換排序法在找到最小元素之前的交換都是毫無意義的,導致交換元素的次數變得十分的多。因此,若能減少沒有必要的交換次數,就可以讓程式效能大增。朝這個方向去優化交換排序法的結果,就是選擇排序法了。

交換排序法的複雜度

最差時間複雜度:O(n2)

最佳時間複雜度:O(n2) (排序正序的陣列)

平均時間複雜度:O(n2)

額外最差空間複雜度:O(1)

選擇排序法(Selection Sort)

選擇排序法的概念

選擇排序法也是很簡單的排序方法,為交換排序法的優化版,在使用交換排序法時尋找最小元素的過程中不直接交換陣列的元素,而是記下目前搜尋到最小元素的索引值,最後再進行元素交換。

選擇排序法的過程

建議先了解交換排序法的過程,再來看選擇排序法。

假設現在有個陣列資料,內容如下:

要如何將它遞增排列呢?

一開始,要將重點聚焦於陣列最前端的位置,因為我們要先將整個陣列的最小值移動到陣列的最前端。那麼,該如何從陣列中找到最小值並將其移動到最前端呢?

先假設目前陣列最前端的元素為最小值,再與其之後的元素比大小,若找到比目前假設最小元素還小的元素,就記下索引值,如下表:

69比81小,假設的最小元素之索引位置不用更動。然後再比69和30的大小,如下表:

69比30大,所以最小元素之索引位置變成2。

繼續判斷大小並更改最小元素之索引位置,直到判斷至最尾端:

判斷至最尾端後,即可找到最小元素的位置,再將最前端的元素和最小元素交換,如下表:

接著用同樣的方法繼續找出第二小的元素,並將其交換至前端第二個位置,再找出第三小的元素,並將其交換至前端第三個位置。直到所有元素位置都被確認過之後,陣列就排序完成了!過程如下:

選擇排序法的程式實作

選擇排序法的複雜度

最差時間複雜度:O(n2)

最佳時間複雜度:O(n2) (排序正序的陣列)

平均時間複雜度:O(n2)

額外最差空間複雜度:O(1)

插入排序法(Insertion Sort)

插入排序法的概念

在原陣列中建立一個保證順序的子陣列(通常位於陣列最前端),將子陣列之後的下一個元素視為要插入至子陣列的元素。將元素插入至保證順序的子陣列時,會從子陣列最尾端開始往前判斷要插入的元素是否大於等於目前判斷位置的元素,若有,則將元素放置於目前判斷位置後一個的位置;若沒有,則將目前判斷位置的元素往後移一個位置,拉出空格以便讓其他元素使用。

插入排序法的過程

假設現在有個陣列資料,內容如下:

要如何將它遞增排列呢?

一開始,排序好的子陣列尚未建立,因此直接將索引0的元素作為進入子陣列的第一個元素。再來要將之後的元素插入至這個子陣列中,並確保子陣列元素的順序,插入元素的過程如下:

插入排序法的程式實作

插入排序法的複雜度

最差時間複雜度:O(n2) (排序逆序的陣列)

最佳時間複雜度:O(n) (排序正序的陣列)

平均時間複雜度:O(n2)

額外最差空間複雜度:O(1)

快速排序法(Quick Sort)

快速排序法的概念

快速排序法算是比較進階的排序方法,它的速度在大多數的情況下比前面四種都快,當然也難了許多。大致上來說,就是先在陣列中找出一個pivot(支點、中心點),想辦法將比pivot小的元素移動到pivot的左邊,比pivot大的元素移動到pivot的右邊,接著再用同樣的方法繼續對pivot的左邊子陣列和右邊子陣列進行排序

快速排序法的過程

假設現在有個陣列資料,內容如下:

要如何將它遞增排列呢?

一開始,將陣列最左端(最前端)的位置與元素定為pivot,如下表所示:

接著從最右端開始,尋找比pivot元素還要小的元素,可以找到索引8的32,如下表所示:

接著從除了pivot的最左端開始,尋找比pivot元素還要更大的元素,可以找到索引1的81,如下表所示:

若比pivot更大的元素位置小於比pivot更小的元素位置(即比pivot更大的元素在比pivot更小的元素左邊),則交換兩個元素的位置,如下表所示:

接著從原先比pivot更小的元素位置繼續向左尋找比pivot更小的元素,可以找到索引7的61,如下表所示:

因為索引7還在原先比pivot更大的元素位置之右邊,因此再繼續從原先比pivot更大的元素位置向右尋找比pivot更大的元素。可以找到索引8的81,如下表所示:

此時比pivot更大的元素位置大於比pivot更小的元素位置(即比pivot更大的元素在比pivot更小的元素右邊),則將比pivot更小的元素與pivot元素交換,如下表所示: