2. 考研
  3. 下列内部排序算法中，其比较次数(或交换次数)与序列初态无关的算法是( )。

下列内部排序算法中，其比较次数(或交换次数)与序列初态无关的算法是( )。

admin2023-02-06  54
问题 下列内部排序算法中，其比较次数(或交换次数)与序列初态无关的算法是(    )。
选项 A、快速排序
B、直接插入排序
C、二路归并排序
D、冒泡排序
答案C
解析 此题考查的知识点是各类排序算法的思想。
冒泡排序方法就是自底向上检查这个序列，若两个相邻的元素的顺序不对，则交换。直到所有元素处理完为止。与序列初态有关，D错。
直接插入排序思想是假设待排序的记录存放在数组R[n+1]中，排序过程中的某一时刻，R被分成两个子区间[R[1]，R[i-1]]和[R，R[n]]，其中，前个子区间是已排好序的有序区；后个子区间是当前未排序的无序区。直接插入排序的基本操作是将当前无序区的第i个记录R插入到有序区中的适当位置，使得R[1]到R变为新的有序区。首先比较R和R[i-1]，如果R[i-1]≤R，则R[1..i]已排好序，第i遍处理就结束了；否则交换R与R[i-1]的位置，继续比较R[i-1]和R[i-2]，直到找到某一个位置j(1≤j≤i-1)使得R[j]≤R[j+1]时为止。与序列初态有关，B错。
快速排序是通过基准元素v把表(文件，数据集合)划分成左、右两部分，使得左边的各记录的关键字都小于v；右边的各记录的关键字都大于等于v；重复该过程直到排好序。与序列初态有关，A错。
二路归并是首先把每个记录看成是一个有序序列，共n个，将它们两两合并成[n／2]个分类序列，每个序列长度为2(当n为奇数时，最后一个序列长度为1)；对[n／2]个分类序列，再两两归并在一起；如此进行，直到归并成一个长度为n的分类序列为止。与序列初态无关，所以选C。
转载请注明原文地址:https://www.kaotiyun.com/show/YIwD777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

相关试题推荐
随机试题
最新回复(0)