一、快速排序

1. 選擇基準值（Pivot）

• 作用 ：從數組中選擇一個元素作為基準（Pivot），用于劃分數組。
• 常見選擇方式 ：
  • 固定選擇最后一個元素（如示例代碼）。
  • 隨機選擇（優化最壞情況）。
  • 選擇中間元素或“三數取中”（避免極端情況）。
• 示例 ：對數組 [10, 7, 8, 9, 1, 5]，選擇最后一個元素 5 作為基準。

2. 分區操作（Partition）

• 目標 ：將數組分為兩部分，使得：
  • 左半部分所有元素 ≤ 基準值。
  • 右半部分所有元素 > 基準值。
• 具體步驟 ：
  1. 初始化兩個指針：
     • i：標記小于基準的邊界（初始為 low-1）。
     • j：遍歷數組的指針（從 low 到 high-1）。
  2. 遍歷數組：
     • 如果 arr[j] ≤ pivot，則 i++，并交換 arr[i] 和 arr[j]。
     • 否則，不做操作，繼續移動 j。
  3. 最后，將基準值交換到正確位置（i+1）。
• 示例 ：
  • 初始數組：[10, 7, 8, 9, 1, 5]（基準為 5）。
  • 分區后：[1, 5, 8, 9, 7, 10]（基準位置為索引 1）。

3. 遞歸排序子數組

• 分治策略 ：
  1. 對左半部分（low 到 pivotIndex-1）遞歸調用快速排序。
  2. 對右半部分（pivotIndex+1 到 high）遞歸調用快速排序。
• 終止條件 ：當子數組長度 ≤1 時，無需排序（遞歸結束）。
• 示例 ：
  • 左子數組 [1]（已有序）。
  • 右子數組 [8, 9, 7, 10]，繼續遞歸分區。

4. 代碼實現

#include <algorithm>  // 提供 std::swap 函數
#include <cstdlib>    // 提供 rand() 和 srand()
#include <ctime>      // 提供 time() 函數用于初始化隨機數種子
#include <iostream>   // 提供輸入輸出功能
#include <vector>     // 提供動態數組 vectorusing namespace std;// 分區函數：將數組劃分為兩部分，并返回基準值的最終位置
int partition(vector<int>& nums, int low, int high)
{// 隨機選擇一個索引作為基準值，并將其與最后一個元素交換int index = low + (rand() % (high - low + 1)); // 隨機選擇 [low, high] 范圍內的索引swap(nums[index], nums[high]);                 // 將基準值放到末尾int pivot = nums[high];                        // 基準值為當前區間最后一個元素int i = low - 1;                               // i 表示小于基準值的邊界// 遍歷區間 [low, high-1]，將小于基準值的元素放到左邊for (int j = low; j < high; j++) {if (nums[j] < pivot) {                     // 如果當前元素小于基準值++i;                                   // 擴展小于基準值的區域swap(nums[j], nums[i]);                // 將當前元素與邊界后的元素交換}}// 將基準值放到正確的位置（即小于基準值區域的后一個位置）swap(nums[++i], nums[high]);return i;                                      // 返回基準值的最終位置
}// 快速排序主函數：遞歸地對數組進行排序
void quick_sort(vector<int>& nums, int low, int high)
{// 如果區間有效（low < high），則繼續分區和遞歸排序if (low < high) {int index = partition(nums, low, high);    // 對當前區間進行分區，獲取基準值位置quick_sort(nums, low, index - 1);          // 遞歸排序左分段（小于基準值的部分）quick_sort(nums, index + 1, high);         // 遞歸排序右分段（大于基準值的部分）}
}int main()
{srand(time(0));                                // 初始化隨機數種子，確保每次運行生成不同的隨機數// 定義測試用例vector<int> nums1 = {10, 7, 8, 9, 1, 5};        // 普通數組vector<int> nums2 = {1};                       // 單元素數組vector<int> nums3 = {};                        // 空數組vector<int> nums4 = {5, 5, 5, 5};              // 全部相等的數組// 對每個數組進行快速排序quick_sort(nums1, 0, nums1.size() - 1);quick_sort(nums2, 0, nums2.size() - 1);quick_sort(nums3, 0, nums3.size() - 1);quick_sort(nums4, 0, nums4.size() - 1);// 輸出排序結果cout << "nums1: ";for (auto& x : nums1)cout << x << " ";                          // 輸出普通數組的排序結果cout << endl;cout << "nums2: ";for (auto& x : nums2)cout << x << " ";                          // 輸出單元素數組的排序結果cout << endl;cout << "nums3: ";for (auto& x : nums3)cout << x << " ";                          // 輸出空數組的排序結果cout << endl;cout << "nums4: ";for (auto& x : nums4)cout << x << " ";                          // 輸出全部相等數組的排序結果cout << endl;return 0;
}

