下列排序算法中，元素的移动次数与关键字的初始排列次序无关的是 （） 。
元素的移动次数与关键字的初始排列次序无关的是：基数排序
元素的比较次数与初始序列无关是：选择排序
算法的时间复杂度与初始序列无关的是：选择排序
发表于 2018-07-27 10:19:42
回复(0)
移动次数：较为有序的序列中一些元素可能就在其最终位置上，快排、插入、冒泡，都可能在比较过程中不移动这些元素。但是基数排序，每个元素都要先到顶堆，然后再到相应位置上，所以不论原来序列是否有序，都要变更元素的位置，所以和初始排列顺序无关。
比较次数：①插入排序：如果当前元素和前面最后一个元素比较结果是不用往前面插入，那么前面排列好的元素就不用再和当前元素比较了，所以顺序情况下，插入排序的比较次数降为O(n-1)。②冒泡排序：改进的冒泡排序，在内循环和外循环之间设立一个flag = false，如果在一次内循环结束后发现flag还是false，表明已经排好了序列，所以比较次数最好的情况可以降为O(n - 1)。但一般的冒泡排序还是要比较O(n^ 2)次。③快排:有序情况下，快排会退化成冒泡排序，比较次数增加。④选择排序：不论是否有序，都比较n ^ 2次。
时间复杂度不变化的：选(n ^ 2)、堆(nlgn)、基(n * k)（计:n + k）、归（nlgn ）。
堆排序：维护堆性质O(lgn)，共n - 1次调用。
归并：二分lgn，合并n。
发表于 2020-08-07 10:55:09
回复(0)
元素的移动次数与关键字的初始排列次序无关的是基数排序。比较次数与初始序列无关的是选择排序。时间复杂度与初始序列无关的是选择排序。
发表于 2022-01-11 00:01:23
回复(0)
由题中“失配 s[i] ≠ t[j] 时， i=j=5 ” ，可知题中的主串和模式串的位序都是从 0 开始的（要注意灵活应变）。 按照 next 数组生成算法，对于 t 有：
编号 | 0 | 1 | 2 | 3 | 4 | 5 |
t | a | b | a | a | b | c |
next | - 1 | 0 | 0 | 1 | 1 | 2 |
依据 KMP 算法“当失配时， i 不变， j 回退到 next[j] 的位置并重新比较”，当失配 s[i] ≠ t[j] 时，i=j=5 ，由上表不难得出 next[j]=next[5]=2 （位序从 0 开始）。从而最后结果应为： i=5 （ i 保持不变）， j=2 。
发表于 2016-12-13 18:14:56
回复(3)
由题中“失配 s[i] ≠ t[j] 时， i=j=5 ” ，可知题中的主串和模式串的位序都是从 0 开始的（要注意灵活应变）。 按照 next 数组生成算法，对于 t 有：
编号 | 0 | 1 | 2 | 3 | 4 | 5 |
t | a | b | a | a | b | c |
next | - 1 | 0 | 0 | 1 | 1 | 2 |
依据 KMP 算法“当失配时， i 不变， j 回退到 next[j] 的位置并重新比较”，当失配 s[i] ≠ t[j] 时， i=j=5 ，由上表不难得出 next[j]=next[5]=2 （位序从 0 开始）。从而最后结果应为： i=5 （ i 保持不变）， j=2 。（来自王道论坛）
发表于 2016-12-01 18:37:35
回复(1)
问题信息
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
