Embedded Files
排序就是將資料由小到大或由大到小排列，常見排序演算法有氣泡排序、選擇排序、插入排序、合併排序與快速排序等，其中以合併排序與快速排序的演算法效率比較好，但程式也較複雜。
(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)最後只剩最後一個元素就不用在比較了，到此完成氣泡排序。
氣泡排序演算法程式
氣泡排序演算法執行結果
排序前
55 78 89 45 65
氣泡排序外層迴圈執行第 1 次
55 78 45 65 89
氣泡排序外層迴圈執行第 2 次
55 45 65 78 89
氣泡排序外層迴圈執行第 3 次
45 55 65 78 89
氣泡排序外層迴圈執行第 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)，到此完成排序。
合併排序演算法程式
函式mergesort用於切割，函式merge用於合併兩個已排序陣列。
合併排序演算法執行結果
排序前
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)的記憶體空間。
(5)比較各排序演算法的效率
(6)使用Python內建排序函式進行排序
Python的串列提供函式sort排序串列，會直接修改串列元素，無法回傳新的串列；另外可以使用函式sorted排序串列，會回傳新的串列。排序演算法的效率為O(n*log(n))，不用辛苦撰寫合併排序或快速排序，直接呼叫使用。
排序演算法的函式說明，如下表。
使用sort與sorted的排序程式
使用內建排序程式執行結果
55 78 89 45 65 99 23 35
55 78 89 45 65 99 23 35
23 35 45 55 65 78 89 99
23 35 45 55 65 78 89 99
99 89 78 65 55 45 35 23
Page updated
Google Sites
Report abuse