单链表排序时间复杂度最小的是哪种排序方法?
o(NlogN)，虽然不是所有的高级排序算法都适用于单链表，但是还是部分适用的，比如归并排序，希尔排序，和快速排序的特定实现。
就算这些算法你统统不考虑，还有一种简单粗暴的方法：
将链表复制到数组
排序数组
将数组还原成链表
这三步的复杂度是O(n+nlogn+n)= O(nlogn)
typedef struct __LINK
{
int data;
struct __LINK *next;
} LinkNode_t;
//冒泡排序单连表, 交换值方式
bool LinkSort( LinkNode_t* &head )
{
assert( head != NULL );
bool change = true;
LinkNode_t* p = head;
LinkNode_t* pStop = head->next;
int ifirst = 0;
while ( pStop && pStop->next )
{
pStop = pStop->next;
}
LinkNode_t* pFlag = head;
while ( change )
{
change = false;
for ( p = head->next; p != pStop; p = p->next )
{
if ( p->data next->data )
{
int value = p->data;
p->data = p->next->data;
p->next->data = value;
change = true;
}
if ( p->next == pStop ) pFlag = p;
}
pStop = pFlag;
}
return true;
}
时间复杂度O(nlog2n) 空间复杂度 O(1)
时间复杂度最低的是堆排序，但空间复杂度会增加O(logn)
还有一点我要说明 各种算法 追求时间复杂度低 就会必然带来空间复杂度的攀升 追求空间复杂度低 也必然会导致时间复杂度上升
就是说没有哪一种算法是时间复杂度和空间复杂度都最低的 就像鱼与熊掌不能兼得一样
既然是单链表 我还是建议你用快速排序 代码也容易些 不会可以在网上搜索 我也可以提供 如果你需要的话
我用后一种，觉得速度会快，
但是实际上是第一种快，因为第一种并没有开辟新的空间。
给定n个数据元素,建立对应的有序单链表的时间复杂度是:
给定n个数据元素，建立对应的有序单链表的时间复杂度是：A.O(1)B.O(n)C.O(n2)[n的平方]D.O(nlog2n)正确答案：O(n2)[n的平方]
为什么单链表访问后继结点的时间复杂度为O(1),而访问前驱结点的时间复杂...
因为访问后继结点只是进行一次间接寻址的操作，这个时间是常量，自然是O(1)了，但是通过单链表当前的地址，如果要访问到其前驱，必须要从头开始顺序访问，如果链表的有n个结点，平均时间为O(n)，因此时间复杂度就是O(n)了
...单链表中,从头开始遍历,访问后继节点的时间复杂度为o(1),访问前驱...
访问后继结点只要一次间接寻址p = p->next，该步骤没有循环，时间复杂度是O(1)访问前驱节点需要从头结点开始根据链表顺序一个一个访问。该步骤有一重循环，基本运算次数与问题规模n的增长呈线性增大关系，所以时间复杂度是O(n)。如果是双向链表p = p->prior就能访问前驱节点。
...将他们合并为长度为m+n的降序链表,最坏情况下时间复杂度怎样求...
已知两个长度为m和n的升序链表将他们合并为长度为m+n的降序链表，最坏情况下时间复杂度怎样求，合并时最坏情况下，长为n的链表中前n-1个都比长为m的链表中的第一元素小，而长为n的链表中最后一元素又比长为m的链表中所有元素大。这样比较元素的次数n+m,则时间复杂度为O(m+n)...
...对于查找第i个元素的运算,顺序表的时间复杂度为(),单链表的...
B C 顺序表就相当于数组，查找的时候可以一下就找到，所以时间复杂度为：O(1)单链表查找的时候要一直找下一个结点，若要查找的元素在最后，就相当于找了n次，所以时间复杂度为：O(n)
简述顺序表和链表的优缺点及适用范围?
存储空间不连续，数据元素之间使用指针相连，每个数据元素只能访问周围的一个元素（根据单链表还是双链表有所不同）。存储密度小，因为每个数据元素，都需要额外存储一个指向下一元素的指针（双链表则需要两个指针）。要访问特定元素，只能从链表头开始，遍历到该元素，时间复杂度为 $O(n)$。在特定的数据...
单链表和循环链表操作用什么不一样?
解答：先从La的头指针开始，把指针移动到循环链表的最后一个结点，移动了La长度的结点数目，再从Lb的头指针开始把指针移动到循环链表的最后一个结点，移动了Lb长度的结点数目，最后将Lb接在La之后还形成一个循环链表，时间复杂度为O（n＋m）。（2）La、Lb都是带头结点、尾指针的单循环链表，如何实现...
在单链表中删除一个指定节点的后继的时间复杂度是多少?
时间复杂度是O(n)在一个具有n个节点的单链表中删除第i个节点算法的时间复杂度是o(n)；因最坏情况是删除最后一个结点，所以要找到最一个结点的前驱，也就要访问前n-1个结点，故算法的时间复杂度为o(n)。for（i=1;i<n;i++）;\/\/ 由于这里有一个分号，所以执行n次 for(j=1;j...
...为n的循环单链表中查找值最大的结点,其时间复杂度?求大神解答下,十 ...
对长度为n的线性表排序，在最坏情况下，有序链表查找为O(n)，循环链表中寻找最大项为O(1)，堆排序需要比较的次数为O(nlog2n)，希尔排序所需要的比较次数为O(n1.5)。
什么是链表的优缺点?
链表优点和缺点如下：优点：在插入和删除操作时，只需要修改被删节点上一节点的链接地址，不需要移动元素，从而改进了在顺序存储结构中的插入和删除操作需要移动大量元素的缺点。缺点：1、没有解决连续存储分配带来的表长难以确定的问题。2、失去了顺序存储结构随机存取的特性。
居的新开： 用快速排序时间空间复杂度较低 时间复杂度O(nlog2n) 空间复杂度 O(1) 时间复杂度最低的是堆排序,但空间复杂度会增加O(logn) 还有一点我要说明 各种算法 追求时间复杂度低 就会必然带来空间复杂度的攀升 追求空间复杂度低 也必然会导致时间复杂度上升 就是说没有哪一种算法是时间复杂度和空间复杂度都最低的 就像鱼与熊掌不能兼得一样 既然是单链表 我还是建议你用快速排序 代码也容易些 不会可以在网上搜索 我也可以提供 如果你需要的话.
三明市19177065252： 什么排序的速度(时间复杂度)最快? - ？
居的新开： 从时间复杂度看,所有内部排序方法可以分为两类.1.插入排序 选择排序 起泡排序 其时间复杂度为O(n2);2.堆排序 快速排序 归并排序 其时间复杂度为O(nlog2n).这是就平均情况而言的,如果从最好的情况考虑, 则插入排序和起泡排序的时间复杂度最好,为O(n), 而其他算法的最好情况同平均情况大致相同.如果从最坏的情况考虑,快速排序的时间复杂度为O(n2),插入排序和起泡排序虽然同平均情况相同,但系数大约增加一倍,运行速度降低一半,而选择排序、堆排序和归并排序则影响不大.总之, 在平均情况下,快速排序最快; 在最好情况下,插入排序和起泡排序最快; 在最坏情况下,堆排序和归并排序最快.
三明市19177065252： 快速排序法的平均时间复杂度和最坏时间复杂度分别是多少? - ？
居的新开： 快速排序的平均时间复杂度和最坏时间复杂度分别是O(nlgn)、O(n^2). 当排序已经成为基本有序状态时,快速排序退化为O(n^2),一般情况下,排序为指数复杂度. 快速排序最差情况递归调用栈高度O(n),平均情况递归调用栈高度O(logn),而...
三明市19177065252： 在最坏的情况下,下列排序方法中时间复杂度最小的是() - ？
居的新开：[选项] A. 冒泡排序 B. 快速排序 C. 插入排序 D. 堆排序 能不能告诉我详细的分析啊?
三明市19177065252： 在下列排序算法中,哪一个算法的时间复杂度与初始排序无关( ). - ？
居的新开： 在下列排序算法中,哪一个算法的时间复杂度与初始排序无关( ).A. 插入排序 B. 起泡排序 C. 快速排序 D. 选择排序
三明市19177065252： C语言 各常见排序法的时间复杂度 急 请简单说明 - ？
居的新开： 选择排序抄算法复杂度是O(n^2). 插入排序是O(n^2) 快速排序快速排序是不稳2113定的.5261最理想情况算法时间复杂度O(nlog2n),最坏4102O(n^2). 堆排序算法时间复杂度O(nlogn). 归并1653排序的时间复杂度是O(nlog2n).
三明市19177065252： 数据结构中排序方法有多少种 - ？
居的新开： 1、插入排序(直接插入排序和希尔排序) 2、选择排序(直接选择排序和堆排序) 3、交换排序(冒泡排序和快速排序) 4、归并排序 5、基数排序 直接插入排序:逐个将后一个数加到前面的排好的序中.在直接插入排序过程中,对其中一个记...
三明市19177065252： 在排序算法中,哪个排序算法的时间复杂度最差?为什么?？
居的新开： 这个不一定,要看数据内容.如果是特殊数据会导致一些算法退化.综合来看应该是基数最快,选择最慢吧(你说的选择是冒泡排序吧)
三明市19177065252： 【讨论】哪种排序算法的平均复杂性最优? - ？
居的新开： 快速排序, 空间复杂度O(1) 时间复杂度最好为O(Log(n)) 缺点为基本有序时时间复杂度为O(n) 但他速度快,所以适合大多数场合,尤其是数据量大时
