堆排序算法的Java实现与分析

1、堆排序算法的简单介绍

顾名思义哈，堆排序算法就是使用堆这种数据结构设计的一种排序算法，关于堆排序算法网上能找到太多的的资料讲解，但我是为了自己学习自己理解来写的博客，所以我呢只在我的博客中记录关键的一些知识点。

堆排序算法的关键知识点：

• 时间复杂度：在最好、最坏、平均情况下的时间复杂度都是O(nlogn)；
• 稳定性：是一种不稳定的排序算法
• 堆分为大根堆和小根堆，相应的堆排序算法分为大根堆排序算法和小根堆排序算法
• 大根堆排序算法对应的是从小到大的排序，小根堆对应的是从大到小的排序算法

2、堆排序算法的基础知识

　　在堆排序算法中需要使用堆这种数据结构。

　　堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。二叉树中的知识点关于什么是完全二叉树什么是满二叉树等是基础中的基础。　　

　　因为堆是完全二叉树，所以我们在储存完全二叉树的时候可以使用数组，这是因为使用数组也能够通过数组下标反映出各个二叉树节点之间的关联关系。这样我们在查找某一个节点的左右孩子的时候就能根据该节点的数组下标直接求出孩子节点的数组下标。换言之就是二叉树的逻辑结构能够通过数组下标间接反映出来。

　　大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]

    小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]  

3、堆排序算法的基本思路

• 步骤一：构建大根堆或者小根堆：因为刚开始的数组中数组是不符合堆的特点的，所以需要适当的调整数组中数据之间下标的相应关系，使得满足满足大根堆或者小根堆的特点，调整的时候是从最后一个非叶子节点开始逐一向上进行调整的。
• 步骤二：将堆顶元素与末尾元素进行交换，使末尾元素最大（使用大根堆进行举例）。交换之后最后一个元素就相当于已经排好顺序了。因为是大根堆，所以最大元素放在最后，排序结束得到的就是一个从小到大排序的数组
• 步骤三：执行完步骤二的堆第一个元素不一定满足堆排序的特点，需要继续调整堆中的第一个节点，再将堆顶元素与末尾元素交换，得到第二大元素。
• 步骤四：如此反复进行交换、重建、交换。

 4、堆排序算法的Java实现 

package com.baozi.paixu;

import java.util.Arrays;

/**
 * 堆排序基本思想：将待排序序列构造成一个大根堆，此时整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，
 * 此时末尾元素就是最大值，然后将n-1个元素重新狗造成一个堆，这样会得到n-1个元素的最大值，这样循环往复就能得到
 * 一个有序序列。
 * 注意：堆排序算法的最好、最坏、平均时间复杂度均为O(nlogn).
 * 对排序算法的步骤：
 * 1、构造初始堆：将一个给定的无序序列构造成一个大根堆（一般升序采用大根堆，降序采用小根堆）
 * ①先确定从该序列（数组保存）的最后一个非叶子节点(length/2-1)从右至左从下至上不断进行调整
 * ②确保每一个子树都是根节点为该子树最大的节点
 * 2、将堆顶元素与末尾元素进行交换，使得末尾元素最大，然后在把剩余的n-1个元素继续继续调整为个数为n-1个元素的
 * 大根堆，这时候再把堆顶元素取出来，这样循环往复就能得到有序序列。
 *
 * @author BaoZi
 * @create 2019-05-15-18:16
 */
public class HeapSort {
    public static void main(String[] args) {
        int[] nums = new int[]{10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
        HeapSort.heapSort(nums);
        System.out.println(Arrays.toString(nums));

    }

    public static void heapSort(int[] nums) {
        //1、创建大根堆，既是将无序的元素按照堆的要求创建成一个大根堆
        //因为刚开始的时候数据元素是存在数组中的
        //这里使用循环的目的是针对每一个非叶子节点都要进行逐一调整
        for (int i = nums.length / 2 - 1; i >= 0; i--) {
            //调整为大根堆的时候是从最后一个非叶子结点从下至上（针对二叉树的结构而言），
            // 从右至左（针对存储为数组而言）调整结构
            adjustHeap(nums, i, nums.length);
        }
        //2、交换末尾元素和第一个元素然后再重新调整堆结构
        for (int j = nums.length - 1; j > 0; j--) {
            //将堆顶元素与末尾元素进行交换
            swap(nums, 0, j);
            //重新对堆进行调整
            adjustHeap(nums, 0, j);
        }
    }

    private static void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    private static void adjustHeap(int[] nums, int i, int length) {
        //先取出当前元素i
        int temp = nums[i];
        //从i结点的左子结点开始，也就是2i+1处开始,这个循环其实就是直接将该节点调整到最终确定的位置
        for (int k = i * 2 + 1; k < length; k = k * 2 + 1) {
            //如果左子结点小于右子结点，k指向右子结点
            if (k + 1 < length && nums[k] < nums[k + 1]) {
                k++;
            }
            //如果子节点大于父节点，将子节点值赋给父节点（不用进行交换）
            if (nums[k] > temp) {
                nums[i] = nums[k];
                i = k;
            }
        }
        //将temp值放到最终的位置
        nums[i] = temp;
    }

}