二元搜索樹

Quick Sort（快速排序）

Quick Sort 是一種分治法的排序演算法。它的核心思想是選取一個基準值（pivot），將數列分成兩部分，左邊的數比基準值小，右邊的數比基準值大，然後遞歸地對兩部分進行同樣的操作。
學習影片:https://www.youtube.com/watch?v=DVDoyB5qDC4&t=32s

• 步驟：

1. 選取基準值（pivot）。
2. 將數列分割成兩個子序列，左邊比基準值小，右邊比基準值大。
3. 對這兩個子序列遞歸應用 Quick Sort。
4. 將結果合併。

• 時間複雜度：平均情況下為 O(n log n)，最壞情況下為 O(n²)（當每次選取的基準值總是數列中最大或最小的數時）。

def quick_sort(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 quick_sort(left) + middle + quick_sort(right)

Merge Sort（合併排序）

Merge Sort 也是一種分治法的排序演算法。它將數列遞歸地分割成兩個子數列，直到每個子數列只包含一個元素，然後再將這些子數列合併回來。
學習影片:https://www.youtube.com/watch?v=C9Xes8wH6Co

• 步驟：

1. 將數列分成兩個部分。
2. 遞歸地對兩個子數列進行排序。
3. 合併兩個已排序的子數列。

• 時間複雜度：O(n log n)，穩定且不依賴基準值。

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

Tree Sort（樹排序）

Tree Sort 是一種基於二元搜索樹（BST）進行排序的演算法。首先將數列中的元素一個一個插入到二元搜索樹中，然後進行中序遍歷，從而得到一個有序數列。

學習影片:https://www.youtube.com/watch?v=n2MLjGeK7qA

• 步驟：

1. 建立一個空的二元搜索樹。
2. 將數列中的每個元素插入到二元搜索樹中。
3. 對樹進行中序遍歷，將結果存入列表中。

• 時間複雜度：O(n log n)，但在最壞情況下為 O(n²)（當樹的高度不平衡時，會退化成鏈表）。

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def insert(root, val):
    if root is None:
        return TreeNode(val)
    if val < root.val:
        root.left = insert(root.left, val)
    else:
        root.right = insert(root.right, val)
    return root

def inorder_traversal(root, result):
    if root:
        inorder_traversal(root.left, result)
        result.append(root.val)
        inorder_traversal(root.right, result)

def tree_sort(arr):
    if len(arr) == 0:
        return []
    root = None
    for val in arr:
        root = insert(root, val)
    result = []
    inorder_traversal(root, result)
    return result

比較

• Quick Sort 是最快速的排序演算法之一，特別適合隨機數列的排序，但最壞情況下表現不佳。
• Merge Sort 時間複雜度穩定，但需要額外的空間進行合併操作。
• Tree Sort 結合了樹結構的優點，但在處理不平衡的數列時可能會退化。