我进行了一些测试，发现快速排序实际上运行得越慢，列表排序越多，这是相当违反直觉的！我已经阅读了维基百科上的快速排序算法，但我不太明白为什么排序越多的列表需要的时间越长。任何帮助，将不胜感激！
问问题
397 次
2 回答
3
非随机快速排序通常会选择第一个元素作为枢轴元素；当列表已经排序时，这将导致列表被拆分为一个空的左侧列表和一个包含n-1 个元素的右侧列表。每次递归调用都会发生相同的行为，总运行时间将为n + n-1 + n-2 + ... + 1 = O(n^2)。
于 2013-05-16T12:58:04.567 回答
1
您指的是 QuickSort 的一个众所周知的问题。解决此问题的一种方法是使用第一个元素以外的元素作为枢轴元素。
这个 StackExchange 条目总体上对 QuickSort 有很好的描述：https ://cs.stackexchange.com/questions/3/why-is-quicksort-better-than-other-sorting-algorithms-in-practice
本文更深入地讨论了已经排序的列表的问题以及实现这种异常情况的快速排序的方法。 http://www.csie.ntu.edu.tw/~b93076/p847-sedgewick.pdf
于 2013-05-16T13:04:23.177 回答