排序(Python)

排序就是將資料由小到大或由大到小排列，常見排序演算法有氣泡排序、選擇排序、插入排序、合併排序與快速排序等，其中以合併排序與快速排序的演算法效率比較好，但程式也較複雜。

(1)氣泡排序演算法

假設由小到大排序五個數字，55、78、89、45與65，從頭到尾不斷比較交換相鄰兩數，直到最大數到最後位置，縮小比較的範圍，再找出縮小範圍的最大數字放置於最後，直到剩下一個元素為止。

Ste1)排序第1個到第5個元素，從前往後每次比較交換相鄰兩數，最後前5個元素的最大數89就在最後面。

—Step2)排序第1個到第4個元素，從前往後每次比較交換相鄰兩數，最後前4個元素的最大數78就在最後面。

Step3)排序第1個到第3個元素，從前往後每次比較交換相鄰兩數，最後前3個元素的最大數65就在最後面。

Step4)排序第1個到第2個元素，從前往後每次比較交換相鄰兩數，最後前2個元素的最大數55就在最後面。

Step5)最後只剩最後一個元素就不用在比較了，到此完成氣泡排序。

氣泡排序演算法執行結果

排序前

89 55 78 45 65

外層迴圈執行 1 次結果為

55 89 78 45 65

外層迴圈執行 2 次結果為

55 78 89 45 65

外層迴圈執行 3 次結果為

45 55 78 89 65

外層迴圈執行 4 次結果為

45 55 65 78 89

排序後

45 55 65 78 89

氣泡排序演算法效率分析

假設要排序5個資料，程式中第7行到第12行為氣泡排序演算法，外層迴圈i數值由4到1，每次遞減1，外層每執行一次，則內層執行i次，內層迴圈的執行總次數影響整個程式的執行效率，累加內層迴圈的執行次數為「4+3+2+1」，假設要排序n個資料，累加內層迴圈的執行次數為「(n-1)+(n-2)+(n-3)+…+2+1」，總次數接近「n^2」，演算法效率為O(n^2)。

(2)插入排序演算法

假設由小到大排序五個數字，89、55、78、45與65，先考慮前兩個元素，將第2個元素插入到指定的位置，讓第1個到第2個元素由小到大排序好，再考慮前三個元素，將第3個元素插入到指定的位置，讓第1個到第3個元素由小到大排序好，依此類推，直到考慮前n個元素，將第n個元素插入到指定的位置，讓第1個到第n個元素由小到大排序好。

Ste1)先考慮前兩個元素，將第2個元素插入到指定的位置，讓第1個到第2個元素由小到大排序好。

Step2)先考慮前三個元素，將第3個元素插入到指定的位置，讓第1個到第3個元素由小到大排序好。

Step3)先考慮前四個元素，將第4個元素插入到指定的位置，讓第1個到第4個元素由小到大排序好。

Step4)先考慮前五個元素，將第5個元素插入到指定的位置，讓第1個到第5個元素由小到大排序好。

插入排序演算法執行結果

排序前

89 55 78 45 65

外層迴圈執行 1 次結果為

55 89 78 45 65

外層迴圈執行 2 次結果為

55 78 89 45 65

外層迴圈執行 3 次結果為

45 55 78 89 65

外層迴圈執行 4 次結果為

45 55 65 78 89

排序後

45 55 65 78 89

插入排序演算法效率分析

假設要排序4個資料，程式中第7行到第16行為插入排序演算法，外層迴圈i數值由1到4，每次遞增1，外層每執行一次內層最多執行i次，內層迴圈的執行總次數影響整個程式的執行效率，累加內層迴圈的執行次數為「1+2+3+4」。假設要排序n個資料，「1+2+3+…+(n-2)+(n-1)」，總次數接近「n^2」，演算法效率為O(n^2)。

(3)合併排序演算法

使用合併排序排序8個元素—(55,78,89,45,65,99,23,35)

