`

排序算法(四)---堆排序(选择排序)

阅读更多
堆排序:heap sort属于选择排序

堆的定义:有n个元素的序列(k1,k2...kn)满足:

1:Ki =< K2i 且 Ki =< K2i+1 (小顶堆)



2:Ki >= K2i 且 Ki >= K2i+1 (大顶堆)

i = (1,2,...n/2)

基本思想:
把要排序的n个数的序列组建成一个堆,将堆顶元素输出(这时,堆顶元素也即是根元素是最大或最小),然后对剩余的n-1个元素再次组建成堆,再次输出堆顶元素……
直到只有两个结点的堆,对它们进行交换,得到一个n个结点有序数列

操作:需要解决两个问题:
1:怎么建成堆
2:输出堆顶元素后,怎么对余下的n-1个元素,构成新的堆

先看第二个问题的解决:
1)将堆底元素送入堆顶(最后一个元素与堆顶交换),堆被破坏
2)将根结点与左,右子树中的最小(或最大)元素进行交换
3)若与左子树交换,若左子树的根结点不满足堆定义,重复2)
4)若与右子树交换,若右子树的根结点不满足堆定义,重复2)
5)继续对不满足堆定义的结点进行调整,直到叶子节点,堆建成

再看第一个问题,堆的建成
1)n个结点的完全二叉树,最后一个节点是第n/2个结点的子树
2)筛选从第n/2个结点为根的子树开始,将该子树建成堆
3)继续对n/2-1的结点,重复2)直到n/2-1=1

算法复杂度:
最坏情况下接近最差情况:O(n*logn)

稳定性:
不稳定

python代码:heap_sort.py

#coding:utf-8
def build_heap(l, length):
    for i in range((length-1)/2, -1, -1):
        adjust_heap(l, i, length)

#l是待排序数列
#s是待调整的数组元素的位置
#length是数组长度
#这是小顶堆排序
def adjust_heap(l, s, length):
    tmp = l[s]
    child = 2*s + 1         #左孩子结点的位置
    while(child < length):
        if(child+1 < length and l[child] < l[child+1]):
            child += 1          #查找左右结点中最小的元素
        if l[s] < l[child]:
            l[s] = l[child]
            s = child           #重新设置s,即待调整的下一个结点的位置
            child = 2*s + 1
        else:
            break
        l[s] = tmp

def heap_sort(l, length):
    #初始化堆
    build_heap(l, length)

    #从最后一个元素开始对序列进行调整
    for i in range(length - 1, -1, -1):
        tmp = l[i]      #堆顶元素和堆底元素交换
        l[i] = l[0]
        l[0] = tmp
        adjust_heap(l, 0, i)   #注意此时堆的大小i

if __name__ == '__main__':
    l = [3,1,5,7,2,4,9,6,10,8]
    heap_sort(l, 10)
    print('result:' + str(l))
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics