堆排序

堆排序

堆排序

堆分为大顶堆和小顶堆，大顶堆就是父节点的值大于子节点的值（小顶堆反之）。大顶堆是升序，小顶堆是降序。
堆排序就是先构建一个顶堆，然后将堆顶第一个元素与最后一个元素交换，此时最大元素就跑到末尾去了，然后再整理一下堆进行下一次交换，直到剩下一个元素堆排序就完成了
稳定排序、空间复杂度是O(1)、时间复杂度是O(nlogn)（像快速排序、归并排序时间复杂度都是nlogn，那该如何选择呢？）
- 快速排序时间复杂度是nlogn，但是最坏情况是n^2，而归并排序和堆排序的时间复杂度都稳定再nlogn

代码实现

import java.util.Arrays;

/**
 * @Description: 堆排序
 * @Author: LinZeLiang
 * @Date: 2020-10-08
 */
public class HeapSort {

    public static void main(String[] args) {
        int[] a = {9, 8, 7, 5, 6, 4, 3, 2, 1, 0};

        heapSort(a);

        System.out.println(Arrays.toString(a));
    }

    /**
     * 堆排序
     *
     * @param a 待排序数组
     */
    private static void heapSort(int[] a) {
        //获取数组长度
        int length = a.length;
        //建立大顶堆，完成建堆
        for (int i = (length - 2) / 2; i >= 0; i--) {
            downAdjust(a, i, length);
        }
        //进行堆排序
        for (int i = length - 1; i >= 1; i--) {
            //交换，将大的数放到末尾
            int temp = a[i];
            a[i]  = a[0];
            a[0] = temp;

            downAdjust(a, 0, i);
        }
    }

    /**
     * 下沉调整
     *
     * @param a 待排序数组
     * @param parent 父节点
     * @param length 数组长度范围
     */
    private static void downAdjust(int[] a, int parent, int length) {
        int temp = a[parent];
        //获取左孩子索引
        int child = parent * 2 + 1;
        //当孩子的索引再数组长度范围内时（即孩子存在时）
        while (child < length) {
            //如果右孩子比左孩子大，就指向右孩子
            if (child + 1 < length && a[child] < a[child + 1]) {
                child++;
            }
            //如果父节点小于等于孩子的结点，那么下沉结束
            if (temp >= a[child]) {
                break;
            }
            //单向赋值，将孩子上移一位
            a[parent] = a[child];
            //父节点索引指向上移的那个孩子的结点，孩子索引也更新
            parent = child;
            child = parent * 2 + 1;
        }
        a[parent] = temp;
    }
}

堆排序

堆排序

推荐阅读