Python 3路分區（快速排序）

我想寫一個3路分區的Python代碼，但是我得到一個索引錯誤。我試圖修復它，但似乎沒有成功。在我的代碼中，我選擇第一個條目作爲數據透視表，然後從左側和右側進行掃描，根據需要交換數值。如果任何條目等於pivot，我將它移動到開始或結束（我得到一個錯誤）的一個。Python 3路分區（快速排序）

這是我的代碼

def partition(a, start, end): 
    left=start+1 
    right=end 
    p=start+1 
    q=end 
    pivot=a[start] 
    while True: 
     while a[left]<pivot: 
      left+=1 
     while a[right]>pivot: 
      right-=1 
      if right==start+1: 
       break 
     if left>=right: 
      break 
     swap(a[left], a[right]) 
     if a[left]==pivot: 
      swap(a[p],a[left]) 
      p+=1 
     if a[right]==pivot: 
      swap(a[right], a[q]) 
      q-=1 
    swap(a[right], a[start]) 
    k=end 
    while k>=q+1: 
     swap(a[left+1], a[k]) 
     k-=1 
     left+=1 
    k=1 
    while k<p: 
     swap(a[k], a[right+1]) 
     k+=1 
     right-=1

，我定義爲交換：

def swap(a, b): 
    temp=a 
    a=b 
    b=temp

，當我嘗試運行這個功能我在第21行得到一個錯誤，該指數超出範圍。有什麼問題在這裏有什麼建議嗎？

來源

2016-06-12 Kat.m

你的'swap'函數什麼都不做。 Python不通過引用傳遞變量。 – khelwood

謝謝，我修好了，現在它似乎工作！ –

正如在問題的評論中指出的那樣，代碼中的swap()函數不會執行任何操作。在Python中，名稱只是附加到對象的標籤。如果您指定了名稱，則只需將標籤附加到對象。當你將一個對象傳遞給一個函數時，該對象被傳遞，而不是分配給它的名字。函數中的賦值只爲對象創建本地名稱，但在函數外部沒有任何可見的效果。

雖然你可以修改對象傳遞給函數。的swap()下實現將工作：

def swap(a, i, j): 
    a[i], a[j] = a[j], a[i]

它修改傳遞進來a列表。

來源

2016-06-12 20:57:05

Python 3路分區（快速排序）

回答

相關問題