GESP-C++五级 题库
归并排序算法的基本思想是( )。(2023.9C++五级)
将数组分成两个子数组,分别排序后再合并。
随机选择一个元素作为枢轴,将数组划分为两个部分。
从数组的最后一个元素开始,依次与前一个元素比较并交换位置。
比较相邻的两个元素,如果顺序错误就交换位置。
通过在数组的第一个、最中间和最后一个这3个数据中选择中间值作为枢轴(比较基准),快速排序算法可降低落入最坏情况的概率。
下面的C++代码实现归并排序。代码在执行时,将输出一次 HERE 字符串,因为merge()函数仅被调用一次。( )
分治算法将原问题可以分解成规模更小的子问题,使得求解问题的难度降低。
但由于分治算法需要将问题进行分解,并且需要将多个子问题的解合并为原问题的解,所以分治算法的效率通常比直接求解原问题的效率低。( )
归并排序算法的时间复杂度与输入是否有序无关,始终稳定为 O(n log n)。( )
归并排序无论输入数据是否有序,归并排序的时间复杂度 始终为 O(nlog?n)。这是因为:
分解阶段:将数组递归地分成两半,直到子数组长度为 1,共需 log?n 层递归。
合并阶段:每一层需要 O(n) 的时间合并两个有序子数组。
总时间复杂度:递归深度 log?n × 每层 O(n)) = O(nlog?n)。
归并排序算法体现了分治算法,每次将大的待排序数组分成大小大致相等的两个小数组,然后分别对两个小数组进行排序,最后对排好序的两个小数组合并成有序数组。( )
分治法的核心是:
分解:将问题划分为若干 相互独立且结构相同 的子问题。
解决:递归解决子问题。
合并:将子问题的解合并为原问题的解。
归并排序体现了分治算法。
快速排序和归并排序的平均时间复杂度均为 O(nlogn),且都是稳定排序。
快速排序的均摊时间复杂度为O(nlogn),归并排序的时间复杂度是稳定的O(nlogn),所以对于时间复杂度的描述是正确的,但是快速排序不是稳定排序。
归并排序和快速排序都采用递归实现,也都是不稳定排序。( )(2024.6-5)
归并排序是一种稳定的排序算法,快速排序是一种不稳定的排序算法