找到quickSort算法的所有枢轴值

如果我想查找QuickSort的所有主轴值，我该在什么时候停止分割子阵列？

QuickSort(A,p,r): 
    if p < r: 
     q = Partition(A,p,r) 
     Quicksort(A,p,q-1) 
     Quicksort(A,q+1,r) 

Partition(A,p,r): 
    x = A[r] 
    i = p-1 
    for j = p to r-1: 
    if A[j] ≤ x: 
     i = i + 1 
     swap(A[i], A[j]) 
    swap(A[i+1], A[r]) 
    return i+1

含义，如果我有一个数组： A = [9,7，5，11，12，2，14，3，10，6]

作为快速排序打破了这种成其组成件...

A = [2,5，3] [12，7，14，9，10，11]

一个步骤以达到混乱的点...

A = [2,5] [7，12，14，9，10，11]

左侧的子阵列在此停止吗？还是它（quickSort）用5作为最终的枢轴值进行最后一次调用quickSort？

对我来说，我们会继续下去，直到所有的子阵列都是单个项目 - 但是我的一个同伴一直告诉我，这是有道理的。

来源

2017-10-17 Derp

所以，你只是想找到你的算法使用的枢轴值，直到它排序列表？ – gsamaras

@gsamaras是的！我想我已经拥有了它 - 但我想确定自己明白。我认为他们是6,3,5,11,10,9,12 – Derp

@gsamaras这大多是一个*总体概念性问题，而不是一个编码问题。 – Derp

枢轴为你的例子将是：6, 3, 11, 10, 9, 12。关于

左侧的子阵列在这里停止吗？

检查源代码总是最好的。当递归子阵列变为[2, 5, 3]时，函数QuickSort将与p = 0和r = 2一起调用。让我们继续：Partition(A,0,2)将返回q = 1，所以接下来的两个电话将是Quicksort(A,0,0)和Quicksort(A,2,2)。因此，Quicksort(A,0,1)永远不会被调用，所以你永远不会有机会检查子阵列[2, 5] - 它已经被排序！

来源

2017-10-17 07:54:00

找到quickSort算法的所有枢轴值

回答

相关问题