手撕堆排序

题目描述

给你一个整数数组 nums，请你运用堆排序将该数组升序排列。

示例 1：

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

示例 2：

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

提示：

  • 1 <= nums.length <= 50000
  • -50000 <= nums[i] <= 50000

算法思路

运用堆排序在原数组的基础上完成排序的思路主要分为两步：

  1. 建立大根堆；
  2. 然后将大根堆最大的元素，也就是第一个元素，与大根堆中最后一个元素进行调换，然后将剩下的len - 1个数重新调整为大根堆。重复这个过程，最后会得到一个有序的序列。

然后主要的过程分为两个，一个是建立大根堆的过程，一个是调整大根堆的过程。

首先是向下调整的过程：

对于下标为index的元素，如果要将这个元素以下的元素重新调整为大根堆，那么就需要将index的元素与它的两个子节点中较大元素进行比较。如果num[index] < num[maxChild]，那么就需要调换元素。然后通过这个方法，将这个元素以下的所有元素都检查一遍。

需要注意一点，如果这个数组是从下标0开始，那么对于下标index的元素，它的两个子节点的下标就是2 * index + 1和2 * index + 2。

如果这个数组是从下标1开始，那么对于下标index的元素，它的两个子节点的下标就是2 * index 和2 * index + 1。

如果理解了向下调整的过程，那么就很容易理解建堆的过程：

将这个数组中前一半的元素进行向下调整的过程就可以得到大根堆。

然后就可以得出参考代码。

如果想通过图像或者动画加深了解，可以浏览下述链接：

https://leetcode-cn.com/problems/sort-an-array/solution/dong-hua-mo-ni-yi-ge-po-dui-pai-wo-gao-l-i6mt/

参考代码

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
void adjustHeap(vector<int>& num, int len, int index){
    if(index > len) return;

    int left = index * 2 + 1;
    int right = index * 2 + 2;
    int maxChild = index;

    if(left > len) return;
    else if(left <= len && right <= len){
        maxChild = num[left] > num[right] ? left : right;
    }
    else if(left <= right){
        maxChild = left;
    }

    if(num[index] < num[maxChild]){
        swap(num[index], num[maxChild]);
        adjustHeap(num, len, maxChild);
    }
}

void initHeap(vector<int>& num, int len){
    for(int i = num.size() / 2; i >= 0; --i){
        adjustHeap(num, len, i);
    }
}

void heapSort(vector<int>& num, int len){
    if(len < 1) return;
    initHeap(num, len);
    for(int i = len; i >= 1; --i){
        swap(num[0], num[i]);
        adjustHeap(num, i - 1, 0);
    }
}

复杂度分析

时间复杂度：O(nlog(n))O(nlog(n))​​

空间复杂度：O(nlog(n))O(nlog(n))​