找到quickSort算法的所有枢轴值
问题描述:
我似乎对正确实施快速排序有点困惑。找到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?
对我来说,我们会继续下去,直到所有的子阵列都是单个项目 - 但是我的一个同伴一直告诉我,这是有道理的。
答
枢轴为你的例子将是: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]
- 它已经被排序!
所以,你只是想找到你的算法使用的枢轴值,直到它排序列表? – gsamaras
@gsamaras是的!我想我已经拥有了它 - 但我想确定自己明白。我认为他们是6,3,5,11,10,9,12 – Derp
@gsamaras这大多是一个*总体概念性问题,而不是一个编码问题。 – Derp