堆排序
收录于
学习数据结构与算法
2021-05-17 14:29 · 阅读时长3分钟
堆排序是基于二叉堆的一种排序算法，建议先了解一下什么是堆，最大堆和最小堆，这样理解起来会更容易。堆排序的最好、最坏以及平均时间复杂度都是O(NlogN)。
算法主要思路是
- 构建一个最大堆（或者最小堆），参考二叉堆课程。
- 从最大堆中取出第一个元素arr[0]，也就是最大的元素，与数组最后一个元素arr[size-1]交换。
- 对数组中第一个元素执行下移操作，使得arr[0, size-1]子数组仍然是最大堆。
- 重复第2步，直到最大堆中所有元素取完。
下面以数组[1, 3, 2, 5, 6, 4]为例，选择使用最大堆排序。
查看二叉堆课程
注释1import java.util.Arrays;
2
3public class Main {
4
5 public static void main(String[] args) {
6 int[] arr = {1, 3, 2, 5, 6, 4};
7 heapSort(arr);
8 System.out.println(Arrays.toString(arr));
9 }
10
11 private static void heapSort(int[] arr) {
12 /**
13 * 构建最大堆，从底部第一个有子节点的元素开始向上移动
14 */
15 for (int i = arr.length / 2 - 1; i >= 0; i--) {
16 shiftDown(arr, arr.length, i);
17 }
18
19 /**
20 * 取出最大堆顶部最大元素，从后向前填充数组
21 */
22 for (int i = arr.length - 1; i >= 0; i--) {
23 swap(arr, i, 0);
24 shiftDown(arr, i, 0);
25 }
26 }
27
28 private static void shiftDown(int[] arr, int size, int i) {
29 int left = (i + 1) * 2 - 1;
30 if (left > size - 1) {
31 return;
32 }
33 int right = (i + 1) * 2;
34 int max = left;
35 if (right < size && arr[right] > arr[left]) {
36 max = right;
37 }
38 if (arr[i] >= arr[max]) {
39 return;
40 }
41 swap(arr, i, max);
42 shiftDown(arr, size, max);
43 }
44
45 public static void swap(int[] arr, int i, int j) {
46 int temp = arr[i];
47 arr[i] = arr[j];
48 arr[j] = temp;
49 }
50}
51注意: 这个Java运行环境不支持自定义包名，并且public class name必须是Main
堆排序排序算法二叉堆
1