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);
         }
     }
 }