1.分治法原理

所謂的分治指的就是分而治之，即將大規模的問題分解成幾個較小規模的問題。通過對較小規模問題的求解達到對整個問題的的求解。當我們將問題分解成兩個較小問題求解時的分治方法就是二分法。

分支的基本思想是將一個規模為n的問題分解為k個規模較小的子問題，這些子問題相互獨立且與原問題相似。找出個問題的解，然后把各問題的解組合成整個問題的的解。

分治的具體過程：

1.if 問題不可分，返回問題解。

2.else 從原問題中劃出含一半運算對象的子問題1；

3. ? 遞歸調用分治法過程，求出解1.

4. ? 從原問題中劃出含另一半運算對象的子問題2；

5. ? 遞歸調用分治法過程，求出解2；

6. ? 將解1，解2組合成整個問題的解。

2.源代碼

#include<time.h> #include<iostream> using namespace std;// 合并函數 void merge(int *arr, int p, int q, int r) {int len1 = q - p + 1; int len2 = r - q;int *L = new int[len1 + 1];//用動態數組儲存左邊的數 int *R = new int[len2 + 1];//用動態數組儲存右邊的數 for (int i = 0; i < len1; i++) {// 把Array數組左邊的數放入L數組 L[i] = arr[p + i];}for (int j = 0; j < len2; j++) {// 把Array數組右邊的數放入R數組 R[j] = arr[q + 1 + j];}L[len1] = R[len2] = INT_MAX; //定義無窮大 int i = 0, j = 0;for (int k = p; k <= r; k++) {if (L[i] < R[j]) {//小的放左邊，大的放右邊 arr[k] = L[i];i++;}else {arr[k] = R[j];j++;}} }// 歸并排序 void mergeSort(int arr[], int p, int r) {if (p < r){int q = 0;q = (r + p) / 2;mergeSort(arr, p, q);mergeSort(arr, q + 1, r);merge(arr, p, q, r);} }int main() {int n;cout << "輸入產生數組的個數:";cin >> n;cout << endl;int *arr = new int[n];cout << "產生的隨機數組為:";srand((unsigned)time(0));for (int i = 0; i < n; i++){arr[i] = (rand() % (100 - 0 + 1)) + 0;cout << arr[i] << " ";}cout << endl;mergeSort(arr, 0, n - 1);cout << "排序后的數組為：";for (int j = 0; j<n; j++){cout << arr[j] << " ";}system("pause"); } 最差時間復雜度：O(nlogn)?
平均時間復雜度：O(nlogn)?
最差空間復雜度：O(n)?
穩定性：穩定

總結

以上是生活随笔為你收集整理的算法导论-排序算法-分治法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。