【排序算法】数据存储在链表里，分析三个选择排序算法

[slogeor]

Q：如果数据存储在链表里，冒泡排序、插入排序、选择排序这三个算法还能工作吗？时间复杂是多少？空间复杂度是多少？

A：对于这个问题，应该有个大前提，是否允许修改链表的节点 value 值，还是只能改变节点的位置。一般而言，考虑只能改变节点位置。

冒泡排序相比于数组实现，比较次数一致，但交换时操作更复杂

插入排序，比较次数一致，不需要再有后移操作，找到位置后可以直接插入，但排序完毕后可能需要倒置链表

选择排序比较次数一致，交换操作同样比较麻烦。

综上，时间复杂度和空间复杂度并无明显变化。