排序算法 - 堆排序

文章目录

目录

文章目录

前言

1 . 堆排序原理

2 . 堆排序实现 

总结

前言

大家好,今天给大家介绍一下常见排序算法中的堆排序(填坑)

1 . 堆排序原理

堆排序是一种基于二叉堆数据结构的排序算法，它利用堆的性质进行排序。堆是一种完全二叉树，分为最大堆和最小堆两种类型。在堆排序中，通常使用最大堆进行排序。

堆排序的基本思想如下：

1. 将待排序的序列构建成一个最大堆。
2. 交换堆顶元素（最大元素）和堆中最后一个元素，然后将剩余元素重新调整为最大堆。
3. 重复以上步骤，直到所有元素都被取出，最终得到一个有序序列。

具体建堆操作请访问http://t.csdnimg.cn/FMnMP介绍的很详细,不再过多赘述了

2 . 堆排序实现 

import java.util.Arrays;

/**
 * 堆排序
 */
public class HeapSort {
    private static final int[] array = { 27,15,19,18,28,34,65,49,25,37 };

    /**
     * 左子节点: 2*i  右字节点 2*i+1
     * @param args
     */
    public static void main(String[] args) {
        sort();
        System.out.println(Arrays.toString(array));
    }

    public static void sort(){
        createHeap();
        System.out.println(Arrays.toString(array));
        for(int i = 0; i<array.length; i++){
            swap(0,array.length-i-1);
            HeapAdjust(0,array.length-1-i-1);
        }
    }

    public static void createHeap(){
        for(int i = array.length/2+1; i>=0; i--){
            HeapAdjust(i,array.length-1);
        }
    }

    public static void HeapAdjust(int start,int end){
        int parent = start;
        int child = 2*parent+1;
        while(child <= end){
            // 找出左右孩子中最大值
            if(child+1 <= end && array[child] < array[child+1]) child++;

            if(array[parent] < array[child]){
                swap(parent,child);
                parent = child;
                child = 2*parent+1;
            }else{
                break;
            }
        }
    }

    public static void swap(int i,int j){
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
}

总结

以上就是这篇博客的主要内容了,大家多多理解,下一篇博客见!