Python常用排序算法

1. 冒泡排序

冒泡排序是一種簡單的排序算法，它重復地遍歷要排序的列表，比較相鄰的元素，如果他們的順序錯誤就交換他們。

def bubble_sort(arr):# 遍歷所有數組元素for i in range(len(arr)):# 最后i個元素是已經排序好的for j in range(0, len(arr)-i-1):# 如果當前元素大于下一個元素，則交換位置if arr[j] > arr[j+1]:arr[j], arr[j+1] = arr[j+1], arr[j]return arrarr = [11, 32, 21, 67, 54, 19]
sorted_arr = bubble_sort(arr)
print("排序后為:", sorted_arr)

輸出結果：
排序后為: [11, 19, 21, 32, 54, 67]

復雜度分析

時間復雜度：

最壞情況：O(n²)（完全逆序）
最好情況：O(n)
平均情況：O(n²)

空間復雜度：O(1)（原地排序）

2. 選擇排序

選擇排序是一種簡單直觀的排序算法，它的工作原理是每次從待排序的數據元素中選出最小（或最大）的一個元素，存放在序列的起始位置，直到全部待排序的數據元素排序完畢。

def select_sort(arr):# 遍歷所有數組元素for i in range(len(arr)):# 找到剩余未排序部分的最小元素索引min_index = ifor j in range(i+1, len(arr)):if arr[j] < arr[min_index]:min_index = j# 將找到的最小元素與第i個位置的元素交換arr[i], arr[min_index] =  arr[min_index], arr[i]return arrarr = [11, 32, 21, 67, 54, 19]
sorted_arr = select_sort(arr)
print("排序后為:", sorted_arr)

輸出結果：
排序后為: [11, 19, 21, 32, 54, 67]

復雜度分析

時間復雜度：O(n²)
空間復雜度：O(1)（原地排序）

3. 插入排序

插入排序是一種簡單直觀的排序算法，它的工作原理是通過構建有序序列，在已排序序列中從后向前掃描，找到相應位置并插入。

def insert_sort(arr):# 遍歷從1到倒數第二個元素for i in range(1, len(arr)):# 當前需要插入的元素key = arr[i]# 已排序部分的最后一個元素索引j = i - 1# 將arr[i]與已排序部分的元素逐個比較，如果比key大則后移一位while j >= 0 and key < arr[j]:arr[j + 1] = arr[j]j -= 1# 找到合適位置，插入keyarr[j + 1] = keyreturn arrarr = [11, 32, 21, 67, 54, 19]
sorted_arr = insert_sort(arr)
print("排序后為:", sorted_arr)

輸出結果：
排序后為: [11, 19, 21, 32, 54, 67]

復雜度分析

時間復雜度：

最壞情況：O(n²)（當數組是逆序時）
最好情況：O(n)（當數組已經有序時）
平均情況：O(n²)

空間復雜度：O(1)（原地排序）

4. 快速排序

快速排序是一種高效的排序算法，采用分治法策略。首先任意選取一個元素作為基準數據，將待排序列表中的數據分割成獨立的兩部分，比基準數據小的放在它左邊，比基準數據大的放在它右邊，此時第一輪數據排序完成。然后再按照此方法對兩邊的數據分別進行分割，直至被分割的數據只有一個或者零個時，遞歸結束。

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)arr = [11, 32, 21, 67, 54, 19]
sorted_arr = quick_sort(arr)
print("排序后為:", sorted_arr)

輸出結果：
排序后為: [11, 19, 21, 32, 54, 67]

復雜度分析

時間復雜度：

最壞情況：O(n²)（當分區極度不平衡時）
最好情況：O(n log n)
平均情況：O(n log n)

空間復雜度：O(n)（創建了新的列表）

5. 歸并排序

歸并排序是一種基于分治策略的高效排序算法，將數組不斷地分成兩半，然后遞歸地對兩半進行排序，最后將排序好的兩半合并在一起。

def merge_sort(arr):if len(arr) <= 1:return arr# 分割階段mid = len(arr) // 2left = merge_sort(arr[:mid])right = merge_sort(arr[mid:])# 合并階段return merge(left, right)def merge(left, right):"""合并兩個已排序的列表"""result = []i = j = 0while i < len(left) and j < len(right):if left[i] < right[j]:result.append(left[i])i += 1else:result.append(right[j])j += 1# 添加剩余元素result.extend(left[i:])result.extend(right[j:])return resultarr = [38, 27, 43, 3, 9, 82, 10]
sorted_arr = merge_sort(arr)
print("排序后為:", sorted_arr)

輸出結果：
排序后為: [3, 9, 10, 27, 38, 43, 82]

復雜度分析

時間復雜度：O(n log n)
空間復雜度: O(n)（需要額外空間存儲臨時數組）

6. 堆排序

堆排序是一種基于二叉堆數據結構的高效排序算法。堆是一種特殊的完全二叉樹，其中每個父節點的值都大于或等于其子節點的值（稱為最大堆）或每個父節點的值都小于或等于其子節點的值（稱為最小堆）。

import heapqdef heap_sort(arr):# 構建最小堆heapq.heapify(arr)return [heapq.heappop(arr) for _ in range(len(arr))]arr = [12, 11, 15, 3, 21, 9]
sorted_arr = heap_sort(arr)
print("排序后為:", sorted_arr)

輸出結果：
排序后為: [3, 9, 11, 12, 15, 21]

復雜度分析

時間復雜度:

建堆過程：O(n)
每次堆化：O(log n)
總體時間復雜度：O(n log n)

空間復雜度: O(1)（原地排序）

7. 計數排序

