---
# System prepended metadata

title: '[資演] 排序演算法'
tags: [資演]

---

# [資演] 排序演算法

###### 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）的特點。


![](https://hackmd.io/_uploads/SJN8YLjPs.png)


接下來是排序的步驟，此步驟會先將 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]

```