Step1)先考慮將8個元素分成左右兩半各4個元素，左邊4個元素(55,78,89,45)優先處理。

Step2)考慮將左邊4個元素(55,78,89,45)再分成左右兩半各2個元素，左邊2個元素(55,78)優先處理。

Step3)考慮將左邊2個元素(55,78)分成左右兩半各1個元素(55)與(78)，到此只剩一個元素左右兩邊都已完成排序，將左右兩邊合併成一個已排序陣列(55,78)。

Step4)考慮將右邊2個元素(89,45)分成左右兩半各1個元素(89)與(45)，到此只剩一個元素左右兩邊都已完成排序，將左右兩邊合併成一個已排序陣列(45,89)。

Step5)考慮左右兩邊各2個元素(55,78)與(45,89)都已完成排序，將左右兩邊合併成一個已排序陣列(45,55,78,89)。

Step6)考慮右邊4個元素(65,99,23,35) 。

Step7)考慮將左邊4個元素(65,99,23,35)再分成左右兩半各2個元素，左邊2個元素(65,99)優先處理。

Step8)考慮將左邊2個元素(65,99)分成左右兩半各1個元素(65)與(99)，到此只剩一個元素左右兩邊都已完成排序，將左右兩邊合併成一個已排序陣列(65,99)。

Step9)考慮將右邊2個元素(23,35)分成左右兩半各1個元素(23)與(35)，到此只剩一個元素左右兩邊都已完成排序，將左右兩邊合併成一個已排序陣列(23,35)。

Step10)考慮左右兩邊各2個元素(65,99)與(23,35)都已完成排序，將左右兩邊合併成一個已排序陣列(23,35,65,99)。

Step11)考慮左右兩邊各4個元素(45,55,78,89)與(23,35,65,99)都已完成排序，將左右兩邊合併成一個已排序陣列(23,35,45,55,65,78,89,99)，到此完成排序。

合併排序演算法執行結果

排序前

55 78 89 45 65 99 23 35

L= 0 M= 0 R= 1

55 78 89 45 65 99 23 35

L= 2 M= 2 R= 3

55 78 45 89 65 99 23 35

L= 0 M= 1 R= 3

45 55 78 89 65 99 23 35

L= 4 M= 4 R= 5

45 55 78 89 65 99 23 35

L= 6 M= 6 R= 7

45 55 78 89 65 99 23 35

L= 4 M= 5 R= 7

45 55 78 89 23 35 65 99

L= 0 M= 3 R= 7

23 35 45 55 65 78 89 99

排序後

23 35 45 55 65 78 89 99

合併排序演算法效率分析

假設要排序n個資料，程式中第4行到第36行為合併排序演算法，第30行到第31行的mergesort函式每次將資料拆成一半，所以合併排序的mergesort的遞迴深度為O(log(n))，第32行的merge動作每一層都需要O(n)，所以合併演算法效率為O(n*log(n))，相較於氣泡排序與插入排序演算法效能較佳，但排序過程須額外使用O(n)的暫存記憶體空間，所以記憶體空間的使用較氣泡排序與插入排序演算法來的多。

(4)快速排序演算法

使用快速排序由小到大排序8個元素(55,78,89,45,65,99,23,35)

Step1)將第1個元素(55)當成標兵，使用i由前往後找出比55大的元素，使用j由後往前找出比55小的元素。

Step2)若i小於j，則交換兩數。

Step3)將第1個元素(55)當成標兵，使用i由前往後找出比55大的元素，使用j由後往前找出比55小的元素。

Step4)若i小於j，則交換兩數。

Step5)將第1個元素(55)當成標兵，使用i由前往後找出比55大的元素，使用j由後往前找出比55小的元素。

Step6) 若i小於j，則交換兩數，否則將第1個元素(55) 與第j個元素互換。

Step7)元素(55)找到排序好時所在的位置，分成左邊(45,35,23)與右邊(65,99,89,78)分別執行快速排序。

