（4） 快速排序

排序在各种场合经常被用到。

快速排序是十分常用的高效率的算法。

其思想是：先选一个“标尺”， 用它把整个队列过一遍筛子，

以保证：其左边的元素都不大于它，其右边的元素都不小于它。

这样，排序问题就被分割为两个子区间。 再分别对子区间排序就可以了。

这样，排序问题就被分割为两个子区间。 再分别对子区间排序就可以了。

下面的代码是一种实现，请分析并填写划线部分缺少的代码。

#include

void swap(int a[], int i, int j) { int t = a[i]; a[i] = a[j]; a[j] = t; }

int partition(int a[], int p, int r) { int i = p; int j = r + 1; int x = a[p]; while(1) { while(ix); //一样的，一直左移直到小于x时 if(i>=j) break; //如果一直移动到了相交的区间，说明这个区间内都是由小到大的，就直接退拉！不用交换啦！ swap(a,i,j); //有的话呢，就交换，这样保证了左小右大。 } ______________________; return j; }

void quicksort(int a[], int p, int r) { if(p

int main() { int i; int a[] = {5,13,6,24,2,8,19,27,6,12,1,17}; int N = 12; quicksort(a, 0, N-1); for(i=0; i

题解：快速排序。这里是单步快排。就是将一堆数按照某个数作为基准数分成左右两堆 swap(a,p,j)，因为这时候的j是已经不大于了x的，p这个位置要放该区间的最小值，j满足，换过去。

（5） 抽签

X星球要派出一个5人组成的观察团前往W星。 其中：

A国最多可以派出4人。 B国最多可以派出2人。 C国最多可以派出2人。 ....

那么最终派往W星的观察团会有多少种国别的不同组合呢？

下面的程序解决了这个问题。

数组a[] 中既是每个国家可以派出的最多的名额。 程序执行结果为： DEFFF CEFFF CDFFF CDEFF CCFFF CCEFF CCDFF CCDEF BEFFF BDFFF BDEFF BCFFF BCEFF BCDFF BCDEF ....

(以下省略，总共101行)

#include #define N 6 #define M 5

#define BUF 1024

void f(int a[], int k, int m, char b[]) { int i,j; if(k==N) { b[M] = 0; if(m==0) printf(\ return; } for(i=0; i<=a[k]; i++) { for(j=0; j

int main() { int a[N] = {4,2,2,1,1,3}; char b[BUF]; f(a,0,M,b); return 0; }

仔细阅读代码，填写划线部分缺少的内容。

注意：不要填写任何已有内容或说明性文字。

题解：

这个题目是这样的，对于f(int a[],int k,int m,char b[])。

a[] 是每个国家的最多指派人数,k表示当前是哪个国家,m表示还需要派送几个人(可以为负数).b表示已经派送的人的字符串。

所以这个题目在递归中间的的 第一个循环表示从0~a[i]中让i国选择指派人数，内循环只是向b[]记录的过程。

所以答案是f(a,k+1,m-i,b). 因为这里i = j .应该 f(a,k+1,m-j,b)也可以。