## 堆排序 * 空間復雜度：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; } } ~~~