Java实现堆排序

import java.util.Scanner;

/*堆是一种数据结构，类似于一棵完整的二叉树。
 * 思想：堆的根节点值最大（最小），将无序序列调整成一个堆，就能找出这个序列的最大值（最小值），将找出的值交换到序列的最后或最前，
 * 这样有序序列元素增加1个，无序序列元素减少1个，对新的无序序列重复这样的操作，就实现了排序。即：1.建堆2.排序
 * 对排序过程（大顶堆）：
 * （1）从无序序列所确定的完全二叉树的第一个非叶子节点（n/2）开始,从右到左，从下到上，对每个节点进行调整，最终的到大顶堆
 * 对节点的调整方法：将当前节点（a）的值与其孩子节点进行比较，如果存在大于a的孩子节点，从中选出最大的的一个和a进行交换，当
 * a到下一层时重复上述过程，直到a的孩子节点值都小于a为止
 * （2）将当前无序序列的第一个元素（a），即树的根节点与当前无序序列的最后一个元素（b）交换。a进入有序序列，达到最终位置。
 * 无序序列中元素减少1个，有序序列中元素增加1个，此时只有节点b不满足堆定义，对它进行调整
 * （3）重复（2）中过程，直到无序序列中的元素剩下一个时排序结束
 ** 时间复杂度O（nlog2(n)）[2是底]
 ** 空间复杂度O（1）*/
/*适合记录多的排序*/
/*将array[0，...，n-1]看成是一颗完全二叉树的顺序存储结构,利用完全二叉树中双亲节点和孩子结点之间的内在关系.*/
public class heapsort {

    public static void main(String[] args){
        Scanner cin = new Scanner(System.in);
        String str = cin.nextLine();
        String[] st = str.split(" ");
        int[] c = new int[st.length+1];
        for(int i=0;i<st.length;i++){
            c[i+1]=Integer.parseInt(st[i]);
        }
        sort(c);
        for(int i=1;i<c.length;i++){
            System.out.print(c[i]);
            System.out.print(" ");
        }
        
        cin.close();
    }
    //完成R[low]到R[high]范围内对low的调整
    //默认R是一个完全二叉树的顺序存储
    public static void sift(int[] R,int low,int high){
        int i=low,j=i*2;
        int temp = R[i];;
        while(j<=high){ 
            if(j<high&&R[j]<R[j+1]){
                j++;
            }
            if(temp<R[j]){
                R[i]=R[j];
                i=j;
                j=2*i;
            }else{
                break;
            }
        }
        R[i]=temp;
    }
    //堆排序
    public static void sort(int[] R){
        int i,j;
        int n = R.length-1;
        int temp;
        for(i=n/2;i>=1;--i){//初始化（大根）堆
            sift(R,i,n);
        }
        //堆排序
        for(j=n;j>=2;j--){
            temp=R[1];
            R[1]=R[j];
            R[j]=temp;
            sift(R,1,j-1);
        }
    }
}