partition函数的具体扩展如下：
说明：入口参数:集合A（m:q）的头m和尾后一个位置q
出口参数：划分元素A[m]在集合A排序后的集合中的位置
6
四、源程序及实验结果
程序代码如下：
#include
int A[1024]; //A[1024]是全程数组，其中存放待分类的元素void interchange(int i,int j) //将A[i]与A[j]换位 { int t; t=A[i]; A[i]=A[j]; A[j]=t;
7
}
int partition(int m,int p) //用划分元素A[m]划分集合A(m:p-1),并返回划分元素定位后的位置 //划分元素定位后其左边的元素不大于它，其右边的元素不小于它 { int i,v;
v=A[m]; //记下划分元素的值
i=m; //记下划分元素的起始位置
while(1) //查找划分元素在排序后的集合中的位置 { do //由左向右查找不小于划分元素的元素A[i] {
i++;
}while(A[i] do //由右向左查找不大于划分元素的元素A[p] { p--; }while(A[p]>v); if(i else break; } A[m]=A[p]; //划分元素最终定位在集合A中p处 A[p]=v; return p; } void quicksort(int p,int q) //快速分类（本算法为递归算法） /*将全局数组A(1:n)中的元素A[p],.....,A[q]按递增的方式分类，认为A[n+1]已被定义，且不小于A(p:q)的所有元素，即A[n+1]为正无穷大（在主函数令正无穷大为1000） */ { int j; if(p { j=q+1; //此时j为划分元素的起始位置 j=partition(p,j); //此时j存放的是划分元素应在排序后的集合中的位置 //依次对由划分元素划分出的两个子集合进行快速分类 quicksort(p,j-1); quicksort(j+1,q); } } void main() { int i,n; //n中存放待排序元素的个数 printf(\ scanf(\ //输入待排序元素的个数 printf(\ for(i=1;i<=n;i++) //输入待排序的各个元素的值，并存放到集合A中 8 scanf(\ A[n+1]=1000; quicksort(1,n); //调用快速分类算法对数组A（1：n）进行归并排序 for(i=1;i<=n;i++) //输出进行快速排序后的集合A printf(\ getch(); } 运行结果如下图：(运行结果与理论结果一致) 五、结果分析 运行源程序后，先输入待排序元素的个数，回车。再分别输入元素的值序列，回车，就会显示按升序排列的元素值序列。不难看出，运行结果与理论结果一致。 记最坏情况下的元素比较次数是Cw(n)；PARTITION一次调用中的元素比较数是p-m+1，故每级递归调用上，元素的比较次数等于该级所处理的待分类元素数。 最坏情况下，每级递归调用的元素总数仅比上一级少1，故Cw(n)是r由n到2的累加和。 即：Cw(n)=Ο(n2) 9 上机实验三 一、 实验题目 贪心算法求背包问题 二、算法介绍 1、将若干物品装入背包，装入情况有三种：部分装入、全部装入和未装入； 2、量度标准：物品效益集合和容量集合分别按单位容量的效益增量的降序排列 3、排序方法：快速排序 三、程序流程图 说明： 存放物品的数目的变量n，数组A[1024]存放待分类元素，数组X[1024]存放解向量，数组W[1024]存放各物品的容量，数组P[1024]存放各物品的效益， 以上变量均是全局变量。 贪心算法greedy-knapsa的具体扩展如下： 说明：入口参数:背包容量m 10