堆排序Java实现(递归方式&非递归方式)

很早就学习了堆排序但当时没有用代码实现,现在再去想实现已经忘光光啦┑( ̄Д  ̄)┍,于是就去网上搜了一番,发现没有一篇我能认真看完的文章,没办法就是没耐心,就是笨呗。。。好了,言归正传= ̄ω ̄=

了解概念

首先明白什么是堆,什么是完全二叉树,什么是大顶堆,相信百度一下很容易理解o(^▽^)o。

堆可以用数组来存储,如下图,数组 a[0,...,9] 表示一个堆在数组中的存储模式。数组中下标为i的节点的子节点下标分别为2*i+12*i+2,下标为j的子节点的父节点下标为(j-1)/2
堆排序Java实现(递归方式&非递归方式)

算法描述

  1. 将待排序数组构建成一个大顶堆,也就是变换原始数组中元素的位置,使之满足大顶堆的定义。
  2. 将堆顶节点与堆中末尾节点交换,也就是数组的首尾元素交换,此时末尾节点已为最大元素,考虑剩余节点形成的堆。
  3. 将最新的堆重新构造成大顶堆。
  4. 重复第2步、第3步直到堆中节点全部输出。

建议不明白的同学观看视频https://www.bilibili.com/vide...

算法实现

public class HeapSort {

    public static void heapSort(int[] array) {
        array = buildMaxHeap(array); //初始建堆,array[0]为第一趟值最大的元素
        for (int i = array.length - 1; i >= 1; i--) {
            int temp = array[0];  //将堆顶元素和堆底元素交换,即得到当前最大元素正确的排序位置
            array[0] = array[i];
            array[i] = temp;
            adjustHeap1(array, 0, i);  //整理,将剩余的元素整理成大顶堆
        }
    }

    //自下而上构建大顶堆:将array看成完全二叉树的顺序存储结构
    private static int[] buildMaxHeap(int[] array) {
        //从最后一个节点array.length-1的父节点(array.length-1-1)/2开始,直到根节点0,反复调整堆
        for(int i=(array.length-2)/2;i>=0;i--){
            adjustHeap1(array, i, array.length);
        }
        return array;

    }

    //自上而下调整大顶堆(非递归)
    private static void adjustHeap1(int[] array, int k, int length) {
        int temp = array[k]; //堆顶节点
        for (int i = 2*k+1; i <= length - 1; i = 2*i+1) {    //i为初始化为节点k的左孩子,沿节点较大的子节点向下调整

            if (i+1< length && array[i] < array[i + 1]) {  //如果左孩子小于右孩子
                i++;   //则取右孩子节点的下标
            }
            if (temp >= array[i]) {  //堆顶节点 >=左右孩子中较大者,调整结束
                break;
            } else {   //根节点 < 左右子女中关键字较大者
                array[k] = array[i];  //将左右子结点中较大值array[i]调整到双亲节点上
                k = i; //【关键】修改k值,以便继续向下调整
            }
        }
        array[k] = temp;  //被堆顶结点的值放人最终位置
        
    }

    //自上而下调整大顶堆(递归)
    private static void adjustHeap2(int[] array, int k, int length) {
        int k1=2*k+1;  
        if(k1<length-1 && array[k1]<array[k1+1]){
            k1++;
        }
        if(k1>length-1||array[k]>=array[k1]){
            return;
        }else{
            int temp = array[k];  //将堆顶元素和左右子结点中较大节点交换
            array[k] = array[k1];
            array[k1] = temp;
            adjustHeap2(array,k1,length);
        }
    }
    
    

    public static void main(String[] args) {
        int[] a = {87,45,78,32,17,65,53,9,122,133};
        heapSort(a);
        System.out.println(Arrays.toString(a));
    }
}

算法复杂度

堆排序时间计算分两部分,构建堆时间复杂度O(n),调整堆时间复杂度O(nlogn),总的时间复杂度O(nlogn),堆排序为就地排序,空间复杂度O(1)

相关推荐