首页 > 试题广场 >

排序方法中，关键字比较的次数与记录的初始排列无关的是( ）

[单选题]

排序方法中，关键字比较的次数与记录的初始排列无关的是( ） 

  • 简单选择排序
  • 快速排序
  • 直接插入排序
  • Shell排序
添加回答
推荐
白驹之过隙头像 白驹之过隙
选A。
  • 选项A：简单选择排序，在待排序的数组中选出最小（或最大）的与第一个位置的数据交换，然后在剩下的待排序数组中重复找出剩余序列的最大（或最小）。和初始序列排序无关。
  • 选项B：快速排序，是基准值的正确选择，最坏时间复杂度为O(n2)，只有基准值处于每次的中间位置才是时间复杂度最好的。所以和初始序列排列有关。
  • 选项C：直接插入排序，将待排序的序列插入到有序序列中，最好的时间复杂度是O(n)即整个序列有序，反之逆序的情况下时间复杂度为O(n2)所以和初始排列有关。
  • 选项D：Shell排序，划分子序列做直接插入排序，所以和初始排列有关。
编辑于 2019-10-28 14:29:44 回复(0)
Ryanww头像 Ryanww
A 
选择排序算法 选择排序算法是当前元素与序列最小元素交换，每个关键字的比较次数与初始状态无关，与元素初始位置无关
快速排序是冒泡排序的改进，通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。该算法的复杂度和元素交换次数都与初始状态有关。
希尔排序是插入排序的改进，希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。初始状态也是影响到关键字的比较次数。

发表于 2019-10-25 18:39:49 回复(0)
dragonlogin头像 dragonlogin
答案选A

关键字的比较次数可以理解为时间复杂度。
与初始序列是否有关，可以理解为最好最坏的时间复杂度是否一样。

A，简单选择排序：最好：O(n^2)     最坏：O(n^2)
B，快速排序：       最好：O(nlogn)   最坏： O(n^2)
C,  插入排序：        最好：O(n)        最坏：O(n^2)
D,  shell排序           最好：O(n)         最坏：O(n^2)
这种类型的题，找个排序的博客一看，什么时间复杂度， 稳定性，排序算法的思想，一搞定，
遇到这种题都是秒做。



发表于 2019-10-28 11:49:30 回复(1)
牛客699689876号头像 牛客699689876号
B为什么不对 快排的logN和关键字比较次数无关吧
发表于 2023-08-22 02:25:53 回复(0)
Wilbur.头像 Wilbur.
简单选择排序每轮都是一一比较选出最大或者最小的
发表于 2022-08-22 07:27:06 回复(0)
是个呆雁头像 是个呆雁
选A，希尔排序和冒泡排序都属于插入排序，它们通过数据元素的交换来逐步消除线性表中的逆序，所以关键字比较的次数与记录的初始排列次序有关。而选择排序是指扫描整个线性表，从中选出最小的元素，将它交换到表的前面，然后对剩下的字表采用同样的办法，所以关键字比较的次数与记录的初始排列次序无关。
发表于 2019-10-25 15:52:24 回复(0)
提交观点

问题信息

排序
上传者：zsw3
难度：
6条回答 8304浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号