复制
收藏
提问
简洁
快速排序的基本思想是在待排序的n个元素中任取一个元素（通常取第一个元素）作为基准，把该元素放入最终位置后，整个数据序列被基准分割成两个子序列，所有小于基准的元素放置在前子序列中，所有大于基准的元素放置在后子序列中，并把基准排在这两个子序列的中间，这个过程称作划分。然后对两个子序列分别重复上述过程，直至每个子序列内只有一个记录或空为止。请完成程序空缺的部分，注意每个空只填写一个关键字、运算符、标识符或表达式（注意不需要空格和其他间隔符）。 int Partition(int a[],int s,int t) //划分算法 { int i=s,j=t; int tmp=a[s]; //用序列的第1个记录作为基准 while (i<j) //从序列两端交替向中间扫描,直至i=j为止 { while (j>i && a[j]>=tmp) j--; //从右向左扫描,找第1个关键字小于tmp的a[j] while (i<j && ____<tmp) i++; //从左向右扫描,找第1个关键字大于等于tmp的a[i] swap(a[j],a[i]); //将a[i]与a[j]进行交换 } a[i]=tmp; return ____; // 返回基准定位的下标 } void QuickSort(int a[],int s,int t) //对a[s..t]元素序列进行排序 { if (s____t) //序列内至少存在2个元素的情况 { int i=Partition(a,s,t); ____ (a,s,i-1); //对左子序列递归排序 QuickSort(a,i+1, ____); //对右子序列递归排序 } }
3月前
全网
文档
学术
百科
知识库
回答简洁模式
深入研究一些
快速排序算法是一种高效的排序方法，其核心思想是分治法。在给定的程序模板中，需要填写的空缺部分如下：
- 在第一个while循环中，我们需要找到第一个关键字大于等于基准值
tmp的元素，因此空缺处应填写a[i]。 - 在第二个while循环中，我们需要找到第一个关键字小于基准值
tmp的元素，因此空缺处应填写a[j]。 - 在
QuickSort函数的递归调用中，我们需要对基准值左边的子序列进行排序，因此第一个空缺处应填写QuickSort。 - 同样，在
QuickSort函数的递归调用中，我们需要对基准值右边的子序列进行排序，因此第二个空缺处应填写t。
根据上述分析，完整的程序代码如下：
int Partition(int a[], int s, int t) {
int i = s, j = t;
int tmp = a[s]; // 用序列的第一个记录作为基准
while (i < j) {
while (j > i && a[j] >= tmp) j--; // 从右向左扫描，找第一个关键字小于tmp的a[j]
while (i < j && a[i] < tmp) i++; // 从左向右扫描，找第一个关键字大于等于tmp的a[i]
swap(a[j], a[i]); // 将a[i]与a[j]进行交换
}
a[i] = tmp;
return i; // 返回基准定位的下标
}
void QuickSort(int a[], int s, int t) {
if (s < t) { // 序列内至少存在2个元素的情况
int i = Partition(a, s, t);
QuickSort(a, s, i - 1); // 对左子序列递归排序
QuickSort(a, i + 1, t); // 对右子序列递归排序
}
}
你觉得结果怎么样？