首页 文章

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

提问于
浏览
2

对于合并排序和快速排序,我试图想出最糟糕的情况 . 如果我是正确的,在排序所有内容时合并排序最差的情况O(nlogn) . 快速排序最糟糕的情况是当枢轴处于最不理想的位置,并且数组被排序,因此它变为O(n ^ 2) . 我想知道这是否正确,所以如果没有,请纠正我 . 我真正的问题是,如果快速排序的数据库位于数组的中间,那么数组必须是什么才能使它成为O(n ^ 2)?

2 回答

  • 0

    最简单的快速排序是当枢轴小于或大于要排序的所有其他值时 . 在这种情况下,在每个递归级别仅从剩余值中移除1个项目,并且时间复杂度最终为O(n ^ 2) .

    对于基本合并排序,自上而下或自下而上,移动的数量始终相同 . 比较次数取决于数据模式 . 当合并两个大小为n的运行时,最差情况下的比较数为2n-1(当比较两个运行中的每个元素时,只剩下1个元素,没有什么可比较的,所以它只是复制了)最好的情况是,一次运行的所有元素都小于另一次运行的第一个元素,在这种情况下,比较的数量是n,例如数据已经排序或反向排序时 .

  • 1

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

    这假定了一个通常的旋转算法,它会在将数组分区到位之前将数据透视值交换到数组的开头 . 在这种情况下,由于我们将枢轴选择为最小的剩余项目,因此不会进行分区 .

    这是仿真代码:

    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]
    

相关问题