[数据结构与算法]堆排序算法实现

基本思想：堆排序使用了堆这种完全二叉树数据结构，使得子节点的键值总是小于（或者大于）它的父节点，然后逐个选出根节点，直到剩下最后一个节点，最终完成排序。

堆数据结构的实现利用了一维数组，节点满足如下条件：

第i个父节点的左子节点索引为 2i
第i个父节点的右子节点索引为 2i+1
算法实现：

#!/usr/bin/awk -f
# heap sort
BEGIN{
        print "排序："
        print "输入示例：   8 1 6 3 5 2 4 7"
}
{ 
        for( i = 1; i <= NF; i++) 
                A[i] = $i ; 
        hsort(A, NF)
        ## 显示结果
        show(A,1,NF)
        nl()
}
function nl() {
        printf("---------------------------------\n")
}
function show(arr,start ,end , j, i) {
        for( i = start ; i < end ; i++)
                printf("%d%s", arr[i], i == j ? "|":" ")
        printf("%d%s\n", arr[i], i == j ? "|":"")
}

function swap(A,i,j, t){
        t = A[i]; A[i] = A[j]; A[j] = t
}
## heap sort
function hsort(A, n, i){
        # 建堆
        for( i = int(n/2); i >= 1; i--) {
                heapify(A, i, n)
        }
        show(A, 1,n)
        # 挑出父节点后重新建堆 #
        for( i = n; i > 1 ; i--) {
                swap(A, 1, i)
                heapify(A, 1, i-1)
                show(A, 1,n, i-1)
        }
}
# 构建堆
function heapify(A, left, right,  p,c) {
        for( p = left; (c = 2*p) <= right; p = c){
                if( c < right && A[c+1] > A[c])
                        c++
                if( A[p] < A[c])
                        swap(A, c, p)
        }
}

执行结果：

./hsort.awk  
8 1 6 3 5 2 4 7  
8 7 6 3 5 2 4 1  
7 5 6 3 1 2 4|8  
6 5 4 3 1 2|7 8  
5 3 4 2 1|6 7 8  
4 3 1 2|5 6 7 8  
3 2 1|4 5 6 7 8  
2 1|3 4 5 6 7 8  
1|2 3 4 5 6 7 8  
1 2 3 4 5 6 7 8
---------------------------------

下图展示了堆排序的过程示例：