計數排序是一種非比較排序算法，適用于對一定范圍內的整數進行排序。它統計數組中每個元素出現的次數，然后根據統計結果將元素放回正確的位置。

def count_sort(arr):if len(arr) == 0:return arr# 找到數組中的最大值和最小值max_val = max(arr)min_val = min(arr)# 創建計數數組，初始化為0count = [0] * (max_val - min_val + 1)# 統計每個元素出現的次數for num in arr:count[num - min_val] += 1# 重建排序后的數組sorted_arr = []for i in range(len(count)):sorted_arr.extend([i + min_val] * count[i])return sorted_arrarr = [4, 2, 5, 1, 8]
sorted_arr = count_sort(arr)
print("排序后為：", sorted_arr)

輸出結果：
排序后為： [1, 2, 4, 5, 8]

復雜度分析

時間復雜度：O(n+k)，其中n是元素數量，k是數據范圍
空間復雜度：O(n+k)

8. 基數排序

基數排序是一種非比較型整數排序算法，它通過將整數按位切割成不同的數字，然后按每個位數分別比較排序。基數排序可以采用最低位優先（LSD）或最高位優先（MSD）兩種方式。

def radix_sort(arr):# 找到數組中的最大數，確定排序的輪數max_num = max(arr)# 從個位開始exp = 1while max_num // exp > 0:counting_sort_by_digit(arr, exp)exp *= 10return arrdef counting_sort_by_digit(arr, exp):n = len(arr)output = [0] * ncount = [0] * 10# 統計當前位數的數字出現次數for num in arr:digit = (num // exp) % 10count[digit] += 1# 計算累加計數for i in range(1, 10):count[i] += count[i-1]# 反向填充輸出數組（保證穩定性）for i in range(n-1, -1, -1):digit = (arr[i] // exp) % 10output[count[digit] - 1] = arr[i]count[digit] -= 1# 將排序結果復制回原數組for i in range(n):arr[i] = output[i]arr = [170, 45, 75, 90, 802, 24, 2, 66]
sorted_arr = radix_sort(arr)
print("排序后為:", sorted_arr)

輸出結果：
排序后為: [2, 24, 45, 66, 75, 90, 170, 802]

復雜度分析

時間復雜度：O(d*(n+k))，其中d是最大數字的位數，n是元素數量，k是基數
空間復雜度：O(n+k)

9. 桶排序

桶排序是一種分布式排序算法，它將元素分到有限數量的桶里，每個桶再分別排序。

def bucket_sort(arr, bucket_size=5):if len(arr) == 0:return arr# 找到最大值和最小值max_val = max(arr)min_val = min(arr)# 計算桶的數量bucket_count = (max_val - min_val) // bucket_size + 1buckets = [[] for _ in range(bucket_count)]# 將元素分配到各個桶中for num in arr:index = (num - min_val) // bucket_sizebuckets[index].append(num)# 對每個桶進行排序sorted_arr = []for bucket in buckets:# 使用內置的sorted函數sorted_arr.extend(sorted(bucket))return sorted_arrarr = [29 ,25, 13, 21, 8, 43]
sorted_arr = bucket_sort(arr)
print("排序后為:", sorted_arr)

輸出結果：
排序后為: [8, 13, 21, 25, 29, 43]

復雜度分析

時間復雜度：

平均情況：O(n+k)，其中k是桶的數量
最壞情況：O(n²)（當所有元素都分配到同一個桶中）

空間復雜度：O(n+k)

10. 希爾排序

希爾排序是插入排序的一種高效改進版本，也稱為縮小增量排序。它通過將原始列表分割成多個子列表來進行插入排序，隨著算法的進行，子列表的長度逐漸增大，最終整個列表變為一個子列表完成排序。

def shell_sort(arr):n = len(arr)# 初始間隔（gap）設置為數組長度的一半gap = n // 2while gap > 0:# 對各個間隔分組進行插入排序for i in range(gap, n):temp = arr[i]j = i# 對子列表進行插入排序while j >= gap and arr[j - gap] > temp:arr[j] = arr[j - gap]j -= gaparr[j] = temp# 縮小間隔gap = gap // 2return arrarr = [9 , 8, 3, 6, 5, 7, 1]
sorted_arr = shell_sort(arr)
print("排序后為:", sorted_arr)

輸出結果：
排序后為: [1, 3, 5, 6, 7, 8, 9]

復雜度分析

時間復雜度：

平均情況：O(n^1.3)到O(n^1.5)
最壞情況：O(n*n)
最好情況：O(n log n)

空間復雜度：O(1)（原地排序）

11. 拓撲排序

拓撲排序是針對有向無環圖的線性排序算法，使得對于圖中的每一條有向邊（u, v）,u在排序中總是位于v的前面。

from collections import dequedef topo_sort_kahn(graph):# 計算所有節點的入度in_degree = {node: 0 for node in graph}for node in graph:for neighbor in graph[node]:in_degree[neighbor] += 1# 初始化隊列，將所有入度為0的節點加入隊列queue = deque([node for node in graph if in_degree[node] == 0])topo_order = []while queue:current = queue.popleft()topo_order.append(current)# 減少所有鄰居的入度for neighbor in graph[current]:in_degree[neighbor] -= 1# 如果鄰居的入度變為0，加入隊列if in_degree[neighbor] == 0:queue.append(neighbor)# 檢查是否所有節點都被排序（無環）if len(topo_order) == len(graph):return topo_orderelse:return []  # 圖中存在環，無法進行拓撲排序
# 定義有向無環圖（鄰接表表示）
graph = {'A': ['B', 'C'],'B': ['D', 'E'],'C': ['F'],'D': [],'E': ['F'],'F': []
}print("Kahn算法拓撲排序結果:", topo_sort_kahn(graph))