HeapSort
在计算机科学中,堆排序(Heapsort)是一种基于比较的排序算法。Heapsort 可以被认为是一种改进的选择排序:像该算法一样,它将输入分为排序区域和未排序区域,并通过提取最大元素并将其移动到排序区域来迭代缩小未排序区域。改进包括使用堆数据结构而不是线性时间搜索来找到最大值。
堆排序(Heapsort)
基本原理
传送门 堆、堆排序、优先队列
算法步骤
- 由输入的无序数组构造一个最大堆,作为初始的无序区
- 把堆顶元素(最大值)和堆尾元素互换
- 把堆(无序区)的尺寸缩小 1 ,并调用 sinking 函数,目的是把新的数组顶端数据调整到相应位置
- 重复步骤 2 ,直到堆的尺寸为 1
算法图解
构建二叉堆
构建二叉堆,也就是把一个无序的完全二叉树调整为二叉堆,本质上就是让 所有非叶子节点依次下沉。
我们举一个无序完全二叉树的例子:
首先,我们从最后一个 非叶子 节点开始,也就是从节点 10 开始。如果节点 10 大于它左右孩子中最小的一个,则节点 10 下沉。
接下来轮到节点 3 ,如果节点 3 大于它左右孩子中最小的一个,则节点 3 下沉。
接下来轮到节点 1 ,如果节点 1 大于它左右孩子中最小的一个,则节点 1 下沉。事实上节点 1 小于它的左右孩子,所以不用改变。
接下来轮到节点 7 ,如果节点 7 大于它左右孩子中最小的一个,则节点 7 下沉。
节点 7 继续比较,继续下沉。
至此,一颗无序的完全二叉树就构建成了一个最小堆。
堆排序过程
堆排序是利用堆的自我调整实现的。
例如给定一个数组,对数组进行排序,使数组元素从小到大排列。
首先,我们要根据给定的数组构建一个最大堆。当我们删除一个最大堆的堆顶(并不是完全删除,而是替换到最后面),经过自我调节,第二大的元素就会被交换上来,成为最大堆的新堆顶。
如上图所示,当删除值为 10 的堆顶节点,经过调节,值为 9 的新节点就会顶替上来;当删除值为 9 的堆顶节点,经过调节,值为 8 的新节点就会顶替上来.......
由于二叉堆的这个特性,我们每一次删除旧堆顶,调整后的新堆顶都是大小仅次于旧堆顶的节点。那么我们只要反复删除堆顶,反复调节二叉堆,所得到的集合就成为了一个有序集合,过程如下:
删除节点 9 ,节点 8 成为新堆顶:
删除节点 8 ,节点 7 成为新堆顶:
删除节点 7 ,节点 6 成为新堆顶:
删除节点 6 ,节点 5 成为新堆顶:
删除节点 5 ,节点 4 成为新堆顶:
删除节点 4 ,节点 3 成为新堆顶:
删除节点 3 ,节点 2 成为新堆顶:
至此,原本的最大堆已经变成了一个从小到大的有序集合。之前说过二叉堆实际存储在数组当中,数组中的元素排列如下:
动画演示
参考实现
1 | import java.util.Arrays; |
复杂度分析
排序算法 | 平均时间复杂度 | 最好情况 | 最坏情况 | 空间复杂度 | 排序方式 | 稳定性 |
---|---|---|---|---|---|---|
堆排序 | \(O(nlogn)\) | \(O(nlogn)\) | \(O(nlogn)\) | \(O(1)\) | In-place | 不稳定 |
References
https://en.wikipedia.org/wiki/Heapsort
-
2019-05-24
堆(Heap)是计算机科学中的一种特别的树状数据结构。若是满足以下特性,即可称为堆:“给定堆中任意节点 P 和 C,若 P 是 C 的母节点,那么 P 的值会小于等于(或大于等于) C 的值”。
堆始于
J._W._J._Williams
在 1964 年发表的堆排序(heap sort),当时他提出了二叉堆树作为此算法的数据结构。堆在 Dijkstra 等几种有效的图形算法中也非常重要。堆是一种称为优先级队列的抽象数据类型的最有效实现,实际上优先级队列通常被称为“堆”,而不管它们如何实现。
-
2019-05-24
归并排序(Merge sort),是创建在归并操作上的一种基于比较的排序算法。1945 年由约翰·冯·诺伊曼首次提出。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用,且各层分治递归可以同时进行。
-
2019-05-24
快速排序(Quicksort),又称分区交换排序(partition-exchange sort),简称快排,是一种高效的排序算法。由英国计算机科学家 Tony Hoare 于 1959 年开发并于 1961 年发表,至今它仍然是一种常用的排序算法。事实上,如果实施得当,它可以比归并排序、堆排序快两到三倍。
-
2019-05-24
在计算机科学中,选择排序(Selection sort)是一种排序算法,切确的说是就地比较排序。它具有 \(O(n^2)\) 时间复杂度,使其在大型列表上效率低下,并且通常比类似的插入排序更差。选择排序因其简单性而着称,并且在某些情况下具有优于更复杂算法的性能优势,特别是在辅助存储器有限的情况下。
-
2019-05-24
插入排序(Insertion Sort)是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。