排序算法之堆排序

title: 排序算法之堆排序

date: 2021-08-10

tags: 数据结构

categories: 排序算法

堆排序

堆排序是排序算法中的一种，这里的堆是指的二叉堆，顾名思义，二叉堆是完全二叉树或者近似完全二叉树，时间复杂度稳定在O(nlog2n)

堆的性质

1. 堆是一颗完全二叉树
2. 每个节点的值都大于或者小于其子节点的值，大于为最大堆；小于为最小堆

用堆做排序，就需要把数组转换成堆，

首先创建堆

public HeapSort{
    public static void main(String[] args){
        int[] nums = {3,2,1,5,6,4};
        HeapSort(nums);
        
    }
   	static void HeapSort(int[] nums){
        //第一步，先建立堆
        BuildHeap(nums);
        //从堆的末尾取出最小值，放到数组的前面，然后继续调整堆，又出现新的最大堆
        //利用循环可以求得顺序数组
        for(int i=arr.length-1;i>=1;i--){
            int t = arr[i];
            arr[i]=arr[0];
            arr[0]=t;
            Heapify(arr,0,i-1);
        }
    }
    //开始堆排序
    void BuildHeap(int[] nums){
        for(int i = nums.length/2-1;i>=0;i--){
            Heapify(nums,i,nums.length-1);
        }
    }
    //建立堆的时候需要调整堆
    staic void Heapify(int[] nums, int index, int len){
        //找到左右
        int leftson = (index<<1)+1;
        int rightson = (index<<1)+2;
        int temp=0;
        if(leftson<=len && right<=len){
            //求左右孩子节点中较大的
            temp = nums[leftson] > nums[rightson] ? leftson:rightson;
        }
        else if(leftson<=len){
            temp = leftson;
        }
        else if(rightson<=len){
            temp = rightson;
        }
        else return;
        
        if(nums[index] < nums[temp]){
            int t = nums[index];
            nums[index] = nums[temp];
            nums[temp] = t;
            Heapify(nums,temp,len);
        }
    }
}