java 实现堆排序

排序类：

package heap; public class HeapSort { private int[] list; public HeapSort(int[] list) { this.list = list; } /** * 调整堆,从最后一个非叶子结点开始调整 * @param i ：调整的起始位置 * @param size ：调整列表的尺寸大小 */ private void AdjustHeap(int i,int size) { int nleftChild = 2 * i; int nRightChild = 2 * i + 1; int tmp = i; //记录调整的位置，用来记录待调整的左孩子或者右孩子在数组中的索引 if( i < size / 2) { if(nleftChild < size && list[nleftChild] >= list[tmp]) { tmp = nleftChild; } if(nleftChild < size && list[nRightChild] >= list[tmp]) { tmp = nRightChild; } if(tmp != i) //此时满足交换条件，如果左孩子与最后一个非叶结点满足交换条件，则交换，同理，右孩子亦是如此 { int Tmp = list[tmp]; list[tmp] = list[i]; list[i] = Tmp; AdjustHeap(tmp,size); //递归调整 } } } /** * 从最后一个非叶结点处倒序调整为堆 * @param i * @param size */ private void BuildHeap(int size) { for(int i = size / 2 ;i>= 0;i--) { AdjustHeap(i,size); } } public void Sort() { BuildHeap(list.length); //先建立堆 for(int i = list.length - 1;i>0;i--) { int Tmp = list[0]; list[0] = list[i]; list[i] = Tmp; AdjustHeap(0,i); } } public void print() { for(int i=0;i<list.length;i++) { System.out.print(" " +list[i]); } } }

测试：

package heap; public class MainClass { /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub int[] list = {-9,8,1,2,5,4,7,6,3,9}; HeapSort hs = new HeapSort(list); hs.Sort(); hs.print(); } }