java算法排序之堆排序

package 十大排序; import com.sun.org.apache.bcel.internal.generic.SWAP; public class 堆排序2 { public static void main(String[] args) { int[] arr={10,9,11,8,7,13,2,1,12}; sort(arr); for (int i : arr) { System.out.print(i); System.out.print(" "); } } private static void sort(int[] A) { int n = A.length; //先进行堆化 MinHeap(A); for (int x = n - 1; x >= 0; x--) { //把堆顶0号元素对调 int temp = A[0]; A[0] = A[x]; A[x] = temp; MinHeapFixDown(A, 0, x - 1); } } private static void MinHeap(int[] A) { int n = A.length; for (int i = n / 2 - 1; i >= 0; i--) { MinHeapFixDown(A, i, n); } } private static void MinHeapFixDown(int[] A, int tip, int n) { //找到左右孩子 int left = 2 * tip + 1; int right = 2 * tip + 2; //左孩子已经越界,那tip就是子节点 if (left >= n) { return; } int max = left; if (right >= n) { // min =left; } else if (A[right] > A[left]) { max = right; } //min指向左右孩子较小的那个 //与tip比较 if (A[tip] < A[max]) { //交换 int temp = A[tip]; A[tip] = A[max]; A[max] = temp; } else { return; } //递归 MinHeapFixDown(A, max, n); } }