分區陣列沒有正確出來

我想分區的數組，使數組的前半部分中的每個元素小於數組後半部分中的每個元素。這與快速排序中使用的分區算法相同。出於某種原因，我可以使數組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

分區陣列沒有正確出來

回答

相關問題