堆排序

今天我们来学习最后一个排序算法——堆排序。

堆排序,顾名思义,其核心在于“堆”这一数据结构的巧妙运用。

如果你还没有看过我们上一篇所讲的 堆,强烈建议你先掌握这种数据结构,掌握之后你才能更好的理解堆排序的高效精妙之处。

堆排序思路

一种最直接的思路是将数组的所有元素加入到最大堆中,之后再不断的删除最大元素,来得到升序排列的数组。

但这种方法无异于是在做一次选择排序。

下面我们来介绍一种经典而又优雅的基于堆结构的排序算法。

堆排序主要分为两个阶段:最大堆的构造阶段和下沉排序阶段。

最大堆的构造阶段

在这个阶段,我们的目的是把原始的数组组织成一个堆结构。

具体是怎么做的?

首先我们要知道数组的每个位置都是子堆的一个根结点,如果某个结点的两个子结点都是堆了,那么在这个结点上进行 sink 操作就可以将以这个结点作为根结点的子堆变成一个堆。

所以我们可以从右往左,从下往上的对节点进行 sink 操作,而且只需要处理数组一半的节点(也就是从最后一个结点的父结点开始操作),因为节点数量为 1 的子堆不需要处理。

for (int i = (N - 1) / 2; i >= 0; i--) {
    sink(i, N, nums);
}

下沉排序阶段

类似于选择排序,从堆顶选择最大元素与堆的最后进行交换,同时减少堆的大小,然后对堆顶的元素进行 sink 操作,使堆有序。

while (N > 0) {
    swap(nums, 0, N);
    N--;
    sink(0, N, nums);
}

代码实现

public class Solution {

    public int[] sort (int[] nums) {
        int N = nums.length - 1;
        for (int i = (N - 1) / 2; i >= 0; i--) {
            sink(i, N, nums);
        }
        while (N > 0) {
            swap(nums, 0, N);
            N--;
            sink(0, N, nums);
        }
        return nums;
    }

    private void sink (int i, int N, int[] nums) {
        while (i * 2 <= N - 1) {
            int j = i * 2 + 1;
            j = j + 1 <= N && nums[j] < nums[j + 1] ? j + 1 : j;
            if (nums[i] > nums[j]) {
                break;
            }
            swap(nums, i, j);
            i = j;
        }
    }

    private void swap (int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

时间复杂度

堆排序的时间复杂度为 {O(NlogN)},其中 N 表示待排序元素的个数。

堆排序过程包括两个主要步骤:建堆阶段和下沉排序。

建堆阶段的时间复杂度为 {O(N)},主要涉及将一个无序序列构建成一个堆的过程。

下沉排序的时间复杂度为 {O(NlogN)},主要包括将堆顶元素与堆的最后一个元素交换并调整堆结构的过程。

总体来说,堆排序的时间复杂度为 {O(NlogN)},具有较高的效率。

空间复杂度

堆排序是一个原地排序算法,不需要额外的辅助空间,所有操作都在原数组上进行。

因此空间复杂度为 {O(1)}

稳定性

堆排序是一种不稳定的排序算法。

在堆排序中,通过不断交换堆顶元素与最后一个元素并调整堆结构,可能会改变相同元素之间的相对位置,导致排序后相同元素的顺序发生变化。

因此,堆排序不保证相同元素的稳定顺序,是一种不稳定的排序算法。

写在最后

总的来说,堆排序是一种原地、不稳定、时间复杂度为 {O(NlogN)} 的高效排序算法。

到这里我们就把所有的排序算法都学习完了,下篇文章将会带来所有排序算法的总结!

发表回复

后才能评论