排序在各种场合经常被用到。
快速排序是十分常用的高效率的算法。
其思想是:先选一个“标尺”,
用它把整个队列过一遍筛子,
以保证:其左边的元素都不大于它,其右边的元素都不小于它。
这样,排序问题就被分割为两个子区间。
再分别对子区间排序就可以了。
下面的代码是一种实现,请分析并填写划线部分缺少的代码。
#includevoid 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(i x); if(i>=j) break; swap(a,i,j); } #########(11);//填空位置 return j;}void quicksort(int a[], int p, int r){ if(p
注意:只填写缺少的内容,不要书写任何题面已有代码或说明性文字。
C/C++组 答案4 (11分)
看partition函数,首先让i=p,然后循环里,我们发现直接把p位置空过去了,所有交换的ij中都是p后边的位置,p处的值才是比较基准,i最后要么到达r+1,要么就是所存值比基准大,j要么是到了p位置,要么所存值比基准小,最后交换j处的值和基准即可。