基本排序算法——堆排序

堆排序

堆定义
n个关键字序列Kl，K2，…，Kn称为（Heap），当且仅当该序列满足如下性质（简称为堆性质）：
(1)ki<=k(2i）且ki<=k(2i+1)(1≤i≤ n），当然，这是小根堆，大根堆则换成>=号。//k(i）相当于二叉树的非叶结点，K(2i）则是左孩子，k(2i+1）是右孩子
若将此序列所存储的向量R[1..n]看做是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉树：

树中任一非叶结点的关键字均不大于（或不小于）其左右孩子（若存在）结点的关键字。

【例】关键字序列（10，15，56，25，30，70）和（70，56，30，25，15，10）分别满足堆性质（1）和（2），故它们均是堆，其对应的完全二叉树分别如小根堆示例和大根堆示例所示。
大根堆和小根堆：根结点（亦称为堆顶）的关键字是堆里所有结点关键字中最小者的堆称为小根堆，又称最小堆。根结点（亦称为堆顶）的关键字是堆里所有结点关键字中最大者，称为大根堆，又称最大堆。注意：①堆中任一子树亦是堆。②以上讨论的堆实际上是二叉堆（Binary Heap），类似地可定义k叉堆。

高度
堆可以被看成是一棵树，结点在堆中的高度可以被定义为从本结点到叶子结点的最长简单下降路径上边的数目；定义堆的高度为树根的高度。我们将看到，堆结构上的一些基本操作的运行时间至多是与树的高度成正比，为O（lgn）。

package basic.sort;

import java.util.Arrays;
import java.util.Random;

public class HeapSort {
    /*
     * 将数组调整为小根堆，即由小到大排序，每次对定的数据移动到当前为排序的数据列的最后，记得到从小到大的排序数组
     */
    
    /*
     * 创建堆（对该堆进行简单的排序）
     */
    public <AnyType extends Comparable<? super AnyType>>
    void CreateHeap(AnyType[] heap) {
        for (int i = heap.length /2 ; i >=  0 ; i--) {
            AdjustHeap(heap ,i, heap.length);
        }
    }
    
    /*
     * 调整堆使其堆顶为未排序堆中最大关键字
     */
    public <AnyType extends Comparable<? super AnyType>>
    void AdjustHeap(AnyType[] heap, int location, int unSortlength) {
        AnyType temp;
        int right;
        /*
         * 确保左右节点存在
         */
        if ((right = (location + 1) * 2) < unSortlength) {
            /*
             * 判断左右节点大小
             */
            if (heap[right].compareTo(heap[right - 1]) > 0) {
                /*
                 * 判断父节点与子节点的大小，若父节点小，则与大的子节点换位
                 */
                if (heap[location].compareTo(heap[right]) < 0) {
                    temp = heap[location];
                    heap[location] = heap[right];
                    heap[right] = temp;
                    /*
                     * 递归法对换位后的子节点及其子节点进行调整
                     */
                    AdjustHeap(heap,right, unSortlength);
                }
            } else {
                /*
                 * 左节点大于右节点
                 */
                if (heap[location].compareTo(heap[right - 1]) < 0) {
                    temp = heap[location];
                    heap[location] = heap[right - 1];
                    heap[right - 1] = temp;
                    /*
                     * 递归法对换位后的子节点及其子节点进行调整
                     */
                    AdjustHeap(heap ,right - 1, unSortlength);
                }
            }
        }
        /*
         * 确保左节点存在
         */
        else if ((right = (location + 1) * 2 - 1) < unSortlength) {
            /*
             * 与左节点进行比较
             */
            if (heap[location].compareTo(heap[right]) <0) {
                /*
                 * 左子节点大于父节点，将两者进行换位
                 */
                temp = heap[location];
                heap[location] = heap[right];
                heap[right] = temp;
                AdjustHeap(heap ,right, unSortlength);
            }
        }
    }
    public static void main(String[] args) {
        
        Random rand = new Random();
        Integer[] heap = new Integer[10];
        for(int i = 0 ;i <10 ;i++){
            heap[i] = rand.nextInt(1000);
        }
        println(Arrays.toString(heap));
        
        HeapSort heapSort = new HeapSort();
        
        
        /*
         * 创建堆（对该堆进行简单的排序）
         */
        heapSort.CreateHeap(heap);
        Integer temp ;
        for (int i = heap.length - 1; i > 0; i--){
            temp = heap[0];
            heap[0] = heap[i];
            heap[i] = temp;
        /*
         *  从堆顶进行调整，使未排序堆中最大关键字到堆顶
             */
            heapSort.AdjustHeap(heap ,0, i);
        }
        
        println(Arrays.toString(heap));
    }
    
    public static void println(String str){
        System.out.println(str);        
    }
}

推荐网络资源C++实现

http://blog.csdn.net/clam_clam/article/details/6799763