了解合并排序和快速排序的运行时间

对于合并排序和快速排序，我试图想出最糟糕的情况。如果我是正确的，当所有东西都排序后，合并排序的最坏情况O（nlogn）。快速排序最糟糕的情况是当数据透视表处于最不理想的位置，并且数组被排序，所以它变成了O（n^2）。我想知道这是否是正确的，所以如果不是，请纠正。我真正的问题是如果快速排序的枢轴位于数组的中间，那么数组必须看起来像是为了O（n^2）？了解合并排序和快速排序的运行时间

来源

2017-03-09 Dinoman979

快速排序最糟糕的情况是当数据透视小于或大于其他所有剩下要排序的值时。在这种情况下，每个递归级别的剩余值中只有1个项目被删除，时间复杂度最终为O（n^2）。

对于基本的合并排序，自上而下或自下而上，移动次数总是相同。比较的数量取决于数据模式。当合并两次大小为n的游程时，最差情况下的比较次数为2n-1（当比较两次运行中的每个元素时，只剩下1个元素，没有任何可比较的，因此它只是被复制）最好的情况是，一次运行的所有元素都小于另一次运行的第一个元素，在这种情况下，比较次数为n，例如数据已经排序或反向排序。

来源

2017-03-09 02:05:57 rcgldr

因此，如果枢轴为5中的阵列[1,2,3,4,5,6 ，7,8,9]，因为它在中间，所以运行时间是O（n log n），因为5既不大于也不小于数组中的所有其他值？此外，如果枢轴仍然是5，并且该数组类似于[7,8,9,10,5,11,12,13,14]，由于枢轴小于所有其他值，这会是O（n^2）时间复杂度的一个例子？ – Dinoman979

@ Dinoman979 - 是的，但是对于O（n^2）时间复杂度，代码将不得不重复遇到中间点小于或大于其余值的情况。如果代码选择中间值，则模式将变得复杂，并且将取决于数据透视是否包含在通过递归调用传递的子数组中。 – rcgldr

您可以模拟快速排序，确保每次选择枢轴时，它都是连续0,1,2，...以确保最差情况下的性能。

这里假设一个通常的旋转算法，在将数组分区之前，将pivot数值交换到数组的起始位置。在这种情况下，由于我们选择的枢轴是最小的剩余物品，因此不会进行分区。

这里的仿真代码：

class Cell: 
    def set(self, v): 
     self.v = v 

def worst_case_quicksort(xs, i): 
    xs = xs[:] 
    for i in xrange(len(xs)): 
     p = (len(xs) - i) // 2 
     xs[i+p].set(i) 
     xs[i], xs[i+p] = xs[i+p], xs[i] 

xs = [Cell() for _ in xrange(20)] 
worst_case_quicksort(xs, 0) 
print [x.v for x in xs]

输出看起来像这样：

[1, 11, 3, 19, 5, 13, 7, 17, 9, 15, 0, 2, 4, 6, 8, 10, 12, 14, 16, 18]

来源

2017-03-09 02:37:36

了解合并排序和快速排序的运行时间

回答

相关问题