Java排序算法之 —— 堆排序
package algorithm.sort;/** * 堆排序算法：首先建立最大堆，因为最大元素在根A，所以将其与最后一个元素交换 * 然后去除最后一个节点，重新调整最大堆，循环此过程 * @author Administrator * */public class HeapSort {//堆排序public void heapSort(int[] a) {int heapSize =a.length;//建立最大堆buildMaxHeap(a, heapSize);//从最后一个元素开始循环for (int i = a.length-1; i > 0; i--) {//交换最大元素与最后一个元素exchange(a, i, 0);//重新调整根节点为最大堆keepMaxHeapify(a, 0, --heapSize);}}//给定一个数组，建立最大堆public void buildMaxHeap(int[] a, int heapSize) {//对数中每一个不是叶节点的节点调用for (int i = heapSize/2; i>=0; i--) {keepMaxHeapify(a, i, heapSize);//keepMaxHeapifyNoRecurisive(a, i, heapSize);}}//保持最大堆性质，使以i为根的子树为最大堆（采用递归方法）public void keepMaxHeapify(int[] a, int i, int heapSize) {int left = left(i);int right = right(i);int largest = i;if (left < heapSize && a > a) {largest = left;}if (right < heapSize && a > a) {largest = right;}if (largest != i) {exchange(a, largest, i);keepMaxHeapify(a, largest, heapSize);}}//非递归方法保持最大堆性质public void keepMaxHeapifyNoRecurisive(int[] a, int i, int heapSize) {int largest = i;while (largest < heapSize) {int left = left(i);int right = right(i);if (left < heapSize && a > a) {largest = left;}if (right < heapSize && a > a) {largest = right;}if (largest == i) break;exchange(a, largest, i);i = largest;}}//父节点（考虑java中下标从0开始）public int parent(int i) {//return (i-1) / 2;return (i-1) >> 1;//二进制计算法}//左孩子public int left(int i) {//return i * 2 + 1;return (i << 1)+1;}//右孩子public int right(int i) {//return (i + 1) * 2;return (i + 1) << 1;}//交换元素public void exchange(int[] a, int i, int j) {int temp = a;a = a;a = temp;}//打印数组public void printArr(String str, int[] a) {System.out.print(str + "\t");for(int i = 0; i < a.length; i++)System.out.print(a + " ");System.out.println();}//测试数组public static void main(String[] args) {int[] a = {4, 1, 3, 2, 16, 9, 10, 14, 8, 7};HeapSort hs = new HeapSort();hs.printArr("原始数组为：", a);hs.buildMaxHeap(a, a.length);hs.printArr("建立最大堆为：", a);hs.heapSort(a);hs.printArr("堆排序后为：", a);}}//output~
原始数组为：4 1 3 2 16 9 10 14 8 7
建立最大堆为：16 14 10 8 7 9 3 2 4 1
堆排序后为：1 2 3 4 7 8 9 10 14 16
页:
[1]