[TOC] ## 概述 分治法的基本思想是：將原問題分解為若干個規模更小但結構與原問題相似的子問題。遞歸地解這些子問題，然后將這些子問題的解組合為原問題的解。 使用遞歸，則需要找到遞歸點和遞歸出口： * 遞歸點：如果數組的元素大于1，就需要再進行分解，所以我們的遞歸點就是新構造的數組元素個數大于1 * 遞歸出口：我們什么時候不需要再對新數組不進行排序了呢？就是當數組元素個數變成1的時候，所以這就是我們的出口。 ## C++代碼示例 ```cpp void printArray(int *a, int len) { for (size_t i = 0; i < len; i++) printf("%d\n", a[i]); } //快速排序 void quickSort(int *a, int left, int right) { int i = left; int j = right; if (i > j) return; int base = a[i]; while (i < j) { while (i < j && a[j] > base) j--; //分治法，從右往左找，找到比base小的數，賦值給a[i] if (i < j) a[i] = a[j]; while (i < j && a[i] < base) i++;//分治法，從左往右找，找到比base大的數，賦值給a[j] if (i < j) a[j] = a[i]; } a[i] = base;//base左邊是比base小的數，base右邊是比base大的數 quickSort(a, left, i-1);//分治遞歸左邊 quickSort(a, i+1, right);//分治遞歸右邊 } int main() { int a[] = {4,1, 2, 3, 5,7, 6}; quickSort(a, 7); printArray(a, 7); } ```