堆排序

1、基本介绍

• 堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为 O(nlogn)，它也是不稳定排序

• 堆是具有以下性质的完全二叉树：

  • 每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆

    • 注意 : 没有要求结点的左孩子的值和右孩子的值的大小关系

  • 每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆

• 一般升序排序采用大顶堆，降序排列使用小顶堆

2、排序思路

• 堆是一种树结构，但是排序中会将堆进行顺序存储（变为数组结构）

• 将无序序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆(从2n-1个元素开始，逐级向上)

• 将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端(将最大的元素摘出来，放到数组中，重新构建大顶堆)

• 重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序

3、实现代码

package com.yishuai.sort;
​
import java.util.Arrays;
​
public class Heap {
    public static void main(String[] args) {
        int[] initial = {5, 9, 2, 8, 6, 3, 1, 4, 7};
​
        heapSort(initial, initial.length);
        System.out.println(Arrays.toString(initial));
    }
​
    public static void heapSort(int[] initial, int n) {
        //建堆(n/2-1表示最后一个元素的父节点)
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapAdjust(initial, i, n);
        }
        //排序
        for (int j = n - 1; j > 0; j--) {
            //跟最后一个元素交换-
            swap(initial, 0, j);
            //再调整剩下的堆
            heapAdjust(initial, 0, j);
        }
    }
​
    public static void heapAdjust(int[] initial, int i, int n) {
        //达到最后一个元素，调整完成
        if (i >= n) {
            return;
        }
        int left = 2 * i + 1;
        int right = 2 * (i + 1);
        int largest = i;
        //找到最大值的下标
        if (left < n && initial[left] > initial[largest]) {
            largest = left;
        }
        if (right < n && initial[right] > initial[largest]) {
            largest = right;
        }
        //如果最大值不是最开始的根结点，将最大的值放到根结点上去，重新调整后面的元素
        if (largest != i) {
            swap(initial, i, largest);
            heapAdjust(initial, largest, n);
        }
    }
​
    //交换元素
    public static void swap(int[] initial, int i, int j) {
        int temp = initial[i];
        initial[i] = initial[j];
        initial[j] = temp;
    }
}