code:

# 類似于快排的思想跨释，不同的地方在于每趟只需要往一個(gè)方向走
# 按照從小到大的順序胸私，尋找前K個(gè)最小值
def qselect(ary_list, k):
    if len(ary_list) < k:
        return ary_list

    tmp = ary_list[0]
    left = [x for x in ary_list[1:] if x <= tmp] + [tmp]
    llen = len(left)
    if llen == k:
        return left
    if llen > k:
        return qselect(left, k)
    else:
        right = [x for x in ary_list[1:] if x > tmp]
        return left + qselect(right, k-llen)
    pass

最大堆
假設(shè)數(shù)組長度為N，首先取前K個(gè)數(shù)鳖谈，構(gòu)建二叉堆（大頂堆）岁疼，然后將剩余N-K個(gè)元素，依次與堆頂元素進(jìn)行比較缆娃，若小于堆頂元素捷绒，則替換， 并重新為大頂堆贯要。

# 最大堆下沉調(diào)整暖侨，始終保持最大堆
def downAdjust(ary_list, parent_index, length):
    tmp = ary_list[parent_index]
    child_index = 2 * parent_index + 1

    while child_index < length:
        if child_index + 1 < length and ary_list[child_index + 1] > ary_list[child_index]:
            child_index += 1

        if tmp >= ary_list[child_index]:
            break

        ary_list[parent_index] = ary_list[child_index]
        parent_index = child_index
        child_index = 2 * parent_index + 1

    ary_list[parent_index] = tmp
    pass

# 構(gòu)建堆
def build_heap(ary_list, k):
    index = k // 2 - 1  # 最后一個(gè)非葉子結(jié)點(diǎn)
    while index >= 0:
        downAdjust(ary_list, index, k)
        index -= 1
    pass


# 利用最大堆找出前K個(gè)最小值
# 每次從原數(shù)組中拿出一個(gè)元素和當(dāng)前堆頂值比較，
# 然后判斷是否可以放入崇渗，放入后繼續(xù)調(diào)整堆結(jié)構(gòu)
def heapK(ary, nums, k):
    if nums <= k:
        return nums
        
    ks = ary[:k]
    build_heap(ks, k)           # 構(gòu)建大頂堆（先不排序）
    # print('build heap:', ks)
    
    for index in range(k, nums):
        ele = ary[index]
        if ks[0] > ele:
            ks[0] = ele
            downAdjust(ks, 0, k)
            # print('heap adjust:', ks)

    # 如果需要?jiǎng)t輸出排序結(jié)果
    # heap_sort(ks)
    return ks
    pass


if __name__ == '__main__':

    # *** 測試方法1
    ary_list = [10, 2, 38, 9, 22, 53, 47, 7, 3, 97]
    nums = len(ary_list)
    print('{} original data:'.format(nums), ary_list)

    # # 原始數(shù)組的排列順序（作為ks的對(duì)比）
    # build_heap(ary_list, nums)
    # heap_sort(ary_list)
    # print('{} original sorted data:'.format(nums), ary_list)

    for k in range(6, nums + 1):
        ks = heapK(ary_list, nums, k)
        print('{}th data:'.format(k), ks)
        break
    pass

順序

# 堆排序（最大堆）
def heap_sort(ary):
    length = len(ary)

    index = length - 1
    # 依次移除堆頂元素（放入末尾）字逗，并將末尾元素放在堆頂，進(jìn)行下沉調(diào)整宅广，
    # 使得每次都會(huì)有非最大值上浮到堆頂葫掉，并重新調(diào)整為大頂堆；
    # 然后再重復(fù)上述操作跟狱。
    while index >= 0:
        tmp = ary[0]
        ary[0] = ary[index]
        ary[index] = tmp
        downAdjust(ary, 0, index)
        index -= 1

    pass