分区阵列没有正确出来

我想分区的数组，使数组的前半部分中的每个元素小于数组后半部分中的每个元素。这与快速排序中使用的分区算法相同。出于某种原因，我可以使数组A = [2, 8, 7, 1, 3, 5, 6, 4]工作，但A = [7, 3, 6, 1, 9, 5, 4, 8]将无法工作。分区阵列没有正确出来

def partition(A): 
    x = A[len(A)-1] 
    i = -1 
    for j in range (0, len(A)-2): 
     if A[j]<=x: 
     i = i + 1 
     # exchange A[j] and A[i] 
     jValue = A[j] 
     A[j] = A[i] 
     A[i] = jValue 
    # exchange A[len(A)-1] and A[i+1] 
    rValue = A[len(A)-1] 
    A[len(A)-1] = A[i+1] 
    A[i+1] = rValue 
    print(A)

来源

2017-03-11 Brosef

进行调试1）写上你会看到每一遍的东西。 2）让程序打印出它的位置以及每次传递的输入和输出。他们不同意哪里？为什么？是的，这很乏味，但你会在几分钟内找到问题？ ; - /猜猜我如何调试代码。 ; -/ –

我在纸上做了十几遍整个过程，我得到的答案与我的代码输出相匹配。我注意到'A = [7,3,6,1,9,5,4,8]'的原因并不按我期望的方式工作，因为前4个数字小于索引7处的数据点 – Brosef

问题是代码需要选择代表数组中值的数据透视表。这可以使用快速选择或类似的东西来完成。请注意，快速选择的最坏情况时间复杂度为O（n^2）。维基文章：

http://en.wikipedia.org/wiki/Quickselect

来源

2017-03-12 00:27:13 rcgldr

有趣，但它是有道理的。我正在阅读的文本根本没有提到。 – Brosef

分区阵列没有正确出来

回答

相关问题