堆排序算法图文详解（模版使用）

算法介绍

引用百度百科的介绍。

堆排序（英语：Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

算法描述

堆排序的思想借助于二叉堆中的最大堆得以实现。首先，将待排序数列抽象为二叉树，并构造出最大堆；然后，依次将最大元素（即根节点元素）与待排序数列的最后一个元素交换（即二叉树最深层最右边的叶子结点元素）。每次遍历，刷新最后一个元素的位置（自减1），直至其与首元素相交，即完成排序。

算法实现

     void heapSort(int[] nums) {
        int size = nums.length;
        //首先从底向上构建一个大顶堆，抽象我们的二叉树
        for (int i = size/2-1; i >=0; i--) {
            adjust(nums, size, i);
        }
        //然后每次对我们的堆进行首部和尾部的交换并再次调整
        for (int i = size - 1; i >= 1; i--) {
            int temp = nums[0];
            nums[0] = nums[i];
            nums[i] = temp;
            adjust(nums, i, 0);
        }
    }
    //对我们的堆进行调整，保证父亲结点大于左右子结点
    void adjust(int []nums, int len, int index) {
        //计算左右结点的索引下标
        int l = 2 * index + 1;
        int r = 2 * index + 2;
        int maxIndex = index;
        //对左右结点与原来父结点的值进行比较，并更新最大索引
        if (l < len && nums[l] > nums[maxIndex]) maxIndex = l;
        if (r < len && nums[r] > nums[maxIndex]) maxIndex = r;
        //如果最大索引与原来不相等，进行值的交换来保证我们的大顶堆的
        if (maxIndex != index) {
            int temp = nums[maxIndex];
            nums[maxIndex] = nums[index];
            nums[index] = temp;
            //递归调整下面的子树
            adjust(nums, len, maxIndex);
        }
    }

算法分析

时间复杂度为O(nlogn)，空间复杂度为O(1)。

不稳定排序（例a与b值相同，但是在比较后有可能会发生位置变化）

内排序（所有排序操作都在内存中完成）