八大排序算法之堆排序

基本思想

堆的定义如下：具有n个元素的序列（k₁,k₂,…,k_n),当且仅当满足

时称之为堆。由堆的定义可以看出，堆顶元素（即第一个元素）必为最小项（小顶堆）。
若以一维数组存储一个堆，则堆对应一棵完全二叉树，且所有非叶结点的值均不大于（或不小于）其子女的值，根结点（堆顶元素）的值是最小（或最大）的。

算法的实现

package com.zyg.sort;

public class HeapSortAlgorithm
{
    // 建立小根堆，即堆顶元素最小
    public static void buildMinHeap(int a[], int len)
    {
        // 从len/2依次到堆顶建立初始化小根堆
        for (int i = len / 2; i >= 0; i--)
            adjustDown(a, i, len);
    }
    <!--more-->
    public static void adjustDown(int a[], int index, int len)
    {
        // 记录初始节点值
        int temp = a[index];
        // 获取初始节点的子女节点
        for (int i = index * 2 + 1; i < len; i = i * 2 + 1)
        {
            // 如果子女节点有兄弟节点，则取节点值更小的子女节点
            if (i < len - 1 && a[i] > a[i + 1])
                i++;
            // 如果子女节点都比该节点值大，则结束调整
            if (temp < a[i])
                break;
            // 将子女节点的更小值赋给该节点
            a[index] = a[i];
            // 设置改变的子女节点为新的初始节点
            index = i;
        }
        // 将初始节点值放入合适位置
        a[index] = temp;
    }
    
    public static void heapSort(int a[], int len)
    {
        // 建立小根堆
        buildMinHeap(a, len);
        // 打印堆顶元素
        System.out.println(a[0]);
        for (int i = len - 1; i > 0; i--)
        {
            // 将堆顶元素与最后一个元素交换
            swap(a, 0, i);
            // 重新调整堆
            adjustDown(a, 0, i);
            // 打印调整后的堆顶元素
            System.out.println(a[0]);
        }
    }
    
    // 交换元素
    public static void swap(int a[], int i, int j)
    {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
    
    public static void main(String[] args)
    {
        // 定义初始化数组
        int a[] =
        { 4, 3, 6, 7, 33, 15, 90, 65 };
        // 进行堆排序
        heapSort(a, a.length);
    }
}

效率

时间复杂度

平均情况：O(nlog₂n)
最好情况：O(nlog₂n)
最坏情况：O(nlog₂n)

空间复杂度

O(1)

稳定性

不稳定