Step8)縮小快速排序範圍到第1個到第3個元素(45,35,23)，將第1個元素(45)當成標兵，使用i由前往後找出比45大的元素，使用j由後往前找出比45小的元素。

Step9) 若i小於j，則交換兩數，否則將第1個元素(45) 與第j個元素互換。

Step10)元素(45)找到排序好時所在的位置，分成左邊(23,35)與右邊沒有元素()，左邊繼續執行快速排序。

Step11)縮小快速排序範圍到第1個到第2個元素(23,35)，將第1個元素(23)當成標兵，使用i由前往後找出比23大的元素，使用j由後往前找出比23小的元素，若i小於j，則交換兩數，否則將第1個元素(23) 與第j個元素互換。

Step12)元素(23)找到排序好時所在的位置，分成左邊沒有元素()與右邊(35) ，不須繼續排序。

Step13)縮小快速排序範圍到第5個到第8個元素(65,99,89,78)，將第5個元素(65)當成標兵，使用i由前往後找出比65大的元素，使用j由後往前找出比65小的元素，若i小於j，則交換兩數，否則將第5個元素(65) 與第j個元素互換。

Step14)元素(65)找到排序好時所在的位置，分成左邊沒有元素()與右邊(99,89,78) ，右邊(99,89,78)使用快速排序進行排序。

Step15)縮小快速排序範圍到第6個到第8個元素(99,89,78)，將第6個元素(99)當成標兵，使用i由前往後找出比99大的元素，使用j由後往前找出比99小的元素。

Step16) 若i小於j，則交換兩數，否則將第6個元素(99) 與第j個元素互換。

Step17)元素(99)找到排序好時所在的位置，分成左邊(78,89)與右邊沒有元素() ，左邊(78,89)使用快速排序進行排序。

Step18)縮小快速排序範圍到第6個到第7個元素(78,89)，將第6個元素(78)當成標兵，使用i由前往後找出比78大的元素，使用j由後往前找出比78小的元素，若i小於j，則交換兩數，否則將第6個元素(78) 與第j個元素互換。

Step19)元素(78)找到排序好時所在的位置，分成左邊沒有元素() 與右邊(89)， 不須繼續排序。

快速排序演算法執行結果

排序前

55 78 89 45 65 99 23 35

L= 0 j= 3 R= 7

45 35 23 55 65 99 89 78

L= 0 j= 2 R= 2

23 35 45 55 65 99 89 78

L= 0 j= 0 R= 1

23 35 45 55 65 99 89 78

L= 4 j= 4 R= 7

23 35 45 55 65 99 89 78

L= 5 j= 7 R= 7

23 35 45 55 65 78 89 99

L= 5 j= 5 R= 6

23 35 45 55 65 78 89 99

排序後

23 35 45 55 65 78 89 99

快速排序演算法效率分析

假設要排序n個資料，程式中第7行到第26行為快速排序演算法，第25行到第26行的quicksort函式每次將資料拆成一半或接近一半，所以快速排序的quicksort的遞迴深度接近O(log(n))，每一層都需要O(n)，所以快速排序演算法平均效率為O(n*log(n))，相較於氣泡排序與插入排序演算法效能較佳，但最差情形就是每次切割都很不均勻，分成一邊只有1個數字，另一邊是n-1個數字(當數字已經由大到小或由小到大完成排序時)，這時快速排序演算法效率為O(n^2)，並不會比氣泡排序與插入排序演算法來的好。相較於合併排序演算法，最差情形合併排序比快速排序效率要好，快速排序平均而言需使用O(log(n))記憶體空間，因為遞迴深度所占記憶體空間，而合併排序須額外使用O(n)的記憶體空間。

(6)使用Python內建排序函式進行排序

Python的串列提供函式sort排序串列，會直接修改串列元素，無法回傳新的串列；另外可以使用函式sorted排序串列，會回傳新的串列。排序演算法的效率為O(n*log(n))，不用辛苦撰寫合併排序或快速排序，直接呼叫使用。