堆排序

堆排序介绍

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

堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。如下图：

同时，我们对堆中的结点按层进行编号，将这种逻辑结构映射到数组中就是下面这个样子

堆结构

该数组从逻辑上讲就是一个堆结构，我们用简单的公式来描述一下堆的定义就是：

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

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

特点

堆的特点就是堆顶的元素是一个最值，大顶堆的堆顶是最大值，小顶堆则是最小值。

过程描述

堆排序就是把堆顶的元素与最后一个元素交换，交换之后破坏了堆的特性，我们再把堆中剩余的元素再次构成一个大顶堆，然后再把堆顶元素与最后第二个元素交换….如此往复下去，等到剩余的元素只有一个的时候，此时的数组就是有序的了。

为方便理解我还准备了动图：

实现代码

package fg;

import java.util.Arrays;

public class HeapSort{
    public static void main (String[] args) {
        int []arr={50,45,40,20,25,35,30,10,15};
        System.out.println("排序前："+ Arrays.toString(arr));
        sprt(arr);
        System.out.println("排序后："+Arrays.toString(arr));
    }

    private static void sprt (int[] arr) {
        //1.构建大顶堆
        for (int i =arr.length/2-1; i >=0 ; i--) {
            //从第一个非叶子结点从下至上，从右至左调整结构
            adjustHeap(arr,i,arr.length); //sdjust是调整的意思(英语不好的小伙伴儿不用惊讶)

        }
        //2.调整堆结构+交换堆顶元素与末尾元素
        for (int j = arr.length-1; j >0 ; j--) {
            swap(arr,0,j);//将堆顶元素与末尾元素进行交换
            adjustHeap(arr,0,j);//重新对堆进行调整


        }
    }

    /**
     * 交换元素
     * @param arr
     * @param a
     * @param b
     */

    private static void swap (int[] arr, int a, int b) {
        int temp =arr[a];
        arr[a]=arr[b];
        arr[b]=temp;
    }
    /**
     *
     * 调整大顶堆（仅是调整过程，建立在大顶堆已构建的基础上）
     * @param arr
     * @param i
     * @param length
     */
    private static void adjustHeap (int[] arr, int i, int length) {
        int temp=arr[i];   //先取出当前元素i
        for (int k = 2*i+1; k <length ; k=2*k+1){//从i结点的左子结点开始，也就是2i+1处开始
          if (k+1<length&&arr[k]<arr[k+1]){//如果左子结点小于右子结点，k指向右子结点
             k++;

          }
            if(arr[k] >temp){//如果子节点大于父节点，将子节点值赋给父节点（不用进行交换）
                arr[i] = arr[k];
                i = k;
            }else{
                break;
            }
        }
        arr[i] = temp;//将temp值放到最终的位置
    }
}

输出

排序前：[50, 45, 40, 20, 25, 35, 30, 10, 15]
排序后：[10, 15, 20, 25, 30, 35, 40, 45, 50]