题目描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
给你一个整数数组 nums，请你将该数组升序排列。 

示例 1：

输入：nums = [5,2,3,1]

输出：[1,2,3,5]



示例 2：

输入：nums = [5,1,1,2,0,0]

输出：[0,0,1,1,2,5]

堆排序的性质

  1. 堆是一颗满二叉树
  2. 子节点和父节点下标关系：leftChild = parent * 2 + 1
  3. 构建大顶堆是上浮操作，上浮操作是选择子节点中较大的节点，并和parent节点比较，子节点较大则交换子节点和parent节点
  4. 不稳定排序，时间复杂度O(nlogn)

如何实现

使用堆排序进行排序操作，堆排序可以分成两个步骤

  1. 构建大顶堆，应该是从第向上执行遍历（上浮），所以循环从数组末尾向前循环
  2. 打印或者保存第一个节点
  3. 交换第一个和最后一个节点，缩小数组范围并继续执行第一步

代码如下

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
65
66
67
68
69
70
71
72
73
package com.code.note.test;

import com.code.note.tree.UnOrderBTree;

import java.util.Arrays;

public class Solution {

    /**
     * 构建大顶堆
     * <p>
     * child = parent * 2 + 1;
     */
    public void buildBigHeap(Integer[] nums, int parent, int len) {
        int child = parent * 2 + 1;
        while (child < len) {
            if (child + 1 < len && nums[child] < nums[child + 1]) {
                child++;
            }

            if (nums[child] < nums[parent]) {
                break;
            }

            swap(nums, child, parent);

            parent = child;
            child = child * 2 + 1;
        }
    }

    public void heapSort(Integer[] nums) {
        for (int i = nums.length / 2; i >= 0; i--) {
            buildBigHeap(nums, i, nums.length);
        }

        print(nums);

        for (int i = nums.length - 1; i > 0; i--) {
            int t = nums[0];
            nums[0] = nums[i];
            nums[i] = t;

            buildBigHeap(nums, 0, i);
        }
    }


    public void swap(Integer[] nums, int i, int j) {
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }
  
    private void print(Integer[] arr1) {
        UnOrderBTree unOrderBTree2 = new UnOrderBTree();
        unOrderBTree2.insertLevelOrder(arr1);
        unOrderBTree2.print();
    }

    public static void main(String[] args) {

        Solution s = new Solution();
        Integer[] arr1 = {3, 2, 1, 6, 0, 5};

        s.print(arr1);
        s.heapSort(arr1);

        System.out.println(Arrays.toString(arr1));

    }
}