关于堆排序的整理

每生成一次大（小）顶堆， 将数组首位（顶）与最后一位交换， 使数组减小一位，继续生成大（小）顶堆， 这样就依次将剩余数列中的最大最小元素取出，生成有序列表。 /*  *代码实现  * */ 1.想要实现堆排序，首先要保证是完全二叉树      只要让任何一个节点 i 的左节点= 2*i+1                                          右节点=2*i+2      保证不越界。 2.写一个递归方法      保证从最右下角的第一个非叶子节点k，在这个三点的小二叉树子树中的根节点是最大的      然后 k-- 递归调用本方法           注意：这里判断是否是最后一个节点的条件应为< size      得到最大顶堆 3.将最大顶堆的根节点与最后一个节点调换，然后 size减一，再调用递归方法。

4.重复2，3步骤得到有序数列。

java代码

package heap; import java.util.LinkedList; import java.util.List; /** * 堆排序的实现 * 撸的吐血 * @author Administrator * */ public class HeapifySort { public static void main(String[] args) { // 先初始化数组，并得到数组元素的个数。 int[] a={5,6,9,3,2,4,1,7,8}; int size=a.length; System.out.println(size); //生成完全二叉树 List<TreeNode> by=binary(a,size); /* for (int i=0;i<size;i++){ System.out.println(by.get(i).val); }*/ //递归生成最大顶堆的方法了 heapifySort(by,size); for (int i=0;i<size;i++){ System.out.println(by.get(i).val); } } //递归生成最大顶堆的方法了 private static void heapifySort(List<TreeNode> by,int size) { // TODO Auto-generated method stub for(int i=size-1;i>=0;i--){ if(by.get(i).left!=0){ int largest=by.get(i).val; //System.out.println(by.get(i).val); //存在右子叶的话 if(by.get(i).right<size){ //右子叶的值小于左子叶的值 if(by.get(by.get(i).right).val<by.get(by.get(i).left).val){ if(largest<by.get(by.get(i).left).val){ largest=by.get(by.get(i).left).val; by.get(by.get(i).left).val=by.get(i).val; by.get(i).val=largest;} }else{ //右子叶的值不小于左子叶的值 if(largest<by.get(by.get(i).right).val){ largest=by.get(by.get(i).right).val; by.get(by.get(i).right).val=by.get(i).val; by.get(i).val=largest; } } // if(largest<by.get(by.get(i).right).val){ // } }else if(by.get(i).left<size){ //不存在右子叶的话 if(largest<by.get(by.get(i).left).val){ largest=by.get(by.get(i).left).val; by.get(by.get(i).left).val=by.get(i).val; by.get(i).val=largest; } } } System.out.print("P"+by.get(0).val); } //下面要去置换出最大顶 if(size>0){ change(by,size-1); size--; heapifySort(by,size); } } public static List<TreeNode> change(List<TreeNode> by,int size){ int temp=by.get(0).val; by.get(0).val=by.get(size).val; by.get(size).val=temp; return by; } //生成完全二叉树 public static List<TreeNode> binary(int a[],int size){ /* * List是一个接口， * 如user_pyw所讲，不能直接new List，而应该使用ArrayList或者LinkedList（这些实现了List接口） */ List<TreeNode> by = new LinkedList<TreeNode>(); for(int i=0;i<size;i++){ TreeNode tn=new TreeNode(a[i]); if(2*i+1<size) tn.left=2*i+1; if(2*i+2<size) tn.right=2*i+2; by.add(tn); } return by; } } class TreeNode{ int val; //节点的数值 int left; //左节点的数组中的下标 int right; //右节点的数组中的下标 public TreeNode(int x){ val=x; } } 第一次写，写的好乱，不知有没有错，帮忙指摘一下~~