## 堆排序 * 空间复杂度：O(N) * 时间复杂度：O(nLogN) ## 思路描述 其实是利用了堆的特点。 先将元素入堆，再依次取出堆顶，则可完成排序。 ### 系统堆排序 ~~~ /** * 优先队列排序 * 实质就是堆排序 * 大根堆，小根堆 * 堆操作：heapInsert(入堆）, heapify（堆化） */ public class PriorityQueueSort { public static void main(String[] args) { Stopwatch sw = Stopwatch.createStarted(); int[] nums = {13,7,4,6,9,24,12,3,5,2,11,22,41,23,12,18}; System.out.println("old:"+ Arrays.toString(nums)); System.out.println("result:"+Arrays.toString(sort(nums))+"耗时:"+sw.elapsed(TimeUnit.MILLISECONDS)+"ms"); } public static int[] sort(int[] nums){ // 优先队列排序 PriorityQueue<Integer> queue = new PriorityQueue<>(); for(int num : nums){ queue.offer(num); } int i=0; while (!queue.isEmpty()){ nums[i] = queue.poll(); i++; } return nums; } } ~~~ ### 自实现堆排序 先查看如何自实现一个堆结构，[集合数组实现堆](%E9%9B%86%E5%90%88%E6%95%B0%E7%BB%84%E5%AE%9E%E7%8E%B0%E5%A0%86.md) ~~~ /** * 自实现堆排序 * 实质就是堆排序 * 大根堆，小根堆 * 堆操作：heapInsert(入堆）, heapify（堆化） */ public class HeapSort { public static void main(String[] args) { Stopwatch sw = Stopwatch.createStarted(); int[] nums = {13,7,4,6,9,24,12,3,5,2,11,22,41,23,12,18}; System.out.println("old:"+ Arrays.toString(nums)); System.out.println("result:"+Arrays.toString(sort(nums))+"耗时:"+sw.elapsed(TimeUnit.MILLISECONDS)+"ms"); } public static int[] sort(int[] nums){ // 优先队列排序 Heap<Integer> heap = new Heap<>(); for(int num : nums){ heap.insert(num); } int i=0; while (!heap.isEmpty()){ nums[i] = heap.pop(); i++; } return nums; } } ~~~