排序算法之堆排序

本文主要是介绍排序算法之堆排序，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

原理

基本原理也是选择排序，只是不在使用遍历的方式查找无序区间的最大的数，而是通过堆来选择无序区间的最大的
数。
注意：升序建大根堆，降序建小根堆。

思路

1.先把数组建成大根堆。
2.堆顶元素和最后一个元素交换。交换完后再进行大根堆，后续交换时长度每次-1，相当于每次交换完后，有序长度+1。

代码实现

/**
 * @Author: huang
 * @Date: 2021/9/5 9:58
 * @Description: 堆排序
 */
public class Main7 {
    public static void main(String[] args) {
        int[] array = {5,16,4,3,20,17};
        heapSort(array);
        for (int i : array) {
            System.out.print(i + " ");
        }
    }

    public static void heapSort(int[] array) {
        createHeap(array);
        //堆顶元素与最后一个元素交换并调整，需要n-1轮。
        //每次交换和调整的个数都-i
        for (int i = 0; i < array.length - 1; i++) {
            swap(array,0,array.length-1-i);
            //交换后会破坏大根堆，向下调整，长度不算最后第i个元素
            shiftDown(array, array.length-1-i, 0);
        }
    }

    //创建大根堆
    private static void createHeap(int[] array) {
        //1.从最后一个非叶子结点开始，从右往左，从下到上调整
        for (int i = (array.length - 1 - 1) / 2; i >= 0; i--) {
            //2.子树调整为大根堆
            shiftDown(array, array.length, i);
        }

        //3.整棵树调整完后，进行
    }

    private static void shiftDown(int[] array, int length, int index) {
        int left = index * 2 + 1;
        //调整后，可能会破坏下面已排好的大根堆，得继续向下调整
        while(left < length) {
            int max = left;
            int right = left + 1;
            //让max 在left 和 right 大的一方
            if (right < length && array[right] > array[left]) {
                max = right;
            }
            //让 max 和 index 进行比较，调整为大根堆
            if(array[max] > array[index]) {
                swap(array, max, index);
                //可能会破坏下面的大根堆，index 和 left 往下调整
                index = max;
                left = index * 2 + 1;
            }else {
                break;
            }
        }
    }

    private static void swap(int[] array, int max, int index) {
        int tmp = array[max];
        array[max] = array[index];
        array[index] = tmp;
    }
}

时间复杂度及空间复杂度

稳定性：不稳定

这篇关于排序算法之堆排序的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！