阅读下列C程序和程序说明,将应填入(n)处的字句写在对应栏内。 【说明】下面是一个用C编写的快速排序

Question

阅读下列C程序和程序说明，将应填入(n)处的字句写在对应栏内。

【说明】下面是一个用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( (1) ); //递归排序左子区间

quieksort(a,i+1 ,right); //递归排序右子区间

}

}

void median3 (int a[], int left, int right)

{ int mid=(2);

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;

(3) {

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){(4);a[i]=pivot;}

quicksoft ((5)); //递归排序左子区间

left = i+1;

}

}

Answer 1

正确答案：(1)alefti-1 (2)(left+right+1)/2 (3)while(leftright) (4)a[right)=a[i] (5)aleft i-1
(1)a，left，i-1 (2)(left+right+1)/2 (3)while(leftright) (4)a[right)=a[i] (5)a，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(leftright)
循环直到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元素。