運行結果：?

以數組 [10, 7, 8, 9, 1, 5] 為例：

1. 第一次分區 ：
   • 基準值為 5。
   • 分區后數組變為 [1, 5, 8, 9, 7, 10]，基準位置為索引 1。
2. 遞歸處理左子數組 [1]（無需操作）。
3. 遞歸處理右子數組 [8, 9, 7, 10]：
   • 選擇基準 10，分區后數組變為 [8, 9, 7, 10]，基準位置為索引 3。
   • 遞歸處理左子數組 [8, 9, 7]：
     • 選擇基準 7，分區后 [7, 9, 8]，基準位置為索引 0。
     • 遞歸處理右子數組 [9, 8]，最終排序為 [8, 9]。
   • 合并結果得到 [7, 8, 9, 10]。
4. 最終排序結果 ：[1, 5, 7, 8, 9, 10]。

---

二、歸并排序

1. 分治策略?

1. 分解 ：將數組不斷對半分割，直到每個子數組長度為1（天然有序）
2. 解決 ：遞歸地對左右子數組進行排序
3. 合并 ：將兩個有序子數組合并成一個更大的有序數組

2. 歸并排序的分解過程

1、初始數組

索引：0 ? 1 ? 2 ? 3 ? 4 ? 5
值： 10 ?7 ? 8 ? 9 ? 1 ? 5

2、?第一層分解 （整個數組）

[10, 7, 8, 9, 1, 5] → 左半部分 [10, 7, 8] 和 右半部分 [9, 1, 5]

?3、第二層分解 （左半部分 [10,7,8]）

[10,7,8] → 左半部分 [10] 和 右半部分 [7,8]

?4、第三層分解 （右半部分 [7,8]）

[7,8] → 左半部分 [7] 和 右半部分 [8]

?5、第二層分解 （右半部分 [9,1,5]）

[9,1,5] → 左半部分 [9] 和 右半部分 [1,5]

6、第三層分解 （右半部分 [1,5]）

[1,5] → 左半部分 [1] 和 右半部分 [5]

?3. 歸并排序的合并過程

1)、合并層級 1

1. 合并 [7] 和 [8] → [7,8]

2. 合并 [1] 和 [5] → [1,5]

2)、合并層級 2

• 合并 [10] 和 [7,8] → [7,8,10]

10 vs 7 → 取7 → 新數組[7]
10 vs 8 → 取8 → 新數組[7,8]
剩余10 → 追加 → [7,8,10]

• ?合并 [9] 和 [1,5] → [1,5,9]

9 vs 1 → 取1 → 新數組[1]
9 vs 5 → 取5 → 新數組[1,5]
剩余9 → 追加 → [1,5,9]

3)、?合并層級 3（最終合并）

左數組：7,8,10
右數組：1,5,9
初始指針：i=0（左）, j=0（右）

1. 比較 7 vs 1 → 取1 → 新數組[1]
2. 比較 7 vs 5 → 取5 → 新數組[1,5]
3. 比較 7 vs 9 → 取7 → 新數組[1,5,7]
4. 比較 8 vs 9 → 取8 → 新數組[1,5,7,8]
5. 比較 10 vs 9 → 取9 → 新數組[1,5,7,8,9]
6. 右數組耗盡，追加剩余左數組元素 → [1,5,7,8,9,10]

