首页 > 试题广场 >

题目来源于王道论坛 下列排序方法中,若将顺序

[单选题]
题目来源于王道论坛

下列排序方法中,若将顺序存储更换为链式存储,则算法的时间效率会降低的是

Ⅰ.插入排序 Ⅱ.选择排序 Ⅲ.起泡排序 Ⅳ.希尔排序 Ⅴ.堆排序



  • 仅Ⅰ、Ⅱ
  • 仅Ⅱ、Ⅲ
  • 仅Ⅲ、Ⅳ
  • 仅Ⅳ、Ⅴ
推荐

解析:

插入排序、选择排序、起泡排序原本时间复杂度是O(n2),更换为链式存储后的时间复杂度还是O(n2)。希尔排序和堆排序都利用了顺序存储的随机访问特性,而链式存储不支持这种性质,所以时间复杂度会增加,因此选D

发表于 2018-06-16 10:56:38 回复(2)
这题实际上问的是涉及的是元素排序的过程,插入,选择,起泡都是相邻元素之间的操作 而shell和堆排序涉及到非相邻元素的交换,由于链表不支持随机访问,因而非相邻元素之间交换困难,导致算法复杂度上升
发表于 2019-01-11 19:55:00 回复(8)
插入排序、选择排序、起泡排序的时间复杂度为O(n2),都是顺序比较元素,与存储方式无关。
原因顺序比较元素,不存在跨越式比较,比如插入排序,每插入一个元素,顺序与已排序元素比较;比如选择排序,每选择一个元素,顺序与剩下的元素比较。
希尔排序和堆排序都存在元素的跨越式比较,都利用了顺序存储的随机访问特性,而链式存储不支持这种性质,所以时间复杂度会增加。
发表于 2021-02-28 15:48:13 回复(0)
凡利用了顺序访问特性的都会被影响
发表于 2019-12-16 20:07:15 回复(0)
前三张种算法比较n2,执行n2,改成链表后比较n2,执行kn次,效率提高,故不选
发表于 2021-09-27 11:27:44 回复(0)
由于希尔排序不支持链表随机存取的特特点,因此要访问非相邻元素则是需要非常大的时间和空间,因而存在时间复杂度的问题
发表于 2021-07-28 21:46:11 回复(0)
其实就是找不稳定的算法
发表于 2022-06-05 14:53:23 回复(0)
求大神分析分析
发表于 2020-07-14 09:46:47 回复(0)
楼上17shou正解。
发表于 2019-10-15 13:44:44 回复(0)
貌似答案不太对
发表于 2018-12-02 20:40:09 回复(1)