Python quickselect排序

Question

該程序應該使用快速選擇並返回一組整數值的中位數。

問題：當我運行程序時，它告訴我k沒有被定義。我應該如何定義k來獲得中位數？

def quickSelect(lines,k): 
    if len(lines)!=0: 
     pivot=lines[(len(lines)//2)] 
     smallerlist=[] 
     for i in lines: 
      if i<pivot: 
       smallerlist.append(i) 
     largerlist=[] 
     for i in lines: 
      if i>pivot: 
       largerlist.append(i) 
     m=len(smallerlist) 
     count=len(lines)-len(smallerlist)-len(largerlist) 
     if k >= m and k<m + count: 
      return pivot 
     elif m > k: 
      return quickSelect(smallerList,k) 
     else: 
      return quickSelect(largerList, k - m - count) 

Answer 1

該代碼似乎工作正常，經過小幅修正後。 smalllist和greaterlist有一個錯字。

 elif m > k: 
      return quickSelect(smallerList,k) 
     else: 
      return quickSelect(largerList, k - m - count) 

應

 elif m > k: 
      return quickSelect(smallerlist,k) 
     else: 
      return quickSelect(largerlist, k - m - count) 

改變這是最後的更正後的代碼，它運行得很好。

def quickSelect(lines,k): 
    if len(lines)!=0: 
     pivot=lines[(len(lines)//2)] 
     smallerlist=[] 
     for i in lines: 
      if i<pivot: 
       smallerlist.append(i) 
     largerlist=[] 
     for i in lines: 
      if i>pivot: 
       largerlist.append(i) 
     m=len(smallerlist) 
     count=len(lines)-len(smallerlist)-len(largerlist) 
     if k >= m and k<m + count: 
      return pivot 
     elif m > k: 
      return quickSelect(smallerlist,k) 
     else: 
      return quickSelect(largerlist, k - m - count) 

希望它可以幫助

Answer 2

您需要初始化K爲第一次進入該功能。它應該是您正在查找的物品的位置（如果列表已分類）。默認值爲列表長度的一半，爲中位數。說它像這樣：

k = len(lines) // 2 
x = quickSelect(lines, k) 

，或者如果您只想位數，你可以修復功能，因此您不必提供該項目的索引，你想

def quickSelect(lines, k=None): 
    if k is None: 
     k = len(lines)//2 

正如休指出，這個函數只會選擇列表中的一個元素。對於偶數個元素的中位數，中位數實際上應該是中間兩個元素的平均值。

Answer 3

您錯誤地報告了錯誤;它不會抱怨k，它會抱怨smallerList，因爲您定義了smallerlist（小寫-1），然後試圖用大寫字母-L調用它。 Python變量區分大小寫，即smallerlist is smallerList == False。在你的代碼

展望：

def quickSelect(lines, k): 
    if len(lines) != 0: 

len(lst) != 0是不地道; PEP-8說它應該只是lst，如if lst:。另外，camelCase是非細菌的;你的函數名應該是quick_select。 lines意味着你只能對文本進行操作，但是你的函數在任何可訂購的數據類型上都能正常工作，所以items會更準確。你應該有一個文檔字符串，這樣下一個人就會知道它做了什麼，我們將再次調用len(items)，所以我們不妨做一次並存儲結果。最後，如果k > len(items)？

def quick_select(items, k): 
    """ 
    Return the k-from-smallest item in items 

     Assumes 0 <= k < len(items) 
    """ 
    num_items = len(items) 
    if 0 <= k < num_items: 
     pivot = items[num_items // 2] 

繼續：

 smallerlist = [] 
     for i in lines: 
      if i<pivot: 
       smallerlist.append(i) 
     largerlist=[] 
     for i in lines: 
      if i>pivot: 
       largerlist.append(i) 

你已經通過lines重複兩次;你可以把它合併成一個單一的傳球。此外，更好的變量名：

 smaller, larger = [], [] 
     for item in items: 
      if item < pivot: 
       smaller.append(item) 
      elif item > pivot: 
       larger.append(item) 

更好的變量名繼續，

 num_smaller = len(smaller) 
     num_pivot = num_items - num_smaller - len(larger) 

那麼你if s爲亂序;它們更容易以讀取，所以

 if k < num_smaller: 
      return quick_select(smaller, k) 
     elif k < num_smaller + num_pivot 
      return pivot 
     else: 
      return quick_select(larger, k - num_smaller - num_pivot) 

然後什麼如果k < 0或k> =項數?:

else: 
     raise ValueError("k={} is out of range".format(k)) 

最後，因爲該函數是尾遞歸，很容易轉換爲迭代功能：

 while True: 
      pivot = items[num_items // 2] 

      # ... 

      if k < num_smaller: 
       items = smaller 
       num_items = num_smaller 
      elif k < num_smaller + num_pivot 
       return pivot 
      else: 
       items = larger 
       num_items = num_larger 
       k -= num_smaller + num_pivot 

...需要一些程序集，希望有所幫助！