算法十大排序堆排序

Bena ·

更新时间:2024-09-20

· 963 次阅读

十种排序算法——堆排序(小顶堆) 首先要了解什么是堆？小顶堆又是什么？而堆排序是十种排序种唯一种自定义的数据结构

这里的堆就是我们所熟悉的二叉树在这里插入图片描述

而小顶堆又是什么呢？ 小顶堆就是根节点比子节点小，子节点比叶子节点小。

所以我们第一步是进行堆化，从它倒数第一个子节点进行堆化(从右到左)
在这里插入图片描述

它检查完了之后它的兄弟节点再检查
在进行交换子节点始终比叶子节点小
在这里插入图片描述

当交换完成之后再返回它的父节点进行检查

在这里插入图片描述

请注意在每次交换完成之后好要下沉，看一下它的子节点或者是叶子节点是否有比它小的

在这里插入图片描述
当下沉完成之后，同理在检查它的兄弟节点

当检查完之后再返回它的子节点，子节点进行下沉

在这里插入图片描述

到这里我们堆化完成了接下来，把堆顶0号元素和最后一位元素对调

在这里插入图片描述
对调完成之后，不在考虑它对调的那个位置了
在进行向下调整

然后根节点再和最后那个位置交换了(注意不考虑之前交换的位置)

在继续下沉，和最后可以考虑的位置进行交换
最后就交换下沉就如下图所示
在这里插入图片描述
在输出就可以了

import java.util.Scanner;
public class _堆排序小顶堆 {
	  public static void main(String[] args) {
		    Scanner sc =new Scanner(System.in);
//		     int n=sc.nextInt();
		     int A[]  = {1,2,9,7,6,3,4,2};
		     sort(A);
		     for (int i = 0; i =0; i--) {
		            MinHeapFixDown(A,i,n);
	          }
     }
    private static void MinHeapFixDown(int[] A,int i,int n) {
	           //找到左右孩子
    	       int left = i*2+1;
    	       int right= i*2+2;
    	       //如果左孩子已经越界，i就是叶子节点
    	       if(left>=n)return; 
    	        int min=left;
    	        if(right<n){
    	           if(A[right]<A[left]) {
    	        		min=right;
    	        	}
    	        } 
    	        //min指向了left和right中的最小的那个
    	       //如果A[i]比两个孩子小不用调整
    	       if(A[i]=0 ; x--) {
    		  int  temp=A[0];
    		  A[0]=A[x];
    		  A[x]=temp;
    		  //缩小堆的范围，对堆顶进行向下调整
    		  MinHeapFixDown(A,0,x);
		}
         }  
}

作者：HUANGCI666

堆排序算法排序

1024 个赞