[Algorithm] Sorting 排序

Bubble Sort 泡沫排序 T: O(n ^ 2), S: O(1)

依序把最大的放到最後（如泡沫慢慢浮上水面）

1. [2, 3, 5, 4, 1]
2. [2, 3, 4, 1, 5]
3. [2, 3, 1, 4, 5]
4. [2, 1, 3, 4, 5]
5. [1, 2, 3, 4, 5]

def bubble_sort (arr):
  for i in range(len(arr)):
    for j in range(len(arr) - i - 1):
      if arr[j] > arr[j + 1]:
        arr[j], arr[j + 1] = arr[j + 1], arr[j]

Insertion Sort 插入排序 T: O(n ^ 2), S: O(1)

1. [2, 3, 5, 4, 1] ≡ 2 → [] = [2]
2. [2, 3, 5, 4, 1]≡ 3 → [2] = [2, 3]
3. [2, 3, 5, 4, 1]≡ 5 → [2, 3] = [2, 3, 5]
4. [2, 3, 5, 4, 1]≡ 4 → [2, 3, 5] = [2, 3, 4, 5]
   1. [2, 3, 5, 5, 1]
   2. [2, 3, 4, 5, 1]
5. [2, 3, 4, 5, 1]≡ 1 → [2, 3, 4, 5] = [1, 2, 3, 4, 5]
   1. [2, 3, 4, 5, 5]
   2. [2, 3, 4, 4, 5]
   3. [2, 3, 3, 4, 5]
   4. [2, 2, 3, 4, 5]
   5. [1, 2, 3, 4, 5]

def insertion_sort(arr):
  for i in range(len(arr)):
    key = arr[i]
    j = i - 1
    while j > 0 and arr[j] > key:
      arr[j + 1] = arr[j]
      j -= 1
    arr[j + 1] = key

Shell Sort 希爾排序

選擇 Gap sequences 為 (5, 3, 1) 為例

1. [13, 14, 94, 33, 82, 25, 59, 94, 65, 23, 45, 27, 73, 25, 39, 10]
2. 5 – Sorting：
   1. [[13, 14, 94, 33, 82],
       [25, 59, 94, 65, 23],
       [45, 27, 73, 25, 39],
       [10]]
   2. 分別對每行進行插入排序
      [[10, 14, 73, 25, 23],
       [13, 27, 94, 33, 39],
       [25, 59, 94, 65, 82],
       [45]]
3. 還原為一列：
   [10, 14, 73, 25, 23, 13, 27, 94, 33, 39, 25, 59, 94, 65, 82, 45]
4. 3 – Sorting
   1. [[10, 14, 73],
       [25, 23, 13],
       [27, 94, 33],
       [39, 25, 59],
       [94, 65, 82],
       [45]]
   2. [[10, 14, 13],
       [25, 23, 33],
       [27, 25, 59],
       [39, 65, 73],
       [45, 94, 82],
       [94]]
5. 還原為一列：
   [10, 14, 13, 25, 23, 33, 27, 25, 59 ,39, 65, 73, 45, 94, 82, 94]
6. 1 – Sorting（會比原始資料更容易做插入排序）：
   [10, 13, 14, 23, 25, 25, 27, 33, 39, 45, 59, 65, 73, 82, 94, 94]

Gap sequences 步長序列

Selection Sort 選擇排序 T: O(n ^ 2), S: O(n)

1. [2, 3, 5, 4, 1] → [1, 3, 5, 4, 2]
2. [1, 3, 5, 4, 2] → [1, 2, 5, 4, 3]
3. [1, 2, 5, 4, 3] → [1, 2, 3, 4, 5]
4. [1, 2, 3, 4, 5]
5. [1, 2, 3, 4, 5]

def selection_sort(arr):
  for i in range(len(arr) - 1):
    min_i = i
    for j in range(i + 1, range(len(arr)):
      if arr[j] < arr[min_i]:
        min_i = j
    if min_i != i:
      arr[i], arr[min_i] = arr[min_i], arr[i]

Quick Sort 快速排序 T: O(n * log(n)) ~ O(n ^ 2)

使用二分法 (binary method / divide and conquer)

1. [5, 9, 6, 1, 3, 8, 4, 7, 2] → pivot: 5
   → less: [1, 3, 4, 2], greater: [9, 6, 8, 7]
   → quick_sort([1, 3, 4, 2]) + [5] + quick_sort([9, 6, 8, 7])
2. → (quick_sort([]) + [1] + quick_sort([3, 4, 2])) + [5] + (quick_sort([6, 8, 7]) + [9] + quick_sort([]))
3. → ([1] + (quick_sort([2]) + [3] + quick_sort([4]))) + [5] + ((quick_sort([]) + [6] + quick_sort([8, 7])) + [9])
4. → ([1] + (([2]) + [3] + ([4]))) + [5] + (([6] + (quick_sort([]) + [7] + quick_sort([8])) + [9])
5. → ([1] + (([2]) + [3] + ([4]))) + [5] + (([6] + ([7] + [8])) + [9])
6. → [1, 2, 3, 4, 5, 6, 7, 8, 9]

Time Complexity:
Average Case: O(n * log(n))
Worst Case: O(n ^ 2)
Space Complexity: Ω(n)

def quick_sort (arr):
  if len(arr) <= 1: return array

  pivot = arr[0] # select a pivot
  less, greater = [], []
  for n in arr[1:]:
    if n <pivot:
      less.append(n)
    else:
      greater.append(n)

  return quick_sort(less) + [pivot] + quick_sort(greater)

In-plase Version, S: O(1)

1. [5, 9, 6, 1, 4, 7, 3, 8, 2]
2. [5, 9, 6, 1, 4, 7, 3, 8, 2]
3. [5, 9, 6, 1, 4, 7, 3, 8, 2]
4. [5, 1, 6, 9, 4, 7, 3, 8, 2]
5. [5, 1, 4, 9, 6, 7, 3, 8, 2]
6. [5, 1, 4, 9, 6, 7, 3, 8, 2]
7. [5, 1, 4, 3, 6, 7, 9, 8, 2]
8. [5, 1, 4, 3, 6, 7, 9, 8, 2]
9. [5, 1, 4, 3, 2, 7, 9, 8, 6]

Time Complexity:
Average Case: O(n * log(n))
Worst Case: O(n ^ 2)
Space Complexity: O(1)

def quick_sort (arr):
  if len(arr) <= 1: return array

  pivot = arr[0] # select a pivot
  greater_start = 1
  for i, n in enumerate(array[1:]):
    if n < pivot:
      arr[i], arr[greater_start] = arr[greater_start], arr[i]
      greater_start += 1

  return quick_sort(arr[1:greater_start]) + [pivot] + quick_sort(arr[greater_start:])

Merge Sort 合併排序 T: Θ(n * log(n)), S: Θ(n)

def merge_sort(array):
  if len(array) < 2: return array

  mid = (len(array) + 1) // 2

  left  = merge_sort(array[:mid])
  right = merge_sort(array[mid:])

  ret = []
  i = j = 0
  while i < len(left) or j < len(right):
    if i == len(left) or \
         (i < len(left) and j < len(right) and left[i] > right[j]):
      ret.append(right[j])
      j += 1
    else:
      ret.append(left[i])
      i += 1
  return ret

相關例題

• Leetcode # 1051. Height Checker

Heap Sort

參照 Heap 堆積

Last Updated on 2024/06/10 by A1go