亿行代码
十大排序之堆排序（HeapSort）
4.14
简介
堆排序（英语：Heapsort）是指利用堆这种数据结构所设计的一种排序算法。
堆排序的时间复杂度是：O(nlogn) 空间复杂度：O(1).
说到堆排序就不得不提到完全二叉树了。什么是完全二叉树呢？
完全二叉树定义：
若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。
一颗普通的完全二叉树：
我们把堆又分为大根堆和小根堆，
大根堆：根结点的键值是所有堆结点键值中最大者，在堆排序算法中用于升序排列。
小根堆：根结点的键值是所有堆结点键值中最小者，在堆排序算法中用于降序排列；
4.14
图解步骤
利用堆排序的实现排序的思路也很简单：
第一步、将待排序数组构建成一个堆（大根堆或者小根堆，一般用大根堆来升序 排序）；
第二步、把堆首（最大值）和堆尾互换；取出最大的元素（此时堆个数减一）；
第三步、重新构建大根堆；
第四步、重复第二步，第三步，知道堆的大小为1，完成排序。
图解：
假设待排序数组：1，5，2，12，10，9
假设我们使用大根堆来排序：
将堆首元素和堆尾元素交换：
剔除最后一个元素，然后将剩下的元素，重新构建成一个堆。
继续交换堆首元素和堆尾元素
剔除最后一个元素，然后将剩下的元素，重新构建成一个堆。
交换：
剔除，构建堆。
交换，剔除。
交换，剔除。
最终完成排序：
1 2 5 9 10 12
4.14
代码实现
package com.znzz.heapSort;import java.util.Arrays;public class HeapSort {public static void main(String[] args) {int[] arr = {2,4,1,8,20,3,6};new HeapSort().heap_sort(arr, arr.length);System.out.println(Arrays.toString(arr));}/**** @param arr 待排数组* @param n 数组元素* @param i 对哪个节点做heapify*/void heapify(int arr[], int n, int i){if(i >= n){return;}int c1 = 2 * i + 1;int c2 = 2 * i + 2;int max = i;if(c1 < n && arr[c1] > arr[max]){max = c1;}if(c2 < n && arr[c2] > arr[max]){max = c2;}if(max != i){swap(arr,max ,i);heapify(arr,n,max);}}private void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}void build_heap(int arr[], int n){int last_node = n -1;int parent = (last_node -1) /2;int i;for (i = parent; i >= 0; i--) {heapify(arr,n,i);}}void heap_sort(int arr[], int n){build_heap(arr,n);for (int i = n -1; i >= 0 ; i--) {swap(arr,i,0);heapify(arr,i ,0);}}}
小根堆排序（即降序排列）只需要把arr[c1] > arr[max] 和arr[c2] > arr[max] 中条件改为小于即可。
如果该文章对你有帮助，"再看"和"点赞"是对我最大的鼓励！
扫二维码｜关注我们
谢谢观看
把城市夜晚的喧嚣，点出来
▼
