《计算机算法设计与分析》习题及答案

。Рint Partition(SqList &L,int low,int high) //算法10.6(b) Р{//交换顺序表L中子表L.r[low..high]的记录,枢轴记录到位,并返回其所在位置,Р //此时在它之前(后)的记录均不大(小)于它.Р int pivotkey;Р L.r[0]=L.r[low]; //用子表的第一个记录作枢轴记录Р pivotkey=L.r[low].key; //枢轴记录关键字Р while (low<high) //从表的两端交替地向中间扫描Р {while (low<high&&L.r[high].key>=pivotkey) --high;Р L.r[low]=L.r[high]; //将比枢轴记录小的记录移到低端Р while (low<high&&L.r[low].key<=pivotkey) ++low;Р L.r[high]=L.r[low]; //将比枢轴记录大的记录移到高端Р }Р L.r[low]=L.r[0]; //枢轴记录到位Р return low; //返回枢轴位置Р}Рvoid QSort(SqList &L,int low,int high)Р{//对顺序表L中的子序列L.r[low..high]作快速排序Р int pivotloc;Р if (low<high) //长度>1Р {pivotloc=Partition(L,low,high); //将L.r[low..high]一分为二Р QSort(L,low,pivotloc-1); //对低子表递归排序,pivotloc是枢轴位置Р QSort(L,pivotloc+1,high); //对高子表递归排序Р }Р}Рvoid QuickSort(SqList &L)Р{//对顺序表L作快速排序Р QSort(L,1,L.length); }