?4、代碼實現

#include <iostream>
#include <vector>
using namespace std;/*** 合并兩個有序子數組* @param nums 原始數組* @param l 左邊界索引（包含）* @param r 右邊界索引（包含）* @param mid 中間分割點索引*/
void merge(vector<int>& nums, int l, int r, int mid)
{// 創建左右子數組（左閉右開區間）vector<int> left(nums.begin() + l,nums.begin() + mid + 1); // 左子數組 [l, mid]vector<int> right(nums.begin() + mid + 1,nums.begin() + r + 1); // 右子數組 [mid+1, r]int i = 0, j = 0, k = l; // i:左數組指針，j:右數組指針，k:原數組指針// 合并兩個有序數組while (i < left.size() && j < right.size()) {// 使用 <= 保持穩定性：相等元素保留原始順序if (left[i] <= right[j]) {nums[k++] = left[i++];}else {nums[k++] = right[j++];}}// 處理剩余元素（如果有的話）while (i < left.size())nums[k++] = left[i++];while (j < right.size())nums[k++] = right[j++];
}/*** 歸并排序遞歸函數* @param nums 待排序數組* @param l 當前處理范圍的左邊界（包含）* @param r 當前處理范圍的右邊界（包含）*/
void merge_sort(vector<int>& nums, int l, int r)
{if (l >= r)return;                   // 遞歸終止條件：子數組長度≤1int mid = l + (r - l) / 2;    // 防溢出的中間點計算merge_sort(nums, l, mid);     // 遞歸排序左半部分merge_sort(nums, mid + 1, r); // 遞歸排序右半部分merge(nums, l, r, mid);       // 合并有序子數組
}/*** 歸并排序輔助函數（對外接口）* @param nums 待排序數組*/
void merge_sort(vector<int>& nums)
{if (!nums.empty()) { // 非空時才執行排序merge_sort(nums, 0, nums.size() - 1);}
}/*** 測試用例執行函數* @param nums 測試數組* @param testName 測試用例名稱*/
void runTest(vector<int>& nums, const string& testName)
{cout << "========== " << testName << " ==========\n";cout << "原始數組: ";if (nums.empty()) {cout << "（空數組）";}else {for (int num : nums)cout << num << " ";}cout << endl;merge_sort(nums); // 執行排序cout << "排序結果: ";if (nums.empty()) {cout << "（空數組）";}else {for (int num : nums)cout << num << " ";}cout << "\n\n";
}int main()
{// 測試用例定義vector<int> nums1 = {10, 7, 8, 9, 1, 5}; // 普通無序數組vector<int> nums2 = {1};                 // 單元素數組vector<int> nums3 = {};                  // 空數組vector<int> nums4 = {5, 5, 5, 5};        // 全相等元素數組vector<int> nums5 = {3, 1, 2, 4, 5};     // 部分有序數組vector<int> nums6 = {5, 4, 3, 2, 1};     // 完全逆序數組// 執行測試runTest(nums1, "普通數組");runTest(nums2, "單元素數組");runTest(nums3, "空數組");runTest(nums4, "全部相等的數組");runTest(nums5, "部分有序數組");runTest(nums6, "完全逆序數組");return 0;
}

運行結果?

---

三、插入排序

1、算法步驟?

1. 初始狀態 ：默認第一個元素是已排序的。
2. 迭代過程 ：
   • 從第二個元素開始，依次取出每個元素（稱為“當前元素”）。
   • 將當前元素與已排序序列中的元素從后向前 依次比較。
   • 如果已排序的元素大于當前元素，則將其后移一位，為當前元素騰出位置。
   • 直到找到已排序元素小于或等于當前元素的位置，將當前元素插入此處。
3. 終止條件 ：所有元素均被插入到已排序序列中。

2、代碼實現

#include <iostream>
#include <vector>
using namespace std;/*** @brief 插入排序算法實現** 通過逐步構建有序序列，將未排序元素插入到已排序序列的正確位置。* 時間復雜度：O(n2) 最壞/平均情況，O(n) 最好情況（已有序）* 空間復雜度：O(1) 原地排序* 穩定性：穩定排序算法** @param nums 待排序的整型向量（引用傳遞，直接修改原數組）*/
void insert_sort(vector<int>& nums)
{if(nums.empty() && nums.size() == 1) return;for (int i = 1; i < nums.size(); i++) {int temp = nums[i]; // 保存當前待插入元素int j = i - 1;// 將大于temp的已排序元素后移，騰出插入空間while (j >= 0 && nums[j] > temp) {nums[j + 1] = nums[j];--j;}// 因為內層循環結束后，j 必定在待插入元素的前一位// 比如：插入位置為0，那么j 必定等于 -1nums[j + 1] = temp; // 插入到正確位置}
}/*** 測試用例執行函數* @param nums 測試數組* @param testName 測試用例名稱*/
void runTest(vector<int>& nums, const string& testName)
{cout << "========== " << testName << " ==========\n";cout << "原始數組: ";if (nums.empty()) {cout << "（空數組）";}else {for (int num : nums)cout << num << " ";}cout << endl;insert_sort(nums); // 執行排序cout << "排序結果: ";if (nums.empty()) {cout << "（空數組）";}else {for (int num : nums)cout << num << " ";}cout << "\n\n";
}int main()
{// 測試用例定義vector<int> nums1 = {10, 7, 8, 9, 1, 5}; // 普通無序數組vector<int> nums2 = {1};                 // 單元素數組vector<int> nums3 = {};                  // 空數組vector<int> nums4 = {5, 5, 5, 5};        // 全相等元素數組vector<int> nums5 = {3, 1, 2, 4, 5};     // 部分有序數組vector<int> nums6 = {5, 4, 3, 2, 1};     // 完全逆序數組// 執行測試runTest(nums1, "普通數組");runTest(nums2, "單元素數組");runTest(nums3, "空數組");runTest(nums4, "全部相等的數組");runTest(nums5, "部分有序數組");runTest(nums6, "完全逆序數組");return 0;
}

運行結果

---

??四、冒泡排序

1、算法步驟

1. 遍歷數組 ：從頭開始，比較相鄰元素。
2. 交換操作 ：如果前一個元素 > 后一個元素，交換兩者。
3. 重復遍歷 ：每一輪遍歷后，最大的元素會被移動到末尾，下一輪可減少一次比較。
4. 提前終止 ：如果某次遍歷沒有發生交換，說明已有序，可提前結束排序。

2、代碼實現

#include <iostream>
#include <vector>using namespace std;/*** @brief 冒泡排序算法實現** 通過重復遍歷數組，比較相鄰元素并在順序錯誤時交換它們。* 每輪遍歷將最大的元素"浮"到數組末尾，并通過優化標志提前終止有序數組的排序。** 時間復雜度：*   - 最壞/平均情況：O(n2)（完全逆序時）*   - 最好情況：O(n)（已有序時）* 空間復雜度：O(1)（原地排序）* 穩定性：穩定排序（相同元素相對位置不變）** @param nums 待排序的整型向量（引用傳遞，直接修改原數組）*/
void bubble_sort(vector<int>& nums)
{if (nums.empty() || nums.size() == 1)return;// 用與檢查該次循環是否發生交換bool isSwap;for (int i = 0; i < nums.size() - 1; i++) {isSwap = false;// 每輪結束后都會將該輪最大的值排到最后// 那么，就沒必要再比較最后 i 個元素for (int j = 0; j < nums.size() - i - 1; j++) {if (nums[j] > nums[j + 1]) {swap(nums[j], nums[j + 1]);isSwap = true;}}// 如果該輪循環沒有交換// 代表數組已經有序，可以提前結束了if (!isSwap) {break;}}
}/*** 測試用例執行函數* @param nums 測試數組* @param testName 測試用例名稱*/
void runTest(vector<int>& nums, const string& testName)
{cout << "========== " << testName << " ==========\n";cout << "原始數組: ";if (nums.empty()) {cout << "（空數組）";}else {for (int num : nums)cout << num << " ";}cout << endl;bubble_sort(nums); // 執行排序cout << "排序結果: ";if (nums.empty()) {cout << "（空數組）";}else {for (int num : nums)cout << num << " ";}cout << "\n\n";
}int main()
{// 測試用例定義vector<int> nums1 = {10, 7, 8, 9, 1, 5}; // 普通無序數組vector<int> nums2 = {1};                 // 單元素數組vector<int> nums3 = {};                  // 空數組vector<int> nums4 = {5, 5, 5, 5};        // 全相等元素數組vector<int> nums5 = {3, 1, 2, 4, 5};     // 部分有序數組vector<int> nums6 = {5, 4, 3, 2, 1};     // 完全逆序數組// 執行測試runTest(nums1, "普通數組");runTest(nums2, "單元素數組");runTest(nums3, "空數組");runTest(nums4, "全部相等的數組");runTest(nums5, "部分有序數組");runTest(nums6, "完全逆序數組");return 0;
}

運行結果?

---

?五、選擇排序

1、算法步驟

1. 初始化 ：將數組視為未排序部分 。
2. 選擇最小元素 ：從未排序部分中找到最小值。
3. 交換位置 ：將最小值與未排序部分的第一個元素交換，將其加入已排序部分。
4. 重復 ：縮小未排序范圍，直到所有元素有序。

2、代碼實現

#include <iostream>
#include <vector>using namespace std;/*** @brief 選擇排序算法實現** 核心思想：每次從未排序部分選擇最小元素，放到已排序序列的末尾。** 時間復雜度：O(n2)（所有情況下均為 O(n2)）* 空間復雜度：O(1)（原地排序）* 穩定性：不穩定（可能改變相等元素的相對位置）** @param nums 待排序的整型向量（引用傳遞，直接修改原數組）*/
void selection_sort(vector<int>& nums)
{// 處理空數組或單元素數組（無需排序）if (nums.empty() || nums.size() == 1) {return;}int n = nums.size();for (int i = 0; i < n - 1; i++) {int minIndex = i; // 初始化最小值索引為當前未排序部分的起始位置// 在未排序部分 [i+1, n-1] 尋找最小值的索引for (int j = i + 1; j < n; j++) {if (nums[j] < nums[minIndex]) {minIndex = j;}}// 將最小值交換到已排序部分的末尾（i 位置）swap(nums[i], nums[minIndex]);}
}/*** 測試用例執行函數* @param nums 測試數組* @param testName 測試用例名稱*/
void runTest(vector<int>& nums, const string& testName)
{cout << "========== " << testName << " ==========\n";cout << "原始數組: ";if (nums.empty()) {cout << "（空數組）";}else {for (int num : nums)cout << num << " ";}cout << endl;selection_sort(nums); // 執行排序cout << "排序結果: ";if (nums.empty()) {cout << "（空數組）";}else {for (int num : nums)cout << num << " ";}cout << "\n\n";
}int main()
{// 測試用例定義vector<int> nums1 = {10, 7, 8, 9, 1, 5}; // 普通無序數組vector<int> nums2 = {1};                 // 單元素數組vector<int> nums3 = {};                  // 空數組vector<int> nums4 = {5, 5, 5, 5};        // 全相等元素數組vector<int> nums5 = {3, 1, 2, 4, 5};     // 部分有序數組vector<int> nums6 = {5, 4, 3, 2, 1};     // 完全逆序數組// 執行測試runTest(nums1, "普通數組");runTest(nums2, "單元素數組");runTest(nums3, "空數組");runTest(nums4, "全部相等的數組");runTest(nums5, "部分有序數組");runTest(nums6, "完全逆序數組");return 0;
}

運行結果