快速選擇算法--解決未排序的數(shù)組中尋找第K小/大的元素
與快速排序不同的是,快速選擇算法只需要對基準(zhǔn)數(shù)的一邊進(jìn)行遞歸
首先,找出基準(zhǔn)數(shù)的下標(biāo)p;
其次,判斷p與(left + k -1)的大小,如果小于的話,直接對數(shù)組基準(zhǔn)數(shù)的左邊進(jìn)行遞歸快排,選擇第 k個;如果大于的話,對基準(zhǔn)數(shù)的右邊進(jìn)行選擇,選擇第K-P-1+left
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))
輸出結(jié)果:3
浙公網(wǎng)安備 33010602011771號