问答题
【说明】下面是一个用C编写的快速排序算法。为了避免最坏情况,取基准记录pivot时,采用从left、right和mid=[(left+right)/2]中取中间值,并交换到right位置的办法。数组a存放待排序的一组记录,数据类型为T,left和right是待排序子区间的最左端点和最右端点。
void quicksort (int a[], int left, int right) {
int temp;
if (left<right) {
hat pivot = median3 (a, left, right); //三者取中子程序
int i = left, j = right-1;
for(;;){
while (i <j && a[i] < pivot) i++;
while (i <j && pivot < a[j]) j--;
if(i<j){
temp = a[i]; a[j] = a[i]; a[i] = temp;
i++; j--;
}
else break;
}
if (a[i] > pivot)
{temp = a[i]; a[i] = a[right]; a[right] = temp;}
quicksort({{U}} (1) {{/U}}); //递归排序左子区间
quieksort(a,i+1 ,right); //递归排序右子区间
}
}
void median3 (int a[], int left, int right)
{ int mid={{U}} (2) {{/U}};
int k = left;
if(a[mid] < a[k])k = mid;
if(a[high] < a[k]) k = high; //选最小记录
int temp = a[k]; a[k] = a[left]; a[left] = temp; //最小者交换到 left
if(a[mid] < a[right])
{temp=a[mid]; a[mid]=a[right]; a[right]=temp;}
}
消去第二个递归调用 quicksort (a,i+1,right)。 采用循环的办法:
void quicksort (int a[], int left, int right) {
int temp; int i,j;
{{U}}(3) {{/U}}{
int pivot = median3(a, left, right); //三者取中子程序
i = left; j = righi-1;
for (;; ){
while (i<j && a[i] < pivot)i++;
while (i<j && pivot <a[j]) j--;
if(i <j) {
temp = a[i]; a[j]; = a[i]; a[i]=temp;
i++; j--;
}
else break;
}
if(a[i]>pivot){{{U}} (4) {{/U}};a[i]=pivot;}
quicksoft ({{U}} (5) {{/U}}); //递归排序左子区间
left = i+1;
}
}
【正确答案】
【答案解析】[解析]
(1)a,left,i-1
递归排序左子区间,从left到i-1元素,不包括i元素。
(2)(left+right+1)/2
三者取中子程序median3(a,left,right),取基准记录pivot时,采用从left、right和 mid=[(left+right)/2]中取中间值,并交换到right位置的办法。
(3)while(left<right)
循环直到left和right相遇。
(4)a[right)=a[i]
若a[i]>pivot则让a[right]=a[i]而让a[i]=pivot;。
(5)a,left, i-1
递归排序左子区间,从left到i-1元素,不包括i元素。