前言

排序算法是數據處理的基礎且重要的組成部分，冒泡排序、選擇排序和插入排序作為基礎排序算法，雖然在效率上不及一些高級排序算法，但它們原理簡單、易于理解，是學習排序算法的入門之選，也是理解更復雜排序算法的基礎。本文我將詳細介紹這三種基礎排序算法的原理、實現代碼、性能分析以及實際應用場景。

一、冒泡排序（Bubble Sort）

1.1 算法原理

冒泡排序的基本思想是重復地走訪過要排序的數列，一次比較兩個相鄰的元素，如果它們的順序錯誤就把它們交換過來。走訪數列的工作是重復地進行直到沒有再需要交換，也就是說該數列已經排序完成。這個過程就像水中的氣泡，較小（或較大）的元素會逐漸 “浮” 到數列的頂端，因此得名冒泡排序。

具體過程如下：

比較相鄰的元素。如果第一個比第二個大（升序排序），就交換它們兩個。

對每一對相鄰元素做同樣的工作，從開始第一對到結尾的最后一對。這步做完后，最后的元素會是最大的數。

針對所有的元素重復以上的步驟，除了最后一個。

持續每次對越來越少的元素重復上面的步驟，直到沒有任何一對數字需要比較。

1.2 代碼實現（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 arr

在上述代碼中，外層循環控制排序的輪數，一共需要n輪（n為數組長度）。內層循環用于每一輪中相鄰元素的比較和交換，隨著外層循環的進行，每一輪比較的次數逐漸減少，因為每一輪結束后，最大的元素已經 “沉” 到了數組末尾。

1.3 性能分析

時間復雜度：

最好情況：當數組已經是有序狀態時，冒泡排序只需要進行一次遍歷，比較n - 1次，不需要交換元素，時間復雜度為$O(n)$。

最壞情況：當數組是逆序狀態時，需要進行$n(n?1)/2$次比較和交換操作，時間復雜度為$O(n^2)$。

平均情況：時間復雜度同樣為$O(n^2)$。

空間復雜度：冒泡排序只需要使用常數級別的額外空間來進行元素交換，空間復雜度為$O(1)$。

穩定性：冒泡排序是一種穩定的排序算法，因為在比較和交換元素時，相同元素的相對順序不會改變。

二、選擇排序（Selection Sort）

2.1 算法原理

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

具體步驟如下：

在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。

再從剩余未排序元素中繼續尋找最小（大）元素，然后放到已排序序列的末尾。

重復第二步，直到所有元素均排序完畢。

2.2 代碼實現（Java）

public class SelectionSort {public static int[] selectionSort(int[] arr) {int n = arr.length;for (int i = 0; i < n - 1; i++) {int minIndex = i;for (int j = i + 1; j < n; j++) {if (arr[j] < arr[minIndex]) {minIndex = j;}}int temp = arr[minIndex];arr[minIndex] = arr[i];arr[i] = temp;}return arr;}public static void main(String[] args) {int[] arr = {64, 25, 12, 22, 11};int[] sortedArr = selectionSort(arr);for (int num : sortedArr) {System.out.print(num + " ");}}
}

上述 Java 代碼中，外層循環控制排序的輪數，一共需要n - 1輪（n為數組長度）。內層循環用于在每一輪中找到未排序部分的最小元素的索引，然后將其與當前輪起始位置的元素交換。

2.3 性能分析

時間復雜度：

最好情況：即使數組已經是有序的，選擇排序也需要進行$n(n?1)/2$次比較，時間復雜度為$O(n^2)$。

最壞情況：同樣需要進行$n(n?1)/2$次比較和交換操作，時間復雜度為$O(n^2)$。

平均情況：時間復雜度為$O(n^2)$。

空間復雜度：選擇排序只需要使用常數級別的額外空間來進行元素交換，空間復雜度為$O(1)$。

