快速排序算法可以分为以下步骤
1）识别枢轴。
2）基于枢轴的链接列表。
3）将链接的列表递归分为2个部分。
现在，如果我总是选择最后一个元素作为枢轴，则识别枢轴元素（第一步）需要O（n）时间。
识别枢轴元素后，我们可以存储其数据并将其与所有其他元素进行比较以识别正确的分区点（第二步）。在我们存储枢轴数据时，每个比较将花费O（1）时间，并且每个交换需要O（1）时间。因此总共需要o（n）元素的时间。
所以复发关系是
t（n）= 2t（n/2） n是o（nlogn），与链接列表中的合并相同。
为什么合并排序优于快速排序链接列表？
因此，复发关系是... o（nlogn）
最坏的阵列上的QuickSort是O（n^2），例如，每个递归级别仅将最大分区的大小降低1或2（如果在任何一个分区中不包含枢轴）。
为什么合并排序优于快速排序链接列表？
它的速度要快得多，尤其是自下而上的合并排序，可以消除列表的扫描以拆分它们。取而代之的是，它使用一个小的（26至32）内部数组的指示器或对节点（或列表少数数组）的引用，将节点合并到数组中，然后将数组合并以创建排序的列表。Wiki文章包括伪代码：
https://en.wikipedia.org/wiki/merge_sort#bottom-up_implementation_using_using_lists
现在，如果我总是将最后一个元素选择为枢轴，则识别枢轴 元素（第一步）需要O（n）时间。
实际上需要O（1）时间。但是无论如何，一个常见的误解W.R.T.Quick-Sort是您可以选择预定义元素作为枢轴而不是随机的想法。您可能不会。
Quick-Sort Works 在O（n log（n））中平均，但最糟糕的案例为o（n^2）。现在，当随机选择枢轴并在大型集上执行算法时，实际上O（n log（n））就是您在实践中获得的。但是，如果您选择一个预定义的枢轴，则根据数据的模式，您可以轻松地击中最坏情况。认为源数据是不是随机的，它来自某些源，并显示出一些模式。
例如，如果您将最后一个元素作为枢轴，而您的源数据在情况下已经以相反的顺序进行排序 - 那么，您肯定会得到o（n的退化情况）^2）。
关于您的问题为什么通常不用于链接列表。原因（IMHO）是对于列表，合并选手是首选的方法。它保证了O（n log（n））的最坏情况。通常不用于数组，因为在数组中需要分配额外的内存，但是链接列表并非如此。