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]
2 回答
最简单的快速排序是当枢轴小于或大于要排序的所有其他值时 . 在这种情况下,在每个递归级别仅从剩余值中移除1个项目,并且时间复杂度最终为O(n ^ 2) .
对于基本合并排序,自上而下或自下而上,移动的数量始终相同 . 比较次数取决于数据模式 . 当合并两个大小为n的运行时,最差情况下的比较数为2n-1(当比较两个运行中的每个元素时,只剩下1个元素,没有什么可比较的,所以它只是复制了)最好的情况是,一次运行的所有元素都小于另一次运行的第一个元素,在这种情况下,比较的数量是n,例如数据已经排序或反向排序时 .
您可以模拟快速排序,确保每次选择枢轴时,它连续为0,1,2,...以保证最差情况下的性能 .
这假定了一个通常的旋转算法,它会在将数组分区到位之前将数据透视值交换到数组的开头 . 在这种情况下,由于我们将枢轴选择为最小的剩余项目,因此不会进行分区 .
这是仿真代码:
输出如下所示: