線性排序法

線性排序（Linear sort），指的是時間複雜度為O(n)的排序演算法，之所以時間複雜度能達到線性，是因為這種排序非基於比較的，但它的適用場景也有很大的限制。
線性排序法有三種：
桶排序(Bucket Sort)、計數排序(Counting Sort)、基數排序(Radix Sort)。

• 時間複雜度

• 筆記來源：
  • https://juejin.cn/post/6844903847664549895
  • https://byvoid.com/zht/blog/sort-radix/

桶排序（Bucket Sort）

桶排序適用於數據範圍較集中且分佈均勻的情況，將數據分到若干個「桶」裡，然後對每個桶內的數據進行排序，最後將每個桶內的數據合併起來。
學習影片： https://www.youtube.com/watch?v=8uMEZ7aKICI

步驟：

1. 初始化若干個空桶。
2. 將數據依據某個規則分配到不同的桶中。
3. 對每個桶內的數據進行排序（可以使用其他排序算法，如插入排序或快速排序）。
4. 將所有桶的數據合併，得到最終的排序數列。

def bucket_sort(arr):
    # 創建桶
    bucket_count = len(arr)
    buckets = [[] for _ in range(bucket_count)]

    # 將元素分配到相應的桶
    for num in arr:
        index = int(bucket_count * num)  # 假設數據在[0,1)之間
        buckets[index].append(num)

    # 對每個桶進行排序
    for bucket in buckets:
        bucket.sort()

    # 合併所有桶中的數據
    sorted_arr = []
    for bucket in buckets:
        sorted_arr.extend(bucket)

    return sorted_arr

• 桶排序優點：
  • 適合數據範圍固定且分佈均勻的情況，能達到近乎線性時間複雜度 𝑂(𝑛)。
  • 可以使用穩定的內部排序，使其成為穩定排序算法。
  • 易於並行處理，每個桶可以獨立排序。
• 限制：
  • 不適合數據範圍過大或分佈不均的情況，否則性能會下降。
  • 需要事先知道數據範圍，且可能會浪費額外空間。
• 不太重要重點學習計數排序與基數排序

計數排序（Counting Sort）

計數排序是一種基於數字頻率的排序方法，適用於整數範圍較小的數據。它通過計算每個元素出現的次數來排序數列。
學習影片： https://www.youtube.com/watch?v=uHHKQBIfUOU

步驟：

1. 找到數列中的最大和最小值。
2. 建立一個計數陣列，根據每個數字的頻率來計數。
3. 根據計數陣列中的數據生成最終的排序數列。

def counting_sort(arr):
    # 找到最大和最小值
    max_val = max(arr)
    min_val = min(arr)

    # 初始化計數陣列
    count_range = max_val - min_val + 1
    count = [0] * count_range

    # 計算每個元素的出現次數
    for num in arr:
        count[num - min_val] += 1

    # 生成排序後的數列
    sorted_arr = []
    for i in range(count_range):
        sorted_arr.extend([i + min_val] * count[i])

    return sorted_arr

• 計數排序優點：
  • 適合範圍小且數量大的整數數據，時間複雜度為 𝑂(𝑛+𝑘)，效率高於比較排序。
  • 是穩定排序，保留相同元素的相對順序。
  • 不需要比較元素，通過計算出現次數實現排序。
• 限制：
  • 當數據範圍 𝑘 過大時，會消耗大量空間，導致效率下降。
  • 僅適用於離散型整數數據，不能處理浮點數或字符串。

基數排序（Radix Sort）

基數排序適用於處理數字（如整數或浮點數）和字符串的排序。它將數字的每一位（如個位、十位等）分別進行排序，從最低位到最高位逐步排序。
學習影片： https://www.youtube.com/watch?v=TYmQNCwRxeI

步驟：

1. 從最低位開始，對每一位使用穩定排序（如計數排序）。
2. 對每個數字的每一位依次進行排序，直到最高位。

def counting_sort_for_radix(arr, exp):
    n = len(arr)
    output = [0] * n
    count = [0] * 10

    # 計算每位數的出現次數
    for i in range(n):
        index = (arr[i] // exp) % 10
        count[index] += 1

    # 修改計數陣列，使其變成位置陣列
    for i in range(1, 10):
        count[i] += count[i - 1]

    # 構建輸出數組
    for i in range(n - 1, -1, -1):
        index = (arr[i] // exp) % 10
        output[count[index] - 1] = arr[i]
        count[index] -= 1

    # 將排序結果存回原數組
    for i in range(n):
        arr[i] = output[i]

def radix_sort(arr):
    max_val = max(arr)

    # 對每個數位進行計數排序
    exp = 1
    while max_val // exp > 0:
        counting_sort_for_radix(arr, exp)
        exp *= 10

• 基數排序優點：
  • 適合處理長度固定的多位數字，如整數和字符串，時間複雜度為 𝑂(𝑑⋅(𝑛+𝑘))
  • 不進行數據比較，效率高於比較排序，且是穩定排序。
  • 當數據位數 𝑑 固定時，能接近線性時間。
• 限制：
  • 只適合整數或字符串，且當數據位數 𝑑 或基數 𝑘 增大時，效率下降。
  • 需要額外空間存儲中間結果。

1365. How Many Numbers Are Smaller Than the Current Number

題目描述：
給定一個數組 nums，對於其中的每個元素 nums[i]，計算有多少個數小於 nums[i]。換言之，對於每一個 nums[i]，都要數一下有多少個數小於它，返回答案數組。

這道題目是請ChatGPT出的，雖然通常用比較排序來解決，但可以用計數排序來實現，讓時間複雜度能達到𝑂(𝑛)。

class Solution(object):
    def smallerNumbersThanCurrent(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        count = [0] * 101

        for num in nums:
            count[num] += 1

        for i in range(1, 101):
            count[i] += count[i - 1]

        result = []
        for num in nums:
            if num == 0:
                result.append(0)
            else:
                result.append(count[num - 1])
        return result

程式步驟：

1. 計數數組初始化：創建一個大小為 101 的計數數組 count，因為數字範圍是 [0, 100]。
2. 統計每個數字的出現次數：遍歷 nums，增加相應數字在 count 中的位置。
3. 累積計數：計算有多少數字小於當前數字，並累加到 count 陣列中。
4. 生成結果：遍歷原數列，根據累積計數來構建結果。