当前位置:   article > 正文

数据结构与算法之堆排序_数据结构堆排序

数据结构堆排序

堆排序概述

堆排序(Heap Sort)是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,每个结点的值都大于或等于其左右孩子结点的值,称为大顶堆;或者每个结点的值都小于或等于其左右孩子结点的值,称为小顶堆。如下图:

在这里插入图片描述同时,我们对堆中的结点按层进行编号,将这种逻辑结构映射到数组中就是下面这个样子
在这里插入图片描述该数组从逻辑上讲就是一个堆结构,我们用简单的公式来描述一下堆的定义就是:

  • 大顶堆:arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]

  • 小顶堆:arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]

步骤一 构造初始堆。将给定无序序列构造成一个大顶堆(一般升序采用大顶堆,降序采用小顶堆)

1)假设给定无序序列结构如下
在这里插入图片描述
2)此时我们从最后一个非叶子结点开始(叶结点自然不用调整,第一个非叶子结点 arr.length/2-1=5/2-1=1,也就是下面的6结点),从左至右,从下至上进行调整
在这里插入图片描述
3)找到第二个非叶节点4,由于[4,9,8]中9元素最大,4和9交换
在这里插入图片描述4)这时,交换导致了子根[4,5,6]结构混乱,继续调整,[4,5,6]中6最大,交换4和6。
在这里插入图片描述此时,我们就将一个无需序列构造成了一个大顶堆

步骤二 将堆顶元素与末尾元素进行交换,使末尾元素最大。然后继续调整堆,再将堆顶元素与末尾元素交换,得到第二大元素。如此反复进行交换、重建、交换

1)将堆顶元素9和末尾元素4进行交换,9就不用继续排序了
在这里插入图片描述
2)重新调整结构,使其继续构建大顶堆(9除外)
在这里插入图片描述
3)再将堆顶元素8与末尾元素5进行交换,得到第二大元素8.
在这里插入图片描述
步骤三 后续过程,继续进行调整,交换,如此反复进行,最终使得整个序列有序
在这里插入图片描述

排序思路

  • 将无需序列构建成一个堆,根据升序降序需求选择大顶堆或小顶堆;

  • 将堆顶元素与末尾元素交换,将最大元素"沉"到数组末端;

  • 重新调整结构,使其满足堆定义,然后继续交换堆顶元素与当前末尾元素,反复执行调整+交换步骤,直到整个序列有序

动图展示

在这里插入图片描述

代码实现

import java.util.Arrays;

public class HeapSort {
    public static void main(String[] args) {
        int[] arr = {4, 6, 8, 5, 9};
        heapSort(arr);
//        [4, 6, 8, 5, 9]
//        [4, 9, 8, 5, 6]
//        [4, 9, 8, 5, 6]
//        [9, 6, 8, 5, 4]
//        [9, 6, 8, 5, 4]
//        [9, 6, 8, 5, 4]
//        [8, 6, 4, 5, 9]
//        [8, 6, 4, 5, 9]
//        [6, 5, 4, 8, 9]
//        [6, 5, 4, 8, 9]
//        [5, 4, 6, 8, 9]
//        [5, 4, 6, 8, 9]
//        [4, 5, 6, 8, 9]
    }

    //堆排序
    public static void heapSort(int[] arr) {
        //开始位置是最后一个非叶子节点(最后一个节点的父节点)
        int start = (arr.length - 1) / 2;
        //循环调整为大顶堆
        for (int i = start; i >= 0; i--) {
            maxHeap(arr, arr.length, i);
        }
        //先把数组中第0个和堆中最后一个交换位置
        for (int i = arr.length - 1; i > 0; i--) {
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            //再把前面的处理为大顶堆
            maxHeap(arr, i, 0);
        }
    }

    //数组转大顶堆,size:调整多少(从最后一个向前减),index:调整哪一个(最后一个非叶子节点)
    public static void maxHeap(int[] arr, int size, int index) {
        //左子节点
        int leftNode = 2 * index + 1;
        //右子节点
        int rightNode = 2 * index + 2;
        //先设当前为最大节点
        int max = index;
        //和两个子节点分别对比,找出最大的节点
        if (leftNode < size && arr[leftNode] > arr[max]) {
            max = leftNode;
        }
        if (rightNode < size && arr[rightNode] > arr[max]) {
            max = rightNode;
        }

        //交换位置
        if (max != index) {
            int temp = arr[index];
            arr[index] = arr[max];
            arr[max] = temp;
            //交换位置后,可能会破坏之前排好的堆,所以之间排好的堆需要重新调整
            maxHeap(arr, size, max);
        }
        //打印每次排序后的结果
        System.out.println(Arrays.toString(arr));
    }
}
  • 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

时间复杂度

  • 最优时间复杂度:o(nlogn)
  • 最坏时间复杂度:o(nlogn)
  • 稳定性:不稳定

它的运行时间主要是消耗在初始构建堆和在重建堆时的反复筛选上。

在构建堆的过程中,因为我们是完全二叉树从最下层最右边的非终端结点开始构建,将它与其孩子进行比较和若有必要的互换,对于每个非终端结点来说,其实最多进行两次比较和互换操作,因此整个构建堆的时间复杂度为O(n)。

在正式排序时,第i次取堆顶记录重建堆需要用O(logi)的时间(完全二叉树的某个结点到根结点的距离为log2i+1),并且需要取n-1次堆顶记录,因此,重建堆的时间复杂度为O(nlogn)

所以总体来说,堆排序的时间复杂度为O(nlogn)。由于堆排序对原始记录的排序状态并不敏感,因此它无论是最好、最坏和平均时间复杂度均为O(nlogn)。这在性能上显然要远远好过于冒泡、简单选择、直接插入的O(n2)的时间复杂度了。

空间复杂度上,它只有一个用来交换的暂存单元,也非常的不错。不过由于记录的比较与交换是跳跃式进行,因此堆排序是一种不稳定的排序方法。

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/Cpp五条/article/detail/681460
推荐阅读
相关标签
  

闽ICP备14008679号