堆排序（Java)

排序原理

大顶堆：在大顶堆中，所有父节点的值>=孩子结点的值

堆排的思想在于每次排序通过父节点与孩子结点的值的比较，确定每一个元素位置。每轮堆排过后，根节点的值就是目前堆中参与排序的最大的值，将它调整到数组尾部，然后缩小需要排序的数组长度，此处思想类似于冒泡排序

代码演示

    /*
		k表示开始堆排的位置
		limit表示当前未排序数组尾部坐标
	*/
    public static void adjust(int[] arr,int k,int limit){  
        int temp=arr[k];                   //将arr[k]中存放的值用temp暂存，且将该值放到堆中合理的位置
        for(int i=2*k+1;i<=limit;i*=2){   //arr[2*k+1]即arr[i]代表arr[k]的左孩子，arr[2*k+2]即arr[i+1代表arr[k]右孩子
            if(i<limit&&arr[i]<arr[i+1]){  //arr[i]表示当前arr[k]两个孩子中的较大值
                i++;
            }
            if(temp>=arr[i]){            //若当前temp的值大于两个孩子节点的值，则temp已经处在了合适的位置
                break;
            }else{
                arr[k]=arr[i];          //将较大孩子的值放到父节点上，符合大顶堆的要求
                k=i;                   //将k替换为i，则下次比较temp与arr[i]的双孩子值进行比较
            }
        }
        arr[k]=temp;
    }
    
   public static void headpSort(int[] arr){
        int len=arr.length;
        for(int i=len/2;i>=0;i--){  //准备工作，初始搭建大顶堆
            adjust(arr,i,len-1);    //从len/2开始调整，确保循环结束后，所有节点满足大顶堆结构
        }
        //此时，堆顶元素为最大元素
        for(int i=len-1;i>=1;i--){  //每次确定当前无序数组最大元素后，就将最大元素挪动到当前无序数组尾部，然后需要排序的数组长度-1，即limit-1
            int temp=arr[0];
            arr[0]=arr[i];
            arr[i]=temp;
            adjust(arr,0,i-1);
        }
    }

验证代码

import java.util.Arrays;
public class HeapSort {
    public static void main(String[] args) {
        int[] arr={0 ,1, 3, 65, 5, 798595, 10};
        headpSort(arr);
        System.out.println(Arrays.toString(arr));
    }
    public static void headpSort(int[] arr){
        int len=arr.length;
        for(int i=len/2;i>=0;i--){
            adjust(arr,i,len-1);
        }
        for(int i=len-1;i>=1;i--){
            int temp=arr[0];
            arr[0]=arr[i];
            arr[i]=temp;
            adjust(arr,0,i-1);
        }
    }
    public static void adjust(int[] arr,int k,int limit){
        int temp=arr[k];
        for(int i=2*k+1;i<=limit;i*=2){
            if(i<limit&&arr[i]<arr[i+1]){
                i++;
            }
            if(temp>=arr[i]){
                break;
            }else{
                arr[k]=arr[i];
                k=i;
            }
        }
        arr[k]=temp;
    }
}

实验结果

输入数组：{0 ,1, 3, 65, 5, 798595, 10}
输出数组：{0, 1, 3, 5, 10, 65, 798595}

如图所示， 实验结果符合预期