题17
题目
Q:【2017 统考真题】下列排序算法中, 若将顺序存储更换为链式存储, 则算法的时间效率会降低的是 ( ).
I. 插入排序
II. 选择排序
III. 冒泡排序
IV. 希尔排序
V. 堆排序
A. 仅 I、II
B. 仅 II、III
C. 仅 III、IV
D. 仅 IV、V
分析
A:链式存储主要影响的是无法O1查询，也就说如果需要做到O1的查询某个元素来进行操作，显然效率会受到影响
插入排序是维护一个有序序列，然后每次从无序序列中取出一个元素，插入到有序序列中的合适位置
选择排序，需要进行选择，然后进行交换，链式存储会影响查询
希尔排序，需要通过下标来实现分组，但是链式存储无法实现O1的元素定位
堆排序应该不受影响，因为堆排序是通过树结构来实现排序的，不需要O1的查询
我上面这个分析是错误，因为数组实现的堆里面有一个操作是a[1]=a[cnt++]这就需要O1的查询得到最后一个元素的位置,如果是链式的，这无法做到
解
D
在顺序存储的条件下,插入排序、选择排序、冒泡排序的时间复杂度都是
希尔排序和堆排序都利用了顺序存储的随机访问特性,而链式存储不支持这种性质, 所以时间复杂度会增加。