[数据结构与算法]十大排序算法之堆排序

十大排序算法之堆排序

本文采用Java书写选择排序，其他语言类似可以借鉴着写

• 思想：所谓堆排序就是通过构造最大堆（升序）或者最小堆（降序）来进行排列的方法。可能有些童鞋不知道何为最大堆，何为最小堆。这里来给大家简单说明一下，最大堆：也就是构造完成一个完全二叉树，父节点均大于子节点；同理最小堆为均小于子节点。堆排序的重点就是构造最大堆或者最小堆，然后依次提取出根节点元素，放在最后。再对之前的重新构造最大堆或者最小堆，重复执行，直到堆中仅剩一个元素。最大堆和最小堆因为都是完全二叉树, 因此满足完全二叉树的性质，可以利用数组进行存储。点击了解详情
• 效果图：
  
  效果图可能不太明显，这里我又找了两个图片便于大家理解
  
  
  

算法复杂度和稳定性

• 稳定性：
  不稳定，相同两个元素可能发生值得交换
• 复杂度：
  时间复杂度：O(NlogN)
  空间复杂度：O(1)

代码实现

package Sort;

/**
 * @Description:
 * @ProjectNmae: gitTest
 * @PackageName: Sort
 * @ClassName: HeapSort
 * @Author: Y-peak
 * @Date: 2021.09.13 00:08   星期一
 */

public class HeapSort {
    public static void heapSort(int [] arr){
        if(arr == null || arr.length<2)
            return;
        for(int i = 0; i < arr.length; i++){ //生成最大堆，也就是大根堆
            heapInsert(arr,i);
        }
        int heapSize = arr.length; //堆的大小
        swap(arr,0, --heapSize); //根节点与最后一个结点互换，将最后一个结点从堆中删除。也就是将最大值排在了最后
        while (heapSize>0){
            heapify(arr, 0 , heapSize);
            swap(arr,0,--heapSize);
        }
    }

    //在将处于index处位置的数，持续上移
    public static void heapInsert(int[] arr, int index){
        while (arr[index] > arr[(index - 1) / 2])
        {
            swap(arr, index, (index - 1) / 2);
            index = (index - 1) / 2;
        }
    }
    public static void swap(int[] arr, int i, int j){
        int temp;
        temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    //在将处于index处位置的数，持续下移
    public static void heapify(int[] arr, int index, int heapSize){
        int left = index*2+1; //左孩子下标
        while (left < heapSize){
            int largest = left+1 < heapSize && arr[left+1] > arr[left]?left + 1:left; //选出子孩子中较大的进行交换
            largest = arr[largest] > arr[index] ? largest:index; //选出父节点与子节点中较大的
            if(largest == index)
                break; //停止
            swap(arr, largest, index);
            index = largest;
            left = index* 2+1;
        }
    }

    public static void main(String[] args) {
        int[] arr = new int[]{24,29,45,73,24,89,90};
        heapSort(arr);
        for (int i :arr){
            System.out.println(i);
        }
    }
}