- 空间复杂度
仅使用了常数个辅助单元,空间复杂度是O(1)。
- 时间复杂度
在最好、最坏平均情况下,堆排序的时间复杂度是O(n*log2n)。
- 代码实现
/** * 源码名称:HeapSort.java * 日期:2014-08-12 * 程序功能: 堆排序 * 版权:CopyRight@A2BGeek * 作者:A2BGeek */ public class HeapSort { public void adjustHeap(int[] in, int index, int length) { int leftcIndex = index * 2 + 1; int rightcIndex = index * 2 + 2; int bigest = index; while (leftcIndex < length || rightcIndex < length) { if (leftcIndex < length && in[leftcIndex] > in[bigest]) { bigest = leftcIndex; } if (rightcIndex < length && in[rightcIndex] > in[bigest]) { bigest = rightcIndex; } if (index == bigest) { break; } else { in[index] = in[index] + in[bigest]; in[bigest] = in[index] - in[bigest]; in[index] = in[index] - in[bigest]; index = bigest; leftcIndex = index * 2 + 1; rightcIndex = index * 2 + 2; } } } public void createHeap(int[] in) { int length = in.length; for (int i = length / 2; i >= 0; i--) { adjustHeap(in, i, length); printArray(in); } } public void printArray(int[] in) { for (int i : in) { System.out.print(i + " "); } System.out.println(); } public static void main(String[] args) { HeapSort heapSort = new HeapSort(); int[] testCase = { 1, 3, 4, 2, 10, 11, 45, 6 }; heapSort.createHeap(testCase); int length = testCase.length; while (length > 1) { testCase[0] = testCase[0] + testCase[length - 1]; testCase[length - 1] = testCase[0] - testCase[length - 1]; testCase[0] = testCase[0] - testCase[length - 1]; heapSort.adjustHeap(testCase, 0, --length); } System.out.println("#########################"); heapSort.printArray(testCase); } }