单链表排序时间复杂度最小的是哪种排序方法?

来源：百度知道 编辑：UC知道 时间：2024/06/16 14:51:01
有两种方式:
1,移动各个结点的next指针
2,交换各个结点的data域

什么排序的时间复杂度最小?
或者什么算法的时间空间复杂度最优?
如果通过更改next的话，不管采用什么算法，对于时间复杂度，我感觉都会是O(n^2)吧，因为你每次遍历总是从头接点开始，没办法往回遍历。

用快速排序时间空间复杂度较低
时间复杂度O(nlog2n) 空间复杂度 O(1)
时间复杂度最低的是堆排序，但空间复杂度会增加O(logn)
还有一点我要说明 各种算法 追求时间复杂度低 就会必然带来空间复杂度的攀升 追求空间复杂度低 也必然会导致时间复杂度上升
就是说没有哪一种算法是时间复杂度和空间复杂度都最低的 就像鱼与熊掌不能兼得一样
既然是单链表 我还是建议你用快速排序 代码也容易些 不会可以在网上搜索 我也可以提供 如果你需要的话

我用后一种，觉得速度会快，
但是实际上是第一种快，因为第一种并没有开辟新的空间。

c c++

一直舍不得 指针，是因为 指针 操作的快速性。。。