简介

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

1. 大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；
2. 小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；

堆排序的平均时间复杂度为 Ο(nlogn)。&&&&&&&&ni

算法步骤

1. 将待排序序列构建成一个堆 H[0……n-1]，根据（升序降序需求）选择大顶堆或小顶堆
2. 把堆首（最大值）和堆尾互换
3. 把堆的尺寸缩小 1，并调用 heapify，目的是把新的数组顶端数据调整到相应位置
4. 重复步骤 2，直到堆的尺寸为 1。

代码

package com.diodi.sort;
import java.util.Arrays;
/**
 * @author diodi
 * @create 2021-10-20-14:43
 */
public class dui{
    /**
     * 主排序方法
     * @param arr
     * @return
     */
    public static int[] sort(int[] arr){
        int[] list = Arrays.copyOf(arr, arr.length);
        int len = list.length;
        buildMaxHeap(list, len);
        for (int i = len-1; i >0; i--) {
            swap(list, 0, i);
            len--;
            heapify(list, 0, len);
        }
        return list;
    }
    //构建大顶堆
    private static void buildMaxHeap(int[] list , int len) {
        for (int i = (int) Math.floor(len / 2); i >=0; i--) {
            heapify(list, i, len);
        }
    }
    //将调整大顶堆
    private static void heapify(int[] list , int i,int len){
        int left = 2*i +1;
        int right = 2*i +2;
        int temp = i;
        if (left<len && list[left]>list[temp]){
            temp = left;
        }
        if (right<len && list[right]>list[temp]){
            temp = right;
        }
        if (temp != i) {
            swap(list, i, temp);
            heapify(list, temp, len);
        }
    }
    //交换定点和末尾叶子节点位置
    private static void swap(int[] list,
                      int i,
                      int j) {
        int temp = list[i];
        list[i] = list[j];
        list[j] = temp;
    }
}

测试

10w个随机数排列