排序演算法

習題預習

1. 什麼是Sorting Algorithms？

2. Sorting Algorithms的時間複雜度計算方式是什麼？

3. 哪些Sorting Algorithms可以實現穩定排序？

4. Sorting Algorithms在什麼情況下可能會導致排序失敗？

5. 什麼是「in-place sorting」？那些Sorting Algorithms可以實現in-place sorting？

說明知識

排序算法是計算機科學中處理數據的常用算法之一，它可以將一組數據按照順序排列。常用的排序算法包括冒泡排序、插入排序、選擇排序、快速排序、合併排序、堆排序等。

下面舉例來說明不同的排序算法：

1. 冒泡排序（Bubble Sort）：從序列的開始位置開始比較相鄰的兩個數，如果前一個數比後一個數大，則交換兩個數的位置，一直比較到序列的最後一位，再從頭開始重複以上步驟，直至整個序列有序。

例如，對於以下數列進行冒泡排序：[5, 2, 8, 6, 3, 9, 1]

第一輪排序：[2, 5, 6, 3, 8, 1, 9]
第二輪排序：[2, 5, 3, 6, 1, 8, 9]
第三輪排序：[2, 3, 5, 1, 6, 8, 9]
第四輪排序：[2, 3, 1, 5, 6, 8, 9]
第五輪排序：[2, 1, 3, 5, 6, 8, 9]
第六輪排序：[1, 2, 3, 5, 6, 8, 9]

2. 插入排序（Insertion Sort）：從未排序的數列中，按照順序遍歷每一個元素，將每一個元素插入到已排序的序列中，直到所有元素都插入完成。

例如，對於以下數列進行插入排序：[5, 2, 8, 6, 3, 9, 1]

第一輪排序：[2, 5, 8, 6, 3, 9, 1]
第二輪排序：[2, 5, 8, 6, 3, 9, 1]
第三輪排序：[2, 5, 6, 8, 3, 9, 1]
第四輪排序：[2, 3, 5, 6, 8, 9, 1]
第五輪排序：[1, 2, 3, 5, 6, 8, 9]

3. 選擇排序（Selection Sort）：從未排序的數列中，每一次找到未排序部分的最小值，將其排到已排序部分的末尾。

例如，對於以下數列進行選擇排序：[5, 2, 8, 6, 3, 9, 1]

第一輪排序：[1, 2, 8, 6, 3, 9, 5]
第二輪排序：[1, 2, 3, 6, 8, 9, 5]
第三輪排序：[1, 2, 3, 5, 8, 9, 6]
第四輪排序：[1, 2, 3, 5, 6, 9, 8]
第五輪排序：[1, 2, 3, 5, 6, 8, 9]

4. 快速排序（Quick Sort）：通過將一個數列劃分為較小和較大的兩部分，不斷對較小部分和較大部分重複上述步驟，直到所有元素都有序。

例如，對於以下數列進行快速排序：[5, 2, 8, 6, 3, 9, 1]

第一輪排序：[1, 2, 3, 5, 8, 9, 6]
第二輪排序：[1, 2, 3, 5, 6, 8, 9]

5. 合併排序（Merge Sort）：將一個數列劃分成兩個子數列，對每個子數列進行排序，然後將兩個子數列合併成一個有序數列。

例如，對於以下數列進行合併排序：[5, 2, 8, 6, 3, 9, 1]

第一輪排序：[2, 5, 8, 6, 1, 3, 9]
第二輪排序：[1, 2, 3, 5, 6, 8, 9]

彙總重點

1. Bubble Sort: 透過不斷比較相鄰的元素，將最大值或最小值移到數列的最後面或最前面。
2. Quick Sort: 以一個基準值為標準分成左右兩部分，將小於基準值的數值移到左邊，大於基準值的數值移到右邊，再以同樣的方式處理左右兩個區間，遞迴進行直到整個數列有序。
3. Merge Sort: 將數列分成若干個子序列進行排序，再將這些子序列合併成一個大序列進行排序。
4. Insertion Sort: 逐一取出元素並按照適當的順序插入已排好序的數列中。
5. Selection Sort: 依次找出數列中最小的元素，放到數列起始位置，再從剩下的元素中找到最小值，將其放到已排序部分的結尾，直到整個數列有序。
6. Shell Sort: 基於插入排序的一種算法，會先進行一次分組排序，然後逐漸縮小分組區間，最終當區間縮小成1時，整個數列也就有序了。
7. Heap Sort: 利用二叉堆進行排序，先將數列變成一個最小堆或最大堆，然後將堆頂元素取出加入結果集，再把剩餘堆調整成新的堆，重複以上步驟直到整個數列有序。
8. Counting Sort: 用於小範圍整數排序，其核心理念在於將輸入的數據值轉化為鍵存儲在額外開闢的數組空間中，然後依次把計數大於 1 的填回原數組。

