单选题 适中
#21114

为了正确实现快速排序,下面横线上的代码应为( )。 void qsort ( vector < int > & arr , int left , int rig…

为了正确实现快速排序,下面横线上的代码应为( )。

void qsort(vector<int>& arr, int left, int right) {
	int i, j, mid;
	int pivot;
	
	i = left;
	j = right;
	mid = (left + right) / 2; // 计算中间元素的索引
	pivot = arr[mid]; // 选择中间元素作为基准值
	
	do {
		while (arr[i] < pivot) i++;
		while (arr[j] > pivot) j--;
		if (i <= j) {
			swap(arr[i], arr[j]); // 交换两个元素
			i++; j--;
		}
	} ________________________________; // 在此处填入代码
	if (left < j) qsort(arr, left, j); // 对左子数组进行快速排序
	if (i < right) qsort(arr, i, right); // 对右子数组进行快速排序
}
未登录也能判分,登录后才会记录
答案与解析
正确答案:D
解析

快速排序的分区过程中,我们使用两个指针i和j分别从左到右和从右到左遍历数组,将小于基准值的元素放到基准值的左边,大于基准值的元素放到右边。

具体的分区过程如下:

首先选择一个基准值pivot,通常选择中间元素arr[mid]。

使用两个指针i和j,分别从数组的左右两端开始向中间移动。

i从左向右移动,直到找到一个大于或等于pivot的元素。

j从右向左移动,直到找到一个小于或等于pivot的元素。

如果i <= j,则交换arr[i]和arr[j],然后i向后移动一位,j向前移动一位。

重复步骤2和3,直到i大于j,此时所有小于等于pivot的元素都在pivot的左边,所有大于等于pivot的元素都在pivot的右边。

在填写横线上的代码时,应该使用while (i <= j),因为分区过程应该持续进行直到i超过j,这样保证了整个分区过程的完成。