堆排序算法

相关知识点

• 大顶堆实现升序排序，小顶堆实现降序排序

• 堆排序是基于堆结构实现

• 堆是完全二叉树，父节点的索引为 i，左孩子节点的索引为 2*i + 1，右孩子节点的索引为 2*i + 2

  大顶堆：arr[i] >= arr[2*i + 1]  && arr[i] >= arr[2*i + 2]
  
  小顶堆：arr[i] <= arr[2*i + 1]  && arr[i] <= arr[2*i + 2]
  1
  2
  3

堆排序思路

• 将一个无序序列构建成一个堆

• 将堆顶元素下沉到数组后面

• 将剩余的 n - 1 个元素重新调整成一个堆

• 继续将堆顶元素下沉

• 重复执行上诉操作，直到得到一个完整的有序序列为止

堆排序代码

import java.util.Arrays;

public class HeadSort {

    public static void main(String[] args) {
        int[] array = new int[]{3, 2, 5, 7, 4, 8, 15, 1};
        HeadSort.sort(array);
        System.out.println(Arrays.toString(array));
    }

    public static void sort(int[] arr) {
        // 1.构建大顶堆
        buildHead(arr);

        // 2.交换堆顶元素和末尾元素，并重新调整堆结构（不包含沉到后面的元素哦）
        for (int j = arr.length - 1; j > 0; j--) {
            swap(arr, 0, j);      // 将堆顶元素与末尾元素进行交换
            adjustHeap(arr, 0, j);   // 重新对堆进行调整
        }

    }

    // 构建堆（堆是在已有数组的基础上进行构建的）
    private static void buildHead(int[] arr){
        // 1.构建大顶堆，从最后一个非叶子结点开始
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            // 从最后一个非叶子结点自下而上，自左往右调整结构
            adjustHeap(arr, i, arr.length);
        }
    }


    // 调整堆结构
    public static void adjustHeap(int[] arr, int i, int len) {
        int left = 2 * i + 1;   // 左孩子的索引
        int right = 2 * i + 2;  // 右孩子的索引
        int maxIndex = i;  // 临时变量记录最大值的索引，初始时记录父节点的索引为最大值的索引

        if (left < len && arr[left] > arr[maxIndex]) {
            maxIndex = left;
        }

        if (right < len && arr[right] > arr[maxIndex]) {
            maxIndex = right;
        }

        if (maxIndex != i) {
        	// 若最大值在子孩子中，则交换它们的位置
            swap(arr, i, maxIndex);
            // 这一步为什么要递归调用，可能有初学者不太理解，我会解惑一栏中着重讲解
            adjustHeap(arr, maxIndex, len);
        }

    }


    // 交换元素
    public static void swap(int[] arr, int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

代码解惑

// 调整堆结构
public static void adjustHeap(int[] arr, int i, int len) {
    // 省略. . .
    
    if (maxIndex != i) {
    	// 若最大值在子孩子中，则交换它们的位置
        swap(arr, i, maxIndex);
        // 这一步为什么要递归调用，可能有初学者不太理解，我会解惑一栏中着重讲解
        adjustHeap(arr, maxIndex, len);
    }

}
1
2
3
4
5
6
7
8
9
10
11
12

对于上诉 if 语句中，为什么交换了孩子节点和父节点的位置后，要进行递归调用？这里的递归调用起到了什么作用？

具体可以看我的另一篇文章 自底向上的构建二叉堆，文中有关于这个问题得详细解析

算法分析

• 建堆的时间复杂度为$O(n)$，遍历交换栈顶元素和尾部元素得时间复杂度为$O(n)$，调整堆结构得时间复杂度为$O(logn)$，总体时间复杂度为$O(nlogn)$

• 堆排序属于就地排序，空间复杂度为$O(1)$

• 堆排序属于不稳定排序。因为在交换元素位置时，有可能会把后面的元素交换到前面去。

参考文献

https://www.cnblogs.com https://www.bilibili.com