堆排序

前言

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

每个节点的值都大于或者等于其左右子节点的值，称为大顶堆；或者每个节点的值都小于或者等于其左右子节点的值，称为小顶堆。

对堆中的节点按层进行编号，将这种逻辑结构映射到数组如下图所示：

该数组从逻辑上讲就是一个堆结构，并且有以下特点：

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

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

综上，堆排序的基本思想就是将待排序的序列构建成一个大顶堆，此时整个序列最大值就是堆顶的根节点。将其与末尾元素交换，此时末尾元素就成为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素中的次小值，也就是n-1个元素中的最大值，并将其放置末尾，并如此反复，就能得到一个有序序列。

实现步骤

步骤一：构造初始堆，将给定无序序列构造成一个大顶堆

假定无序序列结构如下

此时从最后一个非叶子节点[6]开始，叶结点不用调整，从左至右，从上至下进行调整。

找到第二个非叶子节点[4]，由于{4，8，9}中9元素最大，4和9交换。

此时，交换导致了子树{4，5，6}结构混乱，继续调整，现在6元素最大，交换4和6

步骤二：将堆顶元素与末尾元素进行交换，使末尾元素最大，然后继续调整堆，再将堆顶元素与末尾元素交换，如此反复重建和交换。

将堆顶元素9和末尾元素4进行交换

重新调整结构，使其继续满足堆定义

再将堆顶元素8与末尾元素5进行交换，得到第二大元素8

后续过程，继续进行调整，交换，如此反复调整，最终即可整个序列有序。

堆排序算法的基本思路总结：

• 将无序序列建成一个堆，根据升降序需求选择大顶堆和小顶堆。
• 将堆顶元素与末尾元素交换，将最大元素沉到数组末端。
• 重新调整，使其重新满足堆定义，然后继续交换堆顶元素和当前末尾元素，反复执行调整和交换，直至整个序列有序。

代码实现

public static void heapSort(int[] array)
{
    //从倒数第一个非叶子节点开始
    for (int i = array.length/2 - 1; i>=0; i--)
    {
        //从第一天非叶子节点从下至上，从左至右调整结构
        adjustHeap(array,i, array.length);
    }

    //将堆顶元素与末尾元素交换 将最大元素沉到数组末尾 + 重新调整堆结构
    for (int i = array.length - 1; i > 0 ; i--)
    {
        //交换堆顶元素和末尾元素
        swap(array,0,i);
        //交换后的末尾元素忽略(j--) 不再参与堆结构的调整
        //重新调整堆结构
        adjustHeap(array,0,i);
    }

}

private static void swap(int[] array, int start, int end)
{
    int temp = array[start];
    array[start] = array[end];
    array[end] = temp;
}

public static void adjustHeap(int[] array,int index,int length)
{
    //取出当前元素
    int temp = array[index];
    //i节点是index节点的左子节点
    for (int i = 2 * index + 1; i < length; i = 2 * i + 1)
    {
        //表明左子节点小于右子节点
        if (i+1 < length && array[i] < array[i+1])
        {
            //将指针移至较大节点
            i++;
        }

        //如果子节点大于父节点
        if (array[i] > temp)
        {
            //将较大值赋给当前节点
            array[index] = array[i];
            //指针移向子节点
            index = i;
        }
        else
        {
            break;
        }
    }
    //循环结束，已经将最大值放在了堆顶
    //将temp值放到最终的位置
    array[index] = temp;
    
}

public static void main(String[] args)
{
    //升序
    int[] array = {4,6,8,78,13,19,1,5,9,};
    System.out.println("排序前=>"+ Arrays.toString(array));
    heapSort(array);
    System.out.println("排序后=>"+Arrays.toString(array));
}

输出结果

排序前=>[4, 6, 8, 78, 13, 19, 1, 5, 9]
排序后=>[1, 4, 5, 6, 8, 9, 13, 19, 78]

以上。

如有不足或错误欢迎评论指正。