穩定性：選擇排序是不穩定的排序算法，因為在選擇最小元素并交換位置時，可能會改變相同元素的相對順序。例如，數組[5, 5, 3]，在排序過程中兩個5的相對順序可能會發生變化。

三、插入排序（Insertion Sort）

3.1 算法原理

插入排序的基本思想是將一個數據插入到已經排好序的有序數據中，從而得到一個新的、個數加一的有序數據。其操作過程就像玩撲克牌時整理手中牌的過程，每次從 “牌堆” 中摸一張牌，插入到手中已整理好的牌的合適位置。

具體過程如下：

從第一個元素開始，該元素可以認為已經被排序。

取出下一個元素，在已經排序的元素序列中從后向前掃描。

如果該元素（已排序）大于新元素，將該元素移到下一位置。

重復步驟 3，直到找到已排序的元素小于或者等于新元素的位置。

將新元素插入到該位置后。

重復步驟 2~5，直到所有元素均排序完畢。

3.2 代碼實現（C++）

#include <iostream>
#include <vector>
using namespace std;vector<int> insertionSort(vector<int> arr) {int n = arr.size();for (int i = 1; i < n; ++i) {int key = arr[i];int j = i - 1;while (j >= 0 && arr[j] > key) {arr[j + 1] = arr[j];j = j - 1;}arr[j + 1] = key;}return arr;
}

在 C++ 代碼中，外層循環從數組的第二個元素開始（因為第一個元素默認已排序）。內層循環用于在已排序部分中找到合適的插入位置，將當前元素插入到正確的位置，使得已排序部分始終保持有序。

3.3 性能分析

時間復雜度：

最好情況：當數組已經是有序狀態時，每插入一個元素只需要比較一次，不需要移動元素，時間復雜度為$O(n)$。

最壞情況：當數組是逆序狀態時，插入每個元素都需要比較和移動i次（i為當前元素的索引），時間復雜度為$O(n^2)$。

平均情況：時間復雜度為$O(n^2)$。

空間復雜度：插入排序只需要使用常數級別的額外空間來保存當前要插入的元素，空間復雜度為$O(1)$。

穩定性：插入排序是穩定的排序算法，因為在插入元素時，相同元素的相對順序不會改變。

四、三種基礎排序算法的對比與應用場景

算法對比

排序算法	時間復雜度（最好）	時間復雜度（最壞）	時間復雜度（平均）	空間復雜度	穩定性
冒泡排序	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$	穩定
選擇排序	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O(1)$	不穩定
插入排序	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$	穩定

應用場景

冒泡排序：由于其簡單易懂，常用于教學場景幫助初學者理解排序算法的基本概念。在數據規模較小且對時間要求不高的情況下，也可以使用。

選擇排序：適用于對穩定性要求不高，且數據規模較小的排序場景。比如在一些簡單的游戲內數據排序或者資源管理系統中，當數據量不大時可以使用。

插入排序：對于部分有序的數組或者數據量較小的數組，插入排序表現較好。例如，在數據庫的某些索引維護操作中，如果數據更新后仍保持部分有序，插入排序可以高效地對新數據進行插入和排序。

總結

冒泡排序、選擇排序和插入排序作為基礎排序算法，雖然在時間復雜度上都為$O(n^2)$，在處理大規模數據時效率較低，但它們的原理簡單，實現容易，是學習排序算法的重要基石。通過理解這三種算法，我們可以更好地掌握排序算法的基本思想，為學習更復雜高效的排序算法（快速排序、歸并排序、堆排序等）打下堅實的基礎。在下期博客中，我將深入探討快速排序與歸并排序這兩種高效排序算法，詳細解析它們的實現機制、性能特點以及在不同場景下的應用優勢，幫助大家進一步拓寬對排序算法的認知邊界。

That’s all, thanks for reading!
創作不易，點贊鼓勵；
知識無價，收藏備用；
持續精彩，關注不錯過！