为什么我们不在链表上使用快速排序?

所以递归关系是。。。O(非登录)

数组上最坏情况下的快速排序是O(n^2),例如,每一级递归只会将最大分区的大小减少1或2(如果两个分区中都不包括pivot,则为2)。

为什么链表的合并排序优于快速排序?

它的速度要快得多,尤其是自底向上的合并排序,它消除了扫描列表以分割列表的过程。相反,它使用一个小型(26到32)的内部指针数组或节点引用(或小型列表数组),将节点合并到数组中,然后合并数组以创建排序列表。Wiki文章包括伪代码:

https://en.wikipedia.org/wiki/Merge_sort#Bottom-up_implementation_using_lists

现在,如果我总是选择最后一个元素作为轴,那么识别轴 元素(第一步)需要O(n)时间。

快速排序工作 平均而言 在O(N log(N))中,但最坏的情况是O(N^2)。现在,当随机选择轴并在大集合上执行算法时,实际上,在实践中得到的是O(N log(N))。然而,如果您选择了一个预定义的轴心,那么,根据数据的模式,您很容易遇到最坏的情况。 认为源数据是 不 随机性,它来自于某种来源,并表现出某种模式。

以防万一 已经按相反顺序排序了-那么你肯定会得到O(N^2)的退化情况。

关于您的问题,为什么快速排序通常不用于链接列表。原因(IMHO)是,对于列表,合并排序是首选方式。它保证了O(N log(N))的最坏情况性能。它通常不用于数组,因为对于数组,它需要分配额外的内存,但对于链表,情况并非如此。