Python的Quickselect不打印/返回轉動

Question

這裏是quickselect

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

的代碼，我與它遇到的問題是，它沒有任何錯誤或任何運行，但是當它完成了自己，我就期待輸出一些東西到Python shell（在這個特定的情況下，列表的中位數），但我沒有得到任何回報。我在這裏做錯了什麼？

至於什麼我輸入用於LST並且k ....

• LST = [70，120，170，200]
• K = LEN（LST）// 2

我有幾個不同的k值試過很好，但無濟於事

Answer 1

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

lst = [70, 120, 170, 200] 
k = len(lst) // 2 

print(quickSelect(lst, k)) 

產生

>>> 170 

我糾正的唯一問題是縮進。

Answer 2

您可以使用列表理解來優化此算法。此外，我不認爲你需要數...

def quickSelect(seq, k): 
    # this part is the same as quick sort 
    len_seq = len(seq) 
    if len_seq < 2: return seq 

    ipivot = len_seq // 2 
    pivot = seq[ipivot] 

    smallerList = [x for i,x in enumerate(seq) if x <= pivot and i != ipivot] 
    largerList = [x for i,x in enumerate(seq) if x > pivot and i != ipivot] 

    # here starts the different part 
    m = len(smallerList) 
    if k == m: 
     return pivot 
    elif k < m: 
     return quickSelect(smallerList, k) 
    else: 
     return quickSelect(largerList, k-m-1) 




if __name__ == '__main__': 
    # Checking the Answer 
    seq = [10, 60, 100, 50, 60, 75, 31, 50, 30, 20, 120, 170, 200] 

    # we want the middle element 
    k = len(seq) // 2 

    # Note that this only work for odd arrays, since median in 
    # even arrays is the mean of the two middle elements 
    print(quickSelect(seq, k)) 
    import numpy 
    print numpy.median(seq)