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

堆排序：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个元素，构成新的堆

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

[color=blue]再看第一个问题，堆的建成[/color]
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))