问答题

【说明】下面是一个用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; } }