目錄

1、簡述

2、復雜度

3、穩定性

4、例子

---

1、簡述

二路歸并排序（Merge Sort）是一種基于分治法的排序算法，通過將數組遞歸地拆分成兩部分，分別排序后再合并，從而實現整個數組的有序。二路歸并排序具有穩定性和高效性，是一種非常經典的排序算法。

實現步驟

1. 分割：
   • 將數組分成兩部分，分別對每部分進行遞歸排序。
2. 合并：
   • 將兩個已排序的部分合并成一個有序的整體。

2、復雜度

• 時間復雜度：

  • 最佳情況：O(n log n)
  • 最壞情況：O(n log n)
  • 平均情況：O(n log 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;}
}// 遞歸實現歸并排序
void mergeSort(std::vector<int>& arr, int left, int right) {if (left < right) {int mid = left + (right - left) / 2;// 遞歸排序兩個子數組mergeSort(arr, left, mid);mergeSort(arr, mid + 1, right);// 合并兩個已排序的子數組merge(arr, left, mid, right);}
}// 測試代碼
int main() {std::vector<int> array = {12, 11, 13, 5, 6, 7};mergeSort(array, 0, array.size() - 1);std::cout << "Sorted array is \n";for (int num : array)std::cout << num << " ";std::cout << std::endl;return 0;
}

?快捷跳轉：?

• 排序算法概述

---

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