首页 > 代码库 > 分治与递归的结合-------快速排序
分治与递归的结合-------快速排序
运用了分治的思想:为了解决一个大的问题,将一个规模为n的问题分解为规模较小的子问题,这些子问题互相独立并且和原问题相同。分别解这些子问题,最后将子问题的解合并 得到原问题的解。比如实现n个数的快速排序可以分解为 基准点左侧的数的快速排序 和 基准点右侧的数的快速排序。并可以一直分治到只有1个数
运用了递归的手段实现分治。
第一种:
为什么要用递归:因为分治策略将大问题转化为与若干个与原问题解法相同的小问题,既然解法相同,原问题所用的函数 也就适用于若干个小问题。由于是若干个,不知道数量也 就没有办法为每个小问题量身定做一个函数,就算知道数量,定做出的函数除了初始值不一样其他都一样。所以可以通过设置终止条件,确定初始值,来多次地调 用原问题使用的函数。
怎么看待递归: 递归的其中一个重要部分是终止条件,终止条件明确了若干个究竟是多少个,究竟有多少个小问题。
递归的另一个重要部分就是通过一系列变换确定小问题的初始值,由于是多次调用,所以大问题与小问题一定存在某种联系
如何写递归函数 : 第一:明确终止条件
第二:找出大问题与小问题之间的联系,即如何将大的问题转化为小的问题(最简单的就是阶乘了 大问题与小问题 大问题的规模n减去一就能转化为小问题)
这也叫确定小问题的初始值。
写递归函数的步骤: 第一:分类讨论(其中包含终止条件 与 非终止条件 两者都可能不止一个)
第二:对于非终止条件,要对函数传入的n进行转化,转化为适用于小问题的n值,然后调用该递归函数解决这个小问题,并传回这个小问题的值
比如有 7 3 5 9 11 13 1 七个数
第一次调用递归的结果
int Partition(int arr[], int low, int high) //划分算法,low为数组最小下标,high为数组最大下标,目的是为了找到基准点(基准点左侧的数小于等于它,右侧大于等于它) { int i, j, pivot; i = low, j = high, pivot = arr[low]; //选择第一个数作为基准点 while(i < j) { while(i < j && arr[j] >= pivot) --j; if(i < j) swap(arr[i++], arr[j]); //交换 arr[i] 与 arr[j] 之后 i++ while(i < j && arr[i] <= pivot) ++i; if(i < j) swap(arr[i], arr[j--]); } return j; //返回基准元素位置 } void Quick_Sort(int arr[], int low, int high) { int pivotpos; if(low <= high) { pivotpos = Partition(arr, low, high); //通过转化 找到小问题的基准点 pivotpos 确定了小问题的初始条件 if(pivotpos > n / 2) Quick_Sort(arr, low, pivotpos - 1); //基准左递归排序,知道low>high 递归返回,返回的成果在数组中,所以不需要return,一切更改都会保留在数组里 else if(pivotpos < n / 2) Quick_Sort(arr, pivotpos + 1, high); //基准右递归排序 else mid = arr[pivotpos]; } }
分治与递归的结合-------快速排序