以上就是Sorting Algorithms的重點，各算法在時間複雜度和空間複雜度等方面都有不同優點和限制，需要根據應用場景選擇適合的算法來進行排序。

知識測驗

1. 如何實現QuickSort的In-Place版本？
   答案：由於QuickSort是將一個數列切割成較小和較大的元素，因此可以使用一個指針來追踪分割元素的位置，將小於分割元素的元素放在左側，大於分割元素的元素放在右側。請參考以下代碼：

def quickSortInPlace(arr, low, high):
    if low < high:
        pivot = partition(arr, low, high)
        quickSortInPlace(arr, low, pivot - 1)
        quickSortInPlace(arr, pivot + 1, high)
 
def partition(arr, low, high):
    pivot_value = arr[high]
    i = low - 1
    for j in range(low, high):
        if arr[j] <= pivot_value:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

2. 如何使用MergeSort來對超過1TB的大型數據進行排序？
   答案：將數據分成小的塊，分別使用MergeSort進行排序，然後依次合併這些已排序的塊，直到所有數據都被排序。這種方法稱為外部排序（external sorting）。例如，可以將數據分成100GB的塊，排序每個塊，然後使用儲存器並行合併這些已排序的塊。

3. 如何實現HeapSort算法？
   答案：HeapSort使用最大堆（Max Heap）來實現排序的過程。首先將數據構建成最大堆，然後依次取出堆頂元素（最大元素），放到數列最後，再進行最大堆重建操作。請參考以下代碼：

def heapSort(arr):
    n = len(arr)
    for i in range(n//2 - 1, -1, -1):
        heapify(arr, n, i)
    for i in range(n-1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]
        heapify(arr, i, 0)
 
def heapify(arr, n, i):
    largest = i
    l = 2*i + 1
    r = 2*i + 2
    if l < n and arr[l] > arr[largest]:
        largest = l
    if r < n and arr[r] > arr[largest]:
        largest = r
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

4. 如何在O(n)時間複雜度下找到數列中第k小的元素？
   答案：可以使用QuickSelect算法，類似於QuickSort的思想，只需繼續對分割後的一個子數列進行遞迴，直到找到第k小的元素。平均時間複雜度為 O(n)。以下是Python示例代碼：

import random
 
def quickSelect(arr, left, right, k):
    if left == right:
        return arr[left]
    pivotIndex = random.randint(left, right)
    pivotIndex = partition(arr, left, right, pivotIndex)
    if k == pivotIndex:
        return arr[k]
    elif k < pivotIndex:
        return quickSelect(arr, left, pivotIndex - 1, k)
    else:
        return quickSelect(arr, pivotIndex + 1, right, k)
 
def partition(arr, left, right, pivotIndex):
    pivotValue = arr[pivotIndex]
    arr[pivotIndex], arr[right] = arr[right], arr[pivotIndex]
    storeIndex = left
    for i in range(left, right):
        if arr[i] < pivotValue:
            arr[i], arr[storeIndex] =  arr[storeIndex], arr[i]
            storeIndex += 1
    arr[storeIndex], arr[right] = arr[right], arr[storeIndex]
    return storeIndex

5. 如何使用BubbleSort來對鏈表進行排序？
   答案：在鏈表上進行交換操作較為困難，因此可以使用一個標誌來標記最後一個已排序節點的位置，然後將下一個節點與其比較，如果需要排序則進行交換，直到標誌移動到鏈表末尾為止。以下是示例代碼：

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
 
def bubbleSortList(head):
    if not head:
        return None
    flag = True
    while flag:
        flag = False
        curr = head
        while curr.next:
            if curr.val > curr.next.val:
                curr.val, curr.next.val = curr.next.val, curr.val
                flag = True
            curr = curr.next
    return head

以上所有代碼均為Python 3.6+。