基本排序
插入排序（Insertion Sort）
- 時間複雜度（最優）：O(n) 當資料的順序正好是由小到大，每回合只需要比較1次。
- 時間複雜度（最差）：Ο(n2) 當資料順序正好是由大到小，每N回合需要比較N次。
- 時間複雜度（平均）：Ο(n2)
- 空間複雜度：總共O(n)
思路：每次將一個待排序的元素，拿來和已排序的元素進行逐一比較，直到找到合適的位置插入。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
let list1 = [70, 2, 5, 20, -7, -23, 0, 2, 30, 97, -3, 4, 71, 5] let list2 = ["e", "b", "x", "h", "n", "b", "w", "c", "o", "g", "z", "u", "z"] let list3 = ["A"] // 插入排序 func insertionSort<T: Comparable>(_ array:[T], _ compare:(T, T) -> Bool) -> [T] { var tempArray = array for position in 1..<tempArray.count { var pointer = position while pointer > 0 && compare(tempArray[pointer], tempArray[pointer - 1]) { swap(&tempArray[pointer], &tempArray[pointer - 1]) pointer -= 1 } } return tempArray } let insertionSorted1 = insertionSort(list1, <) // [-23, -7, -3, 0, 2, 2, 4, 5, 5, 20, 30, 70, 71, 97] let insertionSorted2 = insertionSort(list2, <) // ["b", "b", "c", "e", "g", "h", "n", "o", "u", "w", "x", "z", "z"] let insertionSorted3 = insertionSort(list3, <) // ["A"] |
希爾排序（Shell Sort）
又稱為「遞減增量排序」，是「插入排序」的優化版。另外，這裡有一個短片，通過跳舞的方式展示Shell Sort是如何運作的。
「插入排序」是不斷的比較鄰近的數字，而「希爾排序」則是先以一定的跨度來進行比較，最後和「插入排序」一樣進行臨近的比較，從而提高效率。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
let list1 = [70, 2, 5, 20, -7, -23, 0, 2, 30, 97, -3, 4, 71, 5] let list2 = ["e", "b", "x", "h", "n", "b", "w", "c", "o", "g", "z", "u", "z"] let list3 = ["A"] // 希爾排序 (Shell Sort) func shellSort<T: Comparable>(_ array:[T], compare:(T,T) -> Bool) -> [T] where T:Comparable { var tempArray = array var gap = array.count/2 while gap > 0 { for position in 0..<tempArray.count { guard position + gap < tempArray.count else { break } if compare(tempArray[position], tempArray[position + gap]) { swap(&tempArray[position], &tempArray[position + gap]) } guard gap == 1 && position > 0 else { continue } if tempArray[position - 1] > tempArray[position] { swap(&tempArray[position - 1], &tempArray[position]) } } gap /= 2 } return tempArray } |
選擇排序（Selection Sort）
黃色為已排序、紅色為當前最小、藍色為當前位置。
思路：從未排序的元素中找到一個最大（小）的元素放到第一位，接著接著從未排序中找到下一個最大（小）的元素放到已排序的末端，直到排序完成。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
let list1 = [70, 2, 5, 20, -7, -23, 0, 2, 30, 97, -3, 4, 71, 5] let list2 = ["e", "b", "x", "h", "n", "b", "w", "c", "o", "g", "z", "u", "z"] let list3 = ["A"] // 選擇排序 func selectionSort<T: Comparable>(_ array:[T], _ compare:(T,T) -> Bool) -> [T] { guard array.count > 1 else { return array } var tempArray = array for position in 0..<tempArray.count { var pointer = position + 1 var targetPosition = position while pointer < tempArray.count { if compare(tempArray[targetPosition], tempArray[pointer]) { targetPosition = pointer } pointer += 1 } if targetPosition != position { swap(&tempArray[position], &tempArray[targetPosition]) } } return tempArray } let selectionSorted1 = selectionSort(list1, >) let selectionSorted2 = selectionSort(list2, >) let selectionSorted3 = selectionSort(list3, >) <br> |
推薦&參考
- 一個用動畫來演示排序算法過程的工具SORTING。
- Swift Algorithm Club
- 當然，Wikipedia也可以找到「算法」的說明，比如「快速排序」。