排序算法之堆排序

1468449529

讲真，我是因为数据结构考试看了一下复习资料才知道的堆排序，一学期没上课的后果。于是，查了资料了解了这一算法。

俗话说堆栈堆栈，堆跟栈是什么就不说了。堆可以被看成是一棵树，那么就有了二叉堆，最小堆最大堆的说法。以下是百度百科的对堆的简述

堆是一种经过排序的完全二叉树，其中任一非终端节点的数据值均不大于（或不小于）其左孩子和右孩子节点的值。

最大堆和最小堆是二叉堆的两种形式。

最大堆：根结点的键值是所有堆结点键值中最大者。

最小堆：根结点的键值是所有堆结点键值中最小者。

而最大-最小堆集结了最大堆和最小堆的优点，这也是其名字的由来。

最大-最小堆是最大层和最小层交替出现的二叉树，即最大层结点的儿子属于最小层，最小层结点的儿子属于最大层。

以最大（小）层结点为根结点的子树保有最大（小）堆性质：根结点的键值为该子树结点键值中最大（小）项。
如图所示

堆的存储如下图所示

那么很容易看出第n个结点的父结点下标就为(n – 1) / 2。它的左右子结点下标分别为2 * n + 1 和 2 * n + 2。如第0个结点左右子结点下标分别为1和2。
代码实现

package com.w.sort;

public class Dsort {

static int[] array = new int[] { 15, 21, 6, 30, 23, 66, 20, 17 };

/**
 * 生成最小堆,最小堆的任意子树根节点不大于任意子结点
 * 
 * @param array
 * @param heapSize
 *            堆的大小
 * @param parent
 *            父节点下标索引
 */
static void minHeap(int[] array, int heapSize, int parent) {
    int left = parent * 2 + 1; // 左孩子
    int right = parent * 2 + 2;// 右孩子
    if (left < heapSize && array[left] > array[parent]) { // 判断孩子是否大于父节点的值,大于则交换,并继续找当前节点的子节点进行判断
        swap(array, left, parent);
        minHeap(array, heapSize, left);
    }
    if (right < heapSize && array[right] > array[parent]) {// 同上
        swap(array, right, parent);
        minHeap(array, heapSize, right);
    }
}

static void swap(int[] array, int x, int y) {
    int t = array[x];
    array[x] = array[y];
    array[y] = t;
}

public static void main(String[] args) {
    // TODO Auto-generated method stub
    int length = array.length;
    // 初始化为最小堆
    for (int i = length / 2; i >= 0; i--)
        minHeap(array, length - 1, i);

    for (int i = length - 1; i >= 1; i--) {
        swap(array, 0, i); // 每次将最小的数array[0]换到后面有序区间
        minHeap(array, i, 0);
    }

    for (int i = 0; i < length; i++)
        System.out.print(array[i] + " ");
}

}