java写的堆排序 代码
参照改写自http://blog.kingsamchen.com/archives/547#viewSourcepublic class HeapSorter {int temp = 0;/* * 输 入: Ary(int[]) - 排序数组 nIndex(int) - 起始下标 nHeapSize(int) - 堆大小 输 * 出: - 功 能: 从nIndex开始检查并保持最大堆性质 */void MaxHeapify(int Ary[], int nIndex, int nHeapSize) {while (true) {int nL = left(nIndex);int nR = right(nIndex);int nLargest;if (nL <= nHeapSize && Ary < Ary) {nLargest = nL;} else {nLargest = nIndex;}if (nR <= nHeapSize && Ary < Ary) {nLargest = nR;}if (nLargest != nIndex) {// 调整后可能仍然违反堆性质swap(Ary, nLargest, nIndex);nIndex = nLargest;} else {break;}}}/* * 输 入: Ary(int[]) - 排序数组 nHeapSize(int) - 堆大小(zero-based) 输 出: * - 功 能: 将一个数组改造为最大堆 */void BuildMaxHeap(int Ary[], int nHeapSize) {for (int i = parent(nHeapSize); i >= 0; --i) {MaxHeapify(Ary, i, nHeapSize);}}/* * 输 入: Ary(int[]) - 排序数组 nCount(int) - 元素个数 输 出: - 功 能: * 对一个数组进行堆排序 */void HeapSort(int Ary[], int nCount) {int nHeapSize = nCount - 1;BuildMaxHeap(Ary, nHeapSize);for (int i = nHeapSize; i >= 1; --i) {swap(Ary, 0, i);--nHeapSize;MaxHeapify(Ary, 0, nHeapSize);}}private void swap(int[] array, int index1, int index2) {temp = array;array = array;array = temp;}private int left(int x) {return (x << 1) + 1;}private int right(int x) {return (x + 1) << 1;}private int parent(int x) {return ((x + 1) >> 1) - 1;}public static void main(String[] s) {int a[] = {6, 16, 4, 10, 14, 7, 9, 3, 2, 8, 1 };new HeapSorter().HeapSort(a, 10);for (int i : a) {System.out.print(i + ",");}}}
输出结果是:1,2,3,4,6,7,8,9,10,14,16,
未做优化.原文就不贴出了
页:
[1]