# [資演] 排序演算法
###### tags: `資演`
在今天的課程中，我們將學習到什麼是排序演算法，以及它們是如何工作的。首先，讓我們來談談什麼是排序演算法。
排序演算法是一種演算法，它可以幫助你將一堆數字或其他資料排列成一個有序的列表，通常是用由小到大的順序。
大多數排序演算法有兩個基本步驟：比較和交換。首先，程式會比較陣列中的要素，以確定它們是否應該排列在一起以及用什麼方式排列。 然後是交換：一旦程式比較了一對要素，它會代表它們的位置對調，以使他們按照正確的排列順序排列。比較和交換步驟會繼續重複，直到陣列被完全排序為止。
排序演算法包括許多不同的演算法，其中包括選擇排序、氣泡排序、快速排序等。我們將探討每一種演算法，以及它們是如何將指定的資料排列成一個有秩序的列表。
## 選擇排序
選擇排序（selection sort）演算法是一種排序演算法，也被稱為直接選擇排序。它的原理是通過不斷地從未排序的array中找出最小的元素，並將其添加到有序的array中。
選擇排序的執行步驟如下：
1. 從array（通常是未排序的）中找出最小的元素，並將它放置在第一個位置。
2. 遍歷剩下的元素，找到最小的那個元素，並將其放置在下一個位置。
3. 繼續重複上述步驟，直到整個array排序完畢（array中所有元素都排序完成）。
選擇排序演算法是一種原地排序演算法，不需要額外的存儲空間，只需要根據比較的結果來變更原本的array排序。
該演算法的時間複雜度為 $O(n^2)$，是一種不穩定的排序演算法。
```python=
def selection_sort(nums):
# 遍歷整個列表
for i in range(len(nums)):
# 初始假設最小的是第一個元素
minimum = i
# 用此元素與列表中的其他元素進行比較，找出最小元素
for j in range(i + 1, len(nums)):
if nums[j] < nums[minimum]:
minimum = j
# 如果最小元素改變，替換
if minimum != i:
nums[i], nums[minimum] = nums[minimum], nums[i]
# 測試程式碼
arr = [19, 2, 31, 45, 30, 11, 121, 27]
selection_sort(arr)
print(arr)
```
## 氣泡排序
氣泡排序（bubble sort），也叫做交換排序，是一種簡單且眾所周知的排序演算法，其特點就是重複的比較和交換相鄰的元素，使得排序的元素慢慢的「冒」到最終的位置，所以也叫做「冒泡排序」。
冒泡排序主要由一個兩層的迴圈組成，外圈為 $n-1$ 次，其對應的是 $n$ 個數字的第一輪比較，使得最大的數字慢慢的“冒泡”到順序位置；而内圈為 $n-1-i$ 次，其對應的是 $n-1-i$ 個數字的比較，使得排序好的數字不會受到順序影響。
此外，冒泡排序也是一種原地排序演算法，僅需要 $O(1)$ 的空間複雜度，並且屬於一種穩定的演算法。
```python=
def bubbleSort(nums):
n = len(nums)
# 用一個迴圈執行到數組的倒數第二個元素
for i in range(n-1):
# 用另一個迴圈執行來自第一個元素到最後一個前一個元素
for j in range(0, n-i-1):
if nums[j] > nums[j+1] :
nums[j], nums[j+1] = nums[j+1], nums[j]
# 測試
arr = [5,2,7,1,3]
bubbleSort(arr)
print(arr) # 印出[1, 2, 3, 5, 7]
```
## 堆排序
堆排序（heap sort）是一種排序演算法，比較適合用在資料量大時，以空間換取時間做運算，所以使用時需要小心，以確保不影響系統資源太多。Heap Sort 演算法分為兩個部分，一個是建構 heap的步驟（heapify），另一個是排序的步驟。
建構 heap 的部分，會先將輸入的陣列轉成 heap（實際上是將原本陣列中的元素重新對應到 heap 中的節點），Heap 的特點之一是，它的父節點的值會大於或等於它的子節點（max-heap），運用這個特點，我們可以將原本陣列中的元素依序存到 heap 中，過程中確保堆積樹（heap）的特點。
接下來是排序的步驟，此步驟會先將 heap 的根節點（第一個最大的值）放置到堆積樹最後，接著將最後一個元素放置到堆積樹的根節點，並且重新產生 heap ，重複以上步驟，就可以依序排序出使用者輸入的陣列。
下面是一個 Heap Sort 的 python 程式碼，此範例排序將大的值放到尾端：
```python=
def heapify(arr, n, i): # 建構 heap
largest = i # 假設 root node
l = 2 * i + 1 # 左子樹
r = 2 * i + 2 # 右子樹
# root node 比子節點大時
if l < n and arr[i] < arr[l]:
largest = l
# root node 比子節點大時
if r < n and arr[largest] < arr[r]:
largest = r
# 將 root node 放大的一邊
if largest != i:
arr[i],arr[largest] = arr[largest],arr[i]
# heapify
heapify(arr, n, largest)
def heapSort(arr): # start from here
n = len(arr)
# build a maxheap
for i in range(n, -1, -1):
heapify(arr, n, i)
# One by one extract elements
for i in range(n-1, 0, -1):
arr[i], arr[0] = arr[0], arr[i]
heapify(arr, i, 0)
# Input Array
arr = [12, 11, 13, 5, 6, 7]
heapSort(arr)
n = len(arr)
print ("Sorted array is")
for i in range(n):
print ("%d" %arr[i]),
```
## 合併排序
合併排序（merge sort） 是一個演算法，藉由分割、排序、合併來將一個陣列（或區段）的值排序。
合併排序演算法的子步驟：
1. 將陣列分割（Divide）：這是演算法的一個遞迴步驟，直到分割到只剩一個個體為止，以此來達成將給定的陣列分為更小的陣列（Unit Size）。
2. 排序（Conquer）：對於每個個體做排序，直到只剩一個個體為止，以此來達成將小的個體排序完成。
3. 合併（Combine）：將兩個子陣列利用比較技巧，合併成單一有序的陣列。
合併排序的優點：
- 時間複雜度為 $O(n\log n)$ 。
- 合併排序是一個穩定的排序，它保證相同值的順序不會改變。
- 合併排序比較容易實作，只需要兩個遞迴函式和兩個主循環即可完成。
合併排序的缺點：
- 它需要花費較多的空間來輔助我們做排序。
- 適合於大型數據的排序，如果數據的量小，則不是一個好的排序演算法。
以下是使用 Python 來實作合併排序的程式碼：
```python=
def mergesort(arr):
# 假如陣列只有一個個體，則返回
if len(arr) == 1:
return arr
else:
# 分割陣列
mid = len(arr)//2
left = arr[:mid]
right = arr[mid:]
# 遞迴呼叫自己，此時已經將陣列分割成一個個體
l1 = mergesort(left)
l2 = mergesort(right)
# 開始合併兩個陣列
# 兩個陣列各自都已排好序，使用比較技巧只需要 3 個步驟即可
i, j, k = 0, 0, 0
while i < len(l1) and j < len(l2):
if l1[i] < l2[j]:
arr[k] = l1[i]
i += 1
else:
arr[k] = l2[j]
j += 1
k += 1
# 如果任一陣列不全部被放入 arr ，則將另外一個陣列的個體全部放入 arr
while i < len(l1):
arr[k] = l1[i]
i += 1
k += 1
while j < len(l2):
arr[k] = l2[j]
j += 1
k += 1
return arr
```
## 快速排序
快速排序（quick sort）是一種遞迴排序演算法，它的特色是可以在 $O(n\log n)$ 的時間內完成排序。它的基本思路是：
1. 取出排序數列中的一個元素，作為基準值（pivot）；
2. 把小於基準值的元素移到底部，把大於基準值的元素移到頂部；
3. 將這個子問題分成兩個子問題，對左右子問題分別進行同樣的程序（即快速排序）
快速排序確定一個基準值，然後將比基準值小的元素移到它的左邊，比基準值大的元素移到它的右邊，以此方法將數列分為兩組，接下來再對兩組數列分別進行同樣的操作，直到兩組中所有的數都按照基準值的大小分配到正確的位置為止，排序完成。
```python=
def quickSort(arr):
if len(arr) <= 1:
return arr # 基底結果，只有一個元素時直接返回
pivot = arr[len(arr) // 2] # 選基準值
left = [x for x in arr if x < pivot] # 小於基準值的元素置於左邊
middle = [x for x in arr if x == pivot] # 等於基準值的元素留在中間
right = [x for x in arr if x > pivot] # 大於基準值的元素置於右邊
return quickSort(left) + middle + quickSort(right) # 遞歸調用
# test
arr = [3,5,7,2,4,9,8,1]
print(quickSort(arr)) # [1, 2, 3, 4, 5, 7, 8, 9]
```
## 基數排序
基數排序（Radix Sort）其中一種特殊的排序演算法，它的原理是把數字的各位數字一個一個比較，並根據比較的結果來重新排序，此演算法特別適用在排序處理又要使用數字的狀況中。
Radix Sort 執行的步驟如下所述：
1. 從最低位數字開始判斷，並依照位數分到不同的桶子中；
2. 再從右到左開始比較，按照位數大小重新排序；
3. 並按順序取出排序好的數字後，開始比較下一個位數；
4. 重複上述比較、排序、取出等動作，直到比較完所有位數，至此完成Radix Sort的演算法。
使用Python來實作Radix Sort可參考以下程式碼：
```python=
def radixSort(arr):
# Determine maximum number of digits
max_digits = max([len(str(i)) for i in arr])
# Do counting sort for every digit. Note that instead
# of passing digit number, exp is passed.exp is 10^i
# where i is current digit number
exp = 1
while max_digits>=exp:
temp_arr = [0]*10
# Store count of occurrences in temp_arr[]
for i in range(0, len(arr)):
index = (arr[i]/exp)
temp_arr[ (index)%10 ] += 1
# Change count_arr[i] so that count_arr[i] now contains
# actual position of this digit in output[]
for i in range(1,10):
temp_arr[i] += temp_arr[i-1]
# Build the output array
output = [0]*len(arr)
for i in range(len(arr)-1, -1, -1):
index = (arr[i]/exp)
output[ temp_arr[ (index)%10 ] - 1] = arr[i]
temp_arr[ (index)%10 ] -= 1
# Copying the output array to arr[],
# so that arr now contains sorted numbers
for i in range(0,len(arr)):
arr[i] = output[i]
# Multiply exp by 10 to get next digit number
exp *= 10
原始資料= [2,1,5,7,4]
radixSort(原始資料)
排序後的資料 = 原始資料
print("排序後的資料為：", 排序後的資料)
排序後的資料為： [1, 2, 4, 5, 7]
```
## Bucket Sort
概念:
Bucket Sort是一種非比較型演算法，屬於排序演算法的一種。它將待排序的元素划分成不同的桶，按照一定的規則把對應的數據進行分組，在每個桶內利用某種快速排序進行排序後，再逐個桶合併，最後得到一個有序列表。
特點:
Bucket Sort 非常適合類似「已知取值范圍」的排序問題。它通過把值分布到不同桶中，比較簡單地完成排序。但它需要大量的預留空間和更多的計算時間，導致空間和時間複雜度增加。
空間複雜度: $O(n)$
時間複雜度:
- 最好情況: $O(n)$
- 最壞情況: $O(n^2)$
實作原理:
(1) 從數據集中取出最大/最小值，計算出取值範圍；
(2) 根據取值範圍，建立一個和取值符合的桶，比如$a$為最小值，$b$為最大值，創建一個包含 $(a,b)$ 為界的桶；
(3) 把每個元素分配到對應的桶中；
(4) 對每個不為空的桶內進行排序；
(5) 按照順序把各個桶中的元素合併起來；
Python實作示例:
```python=
#bucket sort for a list of numbers
def Bucket_Sort(arr):
#get the length/size of the array
n = len(arr)
#create an empty buckets
buckets = []
for i in range(n):
buckets.append([])
#iterate through the array, and add the elements to the respective lists
for j in arr:
index_b = int(n*j)
print(j, index_b)
buckets[index_b].append(j)
#sort the buckets
for i in range(n):
buckets[i] = sorted(buckets[i])
#append the sorted buckets
k = 0
for i in range(n):
for j in range(len(buckets[i])):
arr[k] = buckets[i][j]
k += 1
#sample list for testing
arr = [0.3, 0.2, 0.1, 0.4]
Bucket_Sort(arr)
print("Sorted array is:")
for i in range(len(arr)):
print(arr[i], end=" ")
#output:
Sorted array is:
0.1 0.2 0.3 0.4
```
## 插入排序
插入排序是一種簡單而有效的排序演算法。它的工作原理是：每次從待排序的序列中取出一個元素，然後把它插入到已經排好序的序列中，直到所有的元素都被插入完成。
插入排序的基本思想是：首先將第一個元素看作已經排好序的序列，然後從第二個元素開始，每次取出一個元素，然後把它插入到已經排好序的序列中。插入的過程中，需要比較新元素和已經排好序的序列中的元素，找到合適的插入位置。
下面是一個簡單的python實現：
```python=
def insertion_sort(arr):
for i in range(1, len(arr)):
temp = arr[i]
j = i
while j > 0 and arr[j - 1] > temp:
arr[j] = arr[j - 1]
j -= 1
arr[j] = temp
return arr
```
## Shell sort
Shell sort是一種比較高階的排序演算法，它是在插入排序的基礎上進行改進，得到的一種快速的排序方法。它的基本思想是：將待排序的序列進行分組，然後逐一進行插入排序。
一般來說，Shell sort的做法是將待排序的序列分成多個小的子序列，然後對這些子序列進行插入排序。分組的方式通常是按照一定的間隔進行分組，例如按照序列中相隔若干個元素的元素進行分組。每次插入排序完成後，都會將間隔減小，直到最後只剩一個子序列，這時再進行一次插入排序即可。
下面是一個簡單的python實現：
```python=
def shell_sort(arr):
# 計算出最大的間隔
gap = len(arr) // 2
while gap > 0:
# 間隔為gap的插入排序
for i in range(gap, len(arr)):
temp = arr[i]
j = i
while j >= gap and arr[j - gap] > temp:
arr[j] = arr[j - gap]
j -= gap
arr[j] = temp
gap //= 2
return arr
```
## Timsort
Timsort是一種比較高階的排序演算法，它是由Tim Peters在2002年發明的。Timsort是一種融合了插入排序和合併排序的演算法，它能夠從輸入序列中自動選擇最適合的排序方法，並且能夠高效地對序列進行排序。
Timsort的基本思想是：首先將輸入序列進行分組，每組的長度為一個有序的「塊」。然後對每個塊進行插入排序，得到若干個有序的塊。最後，對這些塊進行合併排序，得到最終的有序序列。
下面是一個簡單的python實現：
```python=
def timsort(arr):
# 將序列分為若干個塊
blocks = []
while len(arr) > 0:
block = []
for i in range(32):
if len(arr) == 0:
break
block.append(arr.pop(0))
block.sort()
blocks.append(block)
# 對塊進行合併排序
while len(blocks) > 1:
blocks = merge_blocks(blocks[0], blocks[1])
# 回傳排序結果
return blocks[0]
def merge_blocks(block1, block2):
# 合併兩個塊，並回傳合併後的塊
merged = []
while len(block1) > 0 and len(block2) > 0:
if block1[0] < block2[0]:
merged.append(block1.pop(0))
else:
merged.append(block2.pop(0))
while len(block1) > 0:
merged.append(block1.pop(0))
while len(block2) > 0:
merged.append(block2.pop(0))
return [merged]
```
Sign in with Wallet
Connect another wallet