单选题
适中
#20899
考虑以下C++代码实现的归并排序算法: void merge ( int arr [ ] , int left , int mid , int right )…
考虑以下C++代码实现的归并排序算法:
对长度为 n 的数组 arr ,挑用函数 merge_sort(a, 0, n-1) ,在排序过程中 merge 函数的递归调用次数大约是( )。
答案与解析
正确答案:B
解析
merge_sort函数的作用是递归进行分治的过程,每次把序列分成两半,然后分别处理,merge函数的作用是把两个有序序列,通过双指针操作,合并为一个有序序列。merge函数的调用次数,先是两个数的合并,执行次数为n/2,然后是4个数合并,执行次数为n/4……大约为O(n)