单选题
适中
#20467
考虑以下C++代码实现的快速排序算法,将数据从小到大排序,则横线上应填的最佳代码是?( ) int partition ( vector < int > & a…
考虑以下C++代码实现的快速排序算法,将数据从小到大排序,则横线上应填的最佳代码是?( )
答案与解析
正确答案:B
解析
快速排序是一种分治算法,其基本步骤如下:
选择基准:从数组中选择一个元素作为基准(通常选择最后一个元素)。
分区:重新排列数组,使得所有比基准小的元素放在基准前面,所有比基准大的元素放在基准后面。分区完成后,基准就位于其最终排序后的正确位置。
递归排序:递归地对基准前后的子数组进行快速排序。
在分区过程中:
i初始化为low - 1,表示小于基准的区域最初为空。
j从low到high - 1遍历数组。
如果arr[j]小于pivot,则i增加1,并将arr[i]和arr[j]交换。这样,arr[i]现在是一个小于pivot的元素。
本题答案为选项B。