[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); } ```