找到無序數(shù)組中的第k大元素， kth_Largest_element_in_an_array。
常見的解決方案有兩種，快速排序思想和堆排序思想，簡單記錄一下過程，順便復(fù)習(xí)快速排序和堆排序過程。
快速排序思想
快速排序的理論基礎(chǔ)是隨機取一個數(shù)，大的放左邊，小的放右邊，完成一趟排序。
分別對左右兩邊遞歸做相同的分割，最后還剩一個數(shù)，自然有序，完成快速排序。
那么找第k大的元素，即完成一次排序后，隨機找出的這個數(shù)的前面有 k -1個數(shù)，那么就是第k大個元素。
下標(biāo)： k - 1 = index.
否則再根據(jù)下標(biāo)關(guān)系判斷在k在左邊還是右邊，繼續(xù)如上操作。
快速排序完成一次排序的函數(shù)如下：
# 最后一個數(shù)為支點，從小到大排序
def partition_two(array, lo, hi):
i = lo
j = hi
while i < j:
while i < j and array[i] <= array[hi]:
i += 1
while i < j and array[j] >= array[hi]: # =保證支點不變，可以后續(xù)比較。
j -= 1
array[i], array[j] = array[j], array[i]
array[i], array[hi] = array[hi], array[i]
return i
下面得到分界點的下標(biāo)，對左右兩邊遞歸分割，完成排序：
# 快速排序
def quick_sort(array, lo, hi):
#參數(shù)合法性
if array is None or lo >= hi:
return
mid = partition_two(array, lo, hi)
quick_sort(array, lo, mid - 1)
quick_sort(array, mid + 1, hi)
找第k大元素的代碼類似。
堆排序思想
首先堆不作介紹，分為大根堆和小根堆。堆的操作有插入和刪除最大(小)元素，插入的節(jié)點放在最后，然后進(jìn)行堆化操作。
堆的一個經(jīng)典實現(xiàn)是完全二叉樹，這樣實現(xiàn)的堆為二叉堆。
下面是數(shù)組進(jìn)行從小到大的堆排序過程。
堆化數(shù)組
一個隨機數(shù)組，對根節(jié)點i進(jìn)行堆化操作(i的左右子樹也都是堆)。
選擇左右節(jié)點的小節(jié)點與根節(jié)點比較，若是根節(jié)點還小于較小值，則滿足堆的性質(zhì)。
否則進(jìn)行交換，對交換過的節(jié)點繼續(xù)進(jìn)行堆化操作，直至全部堆化。
#對數(shù)組來說，以下標(biāo)index為根節(jié)點的左右子樹的下標(biāo)為 index * 2 + 1， index * 2 + 2
# 將length個元素，i為節(jié)點的數(shù)組堆化(i的子節(jié)點也都是堆)
def big_heap_array(array, i, length):
# 左葉子節(jié)點
temp_value = array[i]
node_index = (i << 1) + 1
while node_index < length:
#左右葉子節(jié)點的較大值
if node_index + 1 < length and array[node_index + 1] > array[node_index]:
node_index = node_index + 1
# 如果根節(jié)點大于葉子節(jié)點，說明已經(jīng)是堆，退出循環(huán)。
if array[node_index] < temp_value:
break
array[i] = array[node_index]
# 調(diào)整交換過元素的子節(jié)點
i = node_index
node_index = (i << 1) + 1
array[i] = temp_value
上面操作是堆化i下標(biāo)節(jié)點的數(shù)組，從小到大的排序過程如下：
- 從最后一個根節(jié)點開始，往上進(jìn)行堆化， 此時array[0] 為最大值。
- 交換array[0]和最后一個元素，此時再進(jìn)行堆化，得到最小的元素與倒數(shù)第二個元素，逐次完成從小到大排序。
#n長度的數(shù)組，最后一個根節(jié)點的下標(biāo)為： n / 2 - 1
#構(gòu)建最大堆，從小到大排序
def heap_sort_one(array):
# 最后一個跟節(jié)點
last_node_index = (len(array) >> 1) - 1
for node_index in range(last_node_index, 0 - 1, -1): #[llast_node_index .. 0] 的列表
big_heap_array(array, node_index, len(array))
# 堆頂最大值和最后一個數(shù)互換， 然后堆化數(shù)組
for index in range(len(array) - 1, 0, -1):
array[0], array[index] = array[index], array[0]
big_heap_array(array, 0, index)
下面來解決此問題。
首先利用數(shù)組的前k個元素建立一個k大小的小根堆。逐次取后面的元素與堆頂比較， 如果大于堆頂，則替換堆頂，然后進(jìn)行堆化。最終結(jié)果就是最大的前k個元素都在堆中，其中堆頂元素堆小，就是第k大的元素。
