堆排序
package changsheng.algorithms.sort;
import changsheng.algorithms.util.Swap;
public class HeapSort {
private int heapSize = 0;
public void Sort(int[] a) {
heapSize = a.length;
/*构建大顶堆*/
BuildMaxHeap(a);
/*将大顶堆的第一个元素a[1]最大元素与数组最后的元素进行交换*/
for (int i = a.length - 1; i >=2; i--) {
Swap.swap(a,1,i);
/*由于已经移除了堆顶元素,所以在下次构建时将少一个堆元素*/
heapSize--;
/*自顶向下的重新建堆,而且不是根节点的左子树就是右子树*/
MaxHeapify(a,1);
}
}
/**
* 建堆时必须自底向上建立
*/
private void BuildMaxHeap(int[] a) {
int len = a.length;
for (int i = len / 2; i >= 1; i--) {
MaxHeapify(a, i);
}
}
/**
* 自顶向下
*/
private void MaxHeapify(int[] a, int i) {
int left = 2 * i;
int right = 2 * i + 1;
int largest = i;
if (left < heapSize && a[left] > a[largest]) {
largest = left;
}
if (right < heapSize && a[right] > a[largest]) {
largest = right;
}
if (largest != i) {
Swap.swap(a,i,largest);
MaxHeapify(a, largest);
}
}
}