冒泡排序和選擇排序的區別#
冒泡排序的基本思想是從待排序的序列中依次比較相鄰的兩個元素，如果它們的順序不正確，則進行交換。通過多次遍歷，將最大（或最小）的元素逐漸移動到序列的最後，直到整個序列有序為止。
選擇排序的基本思想是從待排序的序列中選擇最小（或最大）的元素，和序列的第一個元素進行交換，然後從剩餘的未排序部分中繼續選擇最小（或最大）的元素，和序列的第二個元素進行交換，以此類推，直到整個序列有序為止。
總結起來，冒泡排序通過比較相鄰元素並交換來逐步移動最大（或最小）元素，而選擇排序則是通過選擇最小（或最大）元素並交換來逐步構建有序序列。由於每次交換需要佔用較多的時間，所以選擇排序的平均性能要好於冒泡排序，但在實際應用中，如果待排序序列基本有序，冒泡排序可能會比選擇排序更快。
選擇排序和冒泡排序的時間複雜度和穩定性#
冒泡排序（Bubble Sort）
時間複雜度：最好情況下 O (n)，平均和最壞情況下 O (n^2)。
空間複雜度：O (1)。
穩定性：是一個穩定的排序算法，因為在相鄰元素交換的時候，只有當需要交換的元素之間的相對順序不時才會發生交換。
選擇排序（Selection Sort）：
時間複雜度：無論最好、平均和最壞情況下都是 O (n^2)。
空間複雜度：O (1)。
穩定性：選擇排序是一個非穩定的排序算法。在每次選擇最小（或最大）元素的過程中，可能會破壞相同元素之間的相對順序。
綜上所述，冒泡排序是一個穩定的排序算法，而選擇排序是一個非穩定的排序算法。選擇排序在每一輪選擇最小（或最大）元素的過程中，可能導致相同元素的相對順序發生改變。因此，在需要保持相同元素相對順序的情況下，選擇排序不適用，而冒泡排序可以保持相同元素的相對順序。
Python 程式碼舉例說明穩定性和非穩定性的區別，分別使用冒泡排序和選擇排序來進行排序#
首先，我們定義一個包含姓名和分數屬性的學生類：
python
class Student:
def __init__(self, name, score):
self.name = name
self.score = score
def __str__(self):
return f"{self.name}: {self.score}"
接下來，我們創建一個學生陣列，並包含兩個分數相等但姓名不同的學生對象：
students = [
Student("Tom", 80),
Student("Alice", 90),
Student("Bob", 80),
Student("Jack", 70),
Student("David", 80)
]
然後，我們分別使用冒泡排序和選擇排序對學生陣列按照分數進行排序：
冒泡排序：
def bubble_sort(students):
n = len(students)
for i in range(n - 1):
for j in range(n - 1 - i):
if students[j].score > students[j + 1].score:
students[j], students[j + 1] = students[j + 1], students[j]
bubble_sort(students)
選擇排序：
def selection_sort(students):
n = len(students)
for i in range(n - 1):
min_index = i
for j in range(i + 1, n):
if students[j].score < students[min_index].score:
min_index = j
students[i], students[min_index] = students[min_index], students[i]
selection_sort(students)
最後，我們遍歷排序後的學生陣列，輸出排序結果：
for student in students:
print(student)
如果採用穩定的排序算法，比如冒泡排序，執行上述程式碼後的輸出可能是：
Jack: 70
Tom: 80
Bob: 80
David: 80
Alice: 90
可以看到，分數相同的學生對象在排序後保持了原有的相對順序。
而如果採用非穩定的排序算法，比如選擇排序，執行上述程式碼後的輸出可能是：
Jack: 70
Bob: 80
David: 80
Tom: 80
Alice: 90
可以看到，選擇排序打亂了分數相同的學生對象的相對順序。
如果相同分數的元素之間存在某種關聯性或排序規則，改變它們的順序可能會導致這種關聯性丟失。
所以，排序算法的 “非穩定”，主要指的是相同元素排序前後的相對順序可能會改變。
冒泡排序在排序後不改變相同元素的相對位置，故是穩定排序算法；而選擇排序，是非穩定排序算法。
要求穩定排序算法的案例#
確保相同元素的相對位置在排序前後一致的穩定排序算法在許多實際案例中都是必需的。以下是一些常見的需要保持相對位置的實際案例：
歷史記錄排序：在許多應用中，例如瀏覽器歷史記錄、聊天記錄或編輯器中的操作記錄，用戶可能希望按照時間順序查看記錄，並且相同時間戳的記錄應按其出現順序顯示。
優先級隊列：在任務調度系統中，例如操作系統的進程調度或線程池中的任務調度，可能存在具有相同優先級的多個任務。為了公平地處理這些任務，穩定排序可以確保任務按照它們被添加到隊列的順序進行調度。
排名計算：在競賽、比賽或投票等情境中，如果有多個參與者得分相同，則根據其出現的順序確定名次是公平和合理的做法。穩定排序算法可以確保參與者的相對順序不會變化，從而保持正確的排名結果。
特徵提取：在機器學習和數據分析中，特徵提取是一項重要任務。當對數據進行特徵提取時，如果存在相同特徵值的數據點，穩定排序可以確保相同特徵值的數據點在輸出中保持原有的相對位置。
交易處理：在金融領域中，當處理交易記錄時，可能會遇到相同時間戳或相同價格的交易。為了確保交易的正確處理和順序，穩定排序可以保持交易記錄的相對順序不變。