十大排序算法之堆排序

x33g5p2x  于10个月前 转载在 其他  
字(1.5k)|赞(0)|评价(0)|浏览(102)

十大排序算法之堆排序

本文采用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);
        }
    }
}

相关文章