首页 > 代码库 > 【数据结构与算法】堆排序
【数据结构与算法】堆排序
堆排序的时间复杂度是O(nlogn),下面上代码
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 { int sum = in[index] + in[bigest]; in[bigest] = sum - in[bigest]; in[index] = sum - 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) { int sum = testCase[0] + testCase[length - 1]; testCase[0] = sum - testCase[0]; testCase[length - 1] = sum - testCase[0]; heapSort.adjustHeap(testCase, 0, --length); } System.out.println("#########################"); heapSort.printArray(testCase); } }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。