資料結構›Ch7 搜尋與排序第 46 題/共 76 題
46. Quicksort、Hoare Partition、C
#DS-07-046易QuicksortHoare PartitionC
題組題幹(本題:⑥,共 3 小題)點擊展開
The following code is a C implementation of a sorting algorithm:
void FSort(int* a, int left, int right)
{
if (left < right) {
static int c = 0;
int i = left, j = right + 1;
int d = a[left];
do {
do i++; while (a[i] < d);
do j--; while (a[j] > d);
if (i < j) {
int z = a[i]; a[i] = a[j]; a[j] = z;
}
} while (i < j);
int z = a[left]; a[left] = a[j]; a[j] = z;
printf("c=%d\n", ++c);
FSort(a, left, j - 1);
FSort(a, j + 1, right);
}
}
Assume that we want to use this function to sort a 10-element array m, given by
int m[] = { 3,5,9,8,2,0,4,1,6,7 };
Which of the following input array will result in the most number of calls to FSort?
📄 交大113
▤完整推導請見《WH 資工筆記 · 資料結構》Ch7 搜尋與排序