目錄

1、簡述

2、復雜度

3、穩定性

4、例子

---

1、簡述

有序序列的合并（Merge of Sorted Sequences）是歸并排序的核心步驟之一。其目的是將兩個已經排序的序列合并成一個新的有序序列。這個過程在歸并排序中非常重要，因為歸并排序通過遞歸地將序列分割成子序列，然后合并這些子序列來實現排序。

實現步驟

1. 創建臨時數組：

   • 用于存儲兩個子序列的數據，以便合并操作。

2. 雙指針法：

   • 使用兩個指針分別指向兩個子序列的開頭。
   • 比較指針所指向的元素，將較小的元素放入臨時數組中，然后移動指針。

3. 處理剩余元素：

   • 當一個子序列的元素全部被處理完后，將另一個子序列的剩余元素直接復制到臨時數組中。

4. 將臨時數組的內容復制回原數組：

   • 合并完成后，將臨時數組中的數據復制回原數組對應的位置。

2、復雜度

• 時間復雜度：

  • O(n)，其中 n 是兩個有序序列的總長度，因為每個元素都只處理一次。

• 空間復雜度：

  • O(n)，需要額外的空間來存儲臨時數組。

3、穩定性

有序序列的合并是穩定的，因為在合并過程中，相同元素的相對位置不會改變。

4、例子

#include <iostream>
#include <vector>// 合并兩個有序子數組
void merge(std::vector<int>& arr, int left, int mid, int right) {int n1 = mid - left + 1;int n2 = right - mid;// 創建臨時數組std::vector<int> L(n1);std::vector<int> R(n2);// 復制數據到臨時數組 L[] 和 R[]for (int i = 0; i < n1; ++i)L[i] = arr[left + i];for (int i = 0; i < n2; ++i)R[i] = arr[mid + 1 + i];// 合并臨時數組到原數組int i = 0, j = 0, k = left;while (i < n1 && j < n2) {if (L[i] <= R[j]) {arr[k] = L[i];++i;} else {arr[k] = R[j];++j;}++k;}// 復制剩余元素（如果有）while (i < n1) {arr[k] = L[i];++i;++k;}while (j < n2) {arr[k] = R[j];++j;++k;}
}// 測試代碼
int main() {std::vector<int> array = {2, 5, 8, 1, 3, 7, 9, 10};int mid = (array.size() - 1) / 2;// 合并兩個有序序列 [2, 5, 8] 和 [1, 3, 7, 9, 10]merge(array, 0, mid, array.size() - 1);std::cout << "Merged array is \n";for (int num : array)std::cout << num << " ";std::cout << std::endl;return 0;
}

代碼說明

1. merge 函數：

   1. 參數：arr 是待排序的數組，left 是左子數組的起始索引，mid 是左右子數組的分界點，right 是右子數組的結束索引。
   2. 步驟：
      1. 創建并初始化兩個臨時數組 L 和 R，分別存儲左子數組和右子數組的元素。
      2. 使用雙指針法將兩個子數組合并到原數組中。
      3. 處理任何剩余的元素，將其直接復制到原數組中。

2. main 函數：

   1. 創建一個示例數組并設定中間點。
   2. 調用 merge 函數合并兩個有序子數組。
   3. 輸出合并后的數組。

?快捷跳轉：?

• 排序算法概述

---

生命不息，學習不止，若有不正確的地方，歡迎指正。