dangdangA

 1 def parttion(v, left, right):
 2     '''
 3     :param v: 要排序的列表
 4     :param left: 列表起始端
 5     :param right: 列表末端
 6     :return:
 7     '''
 8     key = v[left]  #基準(zhǔn)
 9     low = left
10     high = right
11     while low < high:
12         while (low < high) and (v[high] >= key):
13             high -= 1
14         v[low], v[high] = v[high],v[low]
15         while (low < high) and (v[low] <= key):
16             low += 1
17         v[high],v[low] = v[low],v[high]
18         #v[low] = key
19     return high
20 #查找第K小數(shù)字
21 def quickSelect(v, left, right,k):
22     if left < right:
23         p = parttion(v, left, right)
24         if p == left + k -1:
25             return v[p]
26         elif p > left + k - 1:
27             return quickSelect(v, left, p-1,k)
28         else:
29             return quickSelect(v, p+1, right,left + k-1-p)
30 
31 if __name__ == "__main__":
　　　　s = [6, 8, 1, 4, 3, 9, 5, 4, 11, 2, 2, 15, 6]

32 　　print(quickSelect(s,0,len(s) - 1,4))