手撕堆排序

2021年8月15日 150点热度 0人点赞 0条评论

题目描述

给你一个整数数组 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 <= nums.length <= 50000
  • -50000 <= nums[i] <= 50000

算法思路

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

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

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

首先是向下调整的过程:

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

需要注意一点,如果这个数组是从下标0开始,那么对于下标index的元素,它的两个子节点的下标就是2 * index + 12 * 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/

参考代码

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))$​

agedcat_xuanzai

这个人很懒,什么都没留下

文章评论