一、排序的基本概念

排序是計算機科學中一項重要的操作，它將一組數據元素按照特定的順序（如升序或降序）重新排列。排序算法的性能通常通過時間復雜度和空間復雜度來衡量。在 Python 中，有內置的排序函數，同時也可以手動實現各種排序算法。

二、Python 內置排序函數

1.?sorted()?函數

sorted()?函數可以對任何可迭代對象進行排序，并返回一個新的已排序列表，原對象不會被修改。

python

# 對列表進行排序
numbers = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
sorted_numbers = sorted(numbers)
print("使用 sorted() 排序后的列表:", sorted_numbers)# 對字符串進行排序
string = "python"
sorted_string = ''.join(sorted(string))
print("對字符串排序后的結果:", sorted_string)# 對字典按鍵排序
dictionary = {'c': 3, 'a': 1, 'b': 2}
sorted_dict_keys = sorted(dictionary.keys())
print("對字典按鍵排序后的結果:", sorted_dict_keys)

2.?list.sort()?方法

list.sort()?方法是列表對象的一個方法，它會直接對原列表進行排序，不返回新的列表。

python

numbers = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
numbers.sort()
print("使用 list.sort() 排序后的列表:", numbers)

3. 自定義排序規則

sorted()?和?list.sort()?都可以接受一個?key?參數，用于指定排序的規則。

python

# 按字符串長度排序
words = ["apple", "banana", "cherry", "date"]
sorted_words = sorted(words, key=len)
print("按字符串長度排序后的列表:", sorted_words)# 按自定義函數排序
students = [{"name": "Alice", "age": 20},{"name": "Bob", "age": 18},{"name": "Charlie", "age": 22}
]
sorted_students = sorted(students, key=lambda x: x["age"])
print("按年齡排序后的學生列表:", sorted_students)

三、常見排序算法的 Python 實現

1. 冒泡排序（Bubble Sort）

冒泡排序是一種簡單的排序算法，它重復地走訪過要排序的數列，一次比較兩個元素，如果它們的順序錯誤就把它們交換過來。

python

def bubble_sort(arr):n = len(arr)for i in range(n):for j in range(0, n - i - 1):if arr[j] > arr[j + 1]:arr[j], arr[j + 1] = arr[j + 1], arr[j]return arrnumbers = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
sorted_numbers = bubble_sort(numbers)
print("冒泡排序后的列表:", sorted_numbers)

2. 選擇排序（Selection Sort）

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

python

def selection_sort(arr):n = len(arr)for i in range(n):min_idx = ifor j in range(i + 1, n):if arr[j] < arr[min_idx]:min_idx = jarr[i], arr[min_idx] = arr[min_idx], arr[i]return arrnumbers = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
sorted_numbers = selection_sort(numbers)
print("選擇排序后的列表:", sorted_numbers)

3. 插入排序（Insertion Sort）

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

python

def insertion_sort(arr):for i in range(1, len(arr)):key = arr[i]j = i - 1while j >= 0 and key < arr[j]:arr[j + 1] = arr[j]j -= 1arr[j + 1] = keyreturn arrnumbers = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
sorted_numbers = insertion_sort(numbers)
print("插入排序后的列表:", sorted_numbers)

4. 快速排序（Quick Sort）

快速排序是一種分治的排序算法。它選擇一個基準值，將數組分為兩部分，小于基準值的元素放在左邊，大于基準值的元素放在右邊，然后遞歸地對左右兩部分進行排序。

python

def quick_sort(arr):if len(arr) <= 1:return arrelse:pivot = arr[0]left = [x for x in arr[1:] if x <= pivot]right = [x for x in arr[1:] if x > pivot]return quick_sort(left) + [pivot] + quick_sort(right)numbers = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
sorted_numbers = quick_sort(numbers)
print("快速排序后的列表:", sorted_numbers)

5. 歸并排序（Merge Sort）

歸并排序是一種分治算法，它將一個數組分成兩個子數組，分別對這兩個子數組進行排序，然后將排好序的子數組合并成一個最終的有序數組。

python

def merge_sort(arr):if len(arr) <= 1:return arrmid = 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 += 1result.extend(left[i:])result.extend(right[j:])return resultnumbers = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
sorted_numbers = merge_sort(numbers)
print("歸并排序后的列表:", sorted_numbers)

四、排序算法復雜度分析

排序算法	平均時間復雜度	最壞時間復雜度	最好時間復雜度	空間復雜度	穩定性
冒泡排序	\(O(n^2)\)	\(O(n^2)\)	\(O(n)\)	\(O(1)\)	穩定
選擇排序	\(O(n^2)\)	\(O(n^2)\)	\(O(n^2)\)	\(O(1)\)	不穩定
插入排序	\(O(n^2)\)	\(O(n^2)\)	\(O(n)\)	\(O(1)\)	穩定
快速排序	\(O(n log n)\)	\(O(n^2)\)	\(O(n log n)\)	\(O(log n)\)	不穩定
歸并排序	\(O(n log n)\)	\(O(n log n)\)	\(O(n log n)\)	\(O(n)\)	穩定

五、總結

• Python 內置的?sorted()?函數和?list.sort()?方法使用方便，性能也比較好，在大多數情況下可以直接使用。
• 不同的排序算法有不同的時間復雜度和空間復雜度，在選擇排序算法時需要根據具體的應用場景進行選擇。例如，當數據量較小時，簡單的排序算法（如冒泡排序、選擇排序、插入排序）可能更合適；當數據量較大時，高效的排序算法（如快速排序、歸并排序）則更有優勢。