程序填空题（题中【】处有缺失，请分析算法将其补充完整。） 1. 以下是快速排序算法，它是基于分治策略的一种排序算法。 int Partition(int a[], int p, int r) { int i = p, j = r + 1; Type x=a[p]; while (【1】) { while (a[++i]<x && i<r); while (a[- -j]>x); if (【2】) break; Swap(a[i], a[j]); } a[p] = a[j]; a[j] =【3】; return j; }

&& i<r) i++; // 找到第一个大于等于x的元素
while (a[j]>x) j--; // 找到第一个小于等于x的元素
if (i<j) { // 如果i<j，交换a[i]和a[j]
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
else break; // 如果i>=j，退出循环
}
a[p] = a[j]; // 将a[j]放到a[p]的位置
a[j] = x; // 将x放到a[j]的位置
return j; // 返回j
}

void QuickSort(int a[], int p, int r) {
if (p<r) {
int q = Partition(a, p, r); // 划分
QuickSort(a, p, q-1); // 递归排序左子数组
QuickSort(a, q+1, r); // 递归排序右子数组
}
}

2. 以下是归并排序算法，它是基于分治策略的一种排序算法。 void Merge(int a[], int p, int q, int r) { int n1 = q-p+1; int n2 = r-q; int L[n1+1], R[n2+1]; for (int i=0; i<n1; i++) L[i] = a[p+i]; for (int i=0; i<n2; i++) R[i] = a[q+i+1]; L[n1] = INT_MAX; R[n2] = INT_MAX; int i = 0, j = 0; for (int k=p; k<=r; k++) { if (L[i]<=R[j]) { a[k] = L[i]; i++; } else { a[k] = R[j]; j++; } } } void MergeSort(int a[], int p, int r) { if (p<r) { int q = (p+r)/2; MergeSort(a, p, q); MergeSort(a, q+1, r); Merge(a, p, q, r); } }

3. 以下是堆排序算法，它是基于堆的数据结构的一种排序算法。 void MaxHeapify(int a[], int i, int n) { int l = 2*i; int r = 2*i+1; int largest = i; if (l<=n && a[l]>a[largest]) largest = l; if (r<=n && a[r]>a[largest]) largest = r; if (largest!=i) { int temp = a[i]; a[i] = a[largest]; a[largest] = temp; MaxHeapify(a, largest, n); } } void BuildMaxHeap(int a[], int n) { for (int i=n/2; i>=1; i--) { MaxHeapify(a, i, n); } } void HeapSort(int a[], int n) { BuildMaxHeap(a, n); for (int i=n; i>=2; i--) { int temp = a[1]; a[1] = a[i]; a[i] = temp; MaxHeapify(a, 1, i-1); } }