堆排序

Heap类：
import java.util.ArrayList;
public class HeapSort {
private ArrayList<Integer> list = new ArrayList<Integer>();

public HeapSort(Integer[] list){
for(int i=0;i<list.length;i++){
this.add(list[i]);
}
}

public void add(Integer newInt){
list.add(newInt);
int currentIndex = list.size()-1;
while(currentIndex > 0){
int parentIndex = (currentIndex-1)/2;
if(list.get(currentIndex)>list.get(parentIndex)){
int temp = list.get(parentIndex);
list.set(parentIndex, list.get(currentIndex));
list.set(currentIndex, temp);
}else
break;
currentIndex = parentIndex;
}
}

public Integer remove(){
if(list.size() == 0) return null;
int removeInt = list.get(0);
list.set(0, list.get(list.size()-1));
list.remove(list.size()-1);
int currentIndex = 0;
while(currentIndex < list.size()-1){
int leftChildIndex = currentIndex*2+1;
int rightChildIndex = currentIndex*2+2;
if(leftChildIndex >= list.size()){
break;
}
int maxIndex = leftChildIndex;
if(rightChildIndex < list.size()){
if(list.get(rightChildIndex)>list.get(leftChildIndex)){
maxIndex = rightChildIndex;
}
}

if(list.get(maxIndex)>list.get(currentIndex)){
int temp = list.get(currentIndex);
list.set(currentIndex, list.get(maxIndex));
list.set(maxIndex, temp);
currentIndex = maxIndex;
}else
break;
}
return removeInt;
}
}
使用Heap类排序：
public class HeapSortMain {
public static void heapSort(Integer[] list){
HeapSort heap = new HeapSort(list);
for(int i=list.length-1;i>=0;i--){
list[i] = heap.remove();
System.out.println("list.size = "+list.length+" ,i = "+i+" , "+list[i]);
}
}

public static void main(String[] args) {
Integer[] list = {2,3,2,5,6,1,-2,3,14,12};
heapSort(list);
for(int i=0;i<list.length;i++){
System.out.print(list[i]+" ");
}
}
}

输出结果：
list.size = 10 ,i = 9 , 14
list.size = 10 ,i = 8 , 12
list.size = 10 ,i = 7 , 6
list.size = 10 ,i = 6 , 5
list.size = 10 ,i = 5 , 3
list.size = 10 ,i = 4 , 3
list.size = 10 ,i = 3 , 2
list.size = 10 ,i = 2 , 2
list.size = 10 ,i = 1 , 1
list.size = 10 ,i = 0 , -2
-2 1 2 2 3 3 5 6 12 14