链表边插入边排序的效率高，还是插完所有再顺序排序效率高？

Question

链表边插入边排序的效率高，还是插完所有再顺序排序效率高？

Answer 1

1. 边插入边排序时间复杂度为O(n^2)，插完再排不是很好，因为在链表上排序无法实现随机访问，许多高效排序算法无法在链表上应用。
2. 建议先排序再插入，可以选择快速排序、归并排序等效率较高的算法。

Answer 2

1. 边插入边排序：

   * 每次插入的复杂度是O(log n)
   * 总复杂度自然就是O(nlog n)

2. 先插入后排序：

   * 不用说了...都知道O(nlogn)
   

所以从算法角度的话是一样的。

不过边插入边排序的话一般肯定不会傻傻的单纯用一个普通链表。如果考虑构建一个堆之类的数据结构，构建的复杂度是有可能到O(n)的