java实现堆排序算法

懒驴 2022年12月30日 185次浏览

堆排序算法

堆排序算法: 是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。
将待排序的序列构造成一个大顶堆(从大到小排要构造成小顶堆)。此时,整个序列的最大值就是堆顶的根节点,将他和末尾元素交换,然后将剩余的length-1个节点序列重新构造成新的堆。重复执行,便能得到一个有序序列。

堆排序算法示意图

堆的操作: 在堆的数据结构中,堆中的最大值总是位于根节点(在优先队列中使用堆的话堆中的最小值位于根节点)。堆中定义以下几种操作:
最大堆调整(Max Heapify):将堆的末端子节点作调整,使得子节点永远小于父节点
创建最大堆(Build Max Heap):将堆中的所有数据重新排序
堆排序(HeapSort):移除位在第一个数据的根节点,并做最大堆调整的递归运算

Java代码实现 ↓↓↓↓↓↓↓


/***
 * 堆排序算法
 */
public class HeapSort {
    static void heapSort(int []a,int len){
        int i;
        /**把a[]构造成一个大顶堆**/
        for(i=len/2;i>=0;i--){
            HeapAdjust(a,i,len);
        }
        for(i=len;i>0;i--){
            /**交换堆顶最大元素和堆尾最小元素**/
            swap(a,0,i);
            /**把交换后的堆a[0,i-1],再次构造成大顶顶,使堆顶元素为最大值**/
            HeapAdjust(a,0,i-1);
        }
    }
    static void HeapAdjust(int []a,int start,int len){
        int temp,j;
        temp=a[start];
        /**从index最大的有孩子的节点开始筛选,堆排**/
        for(j=2*start; j<=len; j*=2){
            /**是index=j的元素为较大的元素**/
            if(j<len&&a[j]<a[j+1])
                j++;
            if(temp>=a[j])
                break;
            /**将较大元素赋值给父节点**/
            a[start]=a[j];
            start=j;
        }
        a[start]=temp;
    }
    static void swap(int a[],int low,int high){
        int temp=a[low];
        a[low]=a[high];
        a[high]=temp;
    }
    public static void main(String []args){
        int[] b = {97, 58, 3, 12, 88, 77, 101, 7, 22, 33, 44, 8, 66, 22};
        heapSort(b, b.length - 1);
        for(int w:b)
            System.out.print(" "+w);
    }
}

运行结果 ↓↓↓↓↓↓↓
运行结果