数据结构-建立有序单链表的最低时间复杂度

Question

经常看到一个问题：
给定一个长度为n的一维数组，以它为基础建立一个有序单链表的最低复杂度是多少。

我的想法是：只要数组的最大值可以接受，我就先用桶排，打破交换排序的极限，O（n），然后再头插或者尾插，保证有序，也是O（n）

想问一下大家怎么想。

Answer 1

这个确实是依赖你的排序算法，如果排序的复杂度小于O(n)则最终复杂度为O(n)，否则就是排序算法的复杂度。
另外，你有没有考虑过，如果数组的元素不能用桶排序的情况。