当前课程知识点：数据结构（Data Structures） > 7. Sorting > 7.7 Heap Sort > Video
返回《数据结构（Data Structures）》慕课在线视频课程列表
返回《数据结构（Data Structures）》慕课在线视频列表
各位同学大家好
接下来我们将学习到一种时间复杂度
同样也是⊙（nlogn）排序算法
堆排序 Heap Sort
我们前面已经学习过
关于堆的概念以及性质
我们知道在大顶堆中
最大的元素
始终是记录在树根的位置的
所以我们可以很高效地
获得堆中的最大的元素
当我们把最大的元素
从堆里面取出来之后
我们又可以通过堆调整算法
重新把剩下的元素
再次调整成为堆
因此我们可以继续很高效地拿到
剩下元素的最大值
通过这种方式
我们依次可以获得最大元素
第二大的元素
第三大的元素等等
这样我们就得到了一个
有序的序列
所以我们说堆
是可以用来帮助我们
去实现排序的
下面我们来看一看
具体应该怎么去做
我们首先要把所有的数据
都加入到堆中去
这可以堆的构建过程来实现
在这里我们采用的是大鼎堆
树根是堆中最大的元素
当我们对这个大鼎堆
调用removemax操作的时候
将会从堆中取出堆顶的元素
这个函数的具体操作是
将堆顶的元素
交换到最后的位置上面去
同时让剩下的元素调整成为堆
然后我们可以继续地
将它调用removemax操作
这个时候又会把第二大元素
交换到堆的末尾
也就是倒数第二的位置上面去
所以接下来要做的事情
同学们一定可以猜到了
我们只需要对这个堆
不断的去调用removemax参数
之后我们会得到一个元素
由小到大排列的一个数组
在明白了堆排序的原理之后
实现堆排序的过程
其实非常简单
我们首先要在数组A的基础上
构建一个大顶堆H
然后我们对这个大顶堆
去调用N次removemax操作
我们就可以把这个数组A
调整成一个有序的数组
我们前面学习过
构建堆的过程
它的时间复杂度
是⊙（n)
而removemax它的操作
时间复杂度是⊙(log n）
所以我们要执行n次removemax的操作
所需要的时间
就是⊙(nlog n）
因此整个Heap Sort函数
它的时间复杂度
也就是⊙(nlog n）
好的
这节课我们就讲到这里
下节课我们再见
-1. Introduction--1.1 Introduction of Data
-1.1 Introduction of Data Structure
--Introduction of Data Structure
-1.2 Data Structure and A
-1.2 Data Structure and Algorithm
--Video
-1.3 Asymptotic Analysis
-1.3 Asymptotic Analysis
--Video
-1.4 Simplifying Rules of
-1.4 Simplifying Rules of Asymptotic Analysis
--Video
-2.1 Introduction of List
-2.1 Introduction of List
--Video
-2.2 Array based List
-2.2 Array based List
--Video
-2.3 Insertion Operation on Array
-2.3 Insertion Operation on Array based List
--Video
-2.4 Remove Operation on Array based List
-2.4 Remove Operation on Array based List
--Video
-2.5 Linked list
-2.5 Linked list
--Video
-2.6 Insertion Operation on Linked list
-2.6 Insertion Operation on Linked list
--Video
-2.7 Remove Operation on Linked list
-2.7 Remove Operation on Linked list
--Video
-2.8 SetPos Operation on Linked list
-2.8 SetPos Operation on Linked list
--Video
-2.9 Stack
-2.9 Stack
--Video
-2.10 Application of Stack
--Video
-2.11 Queue
-2.11 Queue
--Video
-3.1 Definition of Binary Tree
-3.1 Definition of Binary Tree
--Video
-3.2 Implementation of Binary Tree
-3.2 Implementation of Binary Tree
--Video
-3.3Traversal
-3.3 Traversal
--Video
-3.4 Binary Search Tree
-3.4 Binary Search Tree
--Video
-3.5 Search on BST
-3.5 Search on BST
--Video
-3.6 Insertion on BST
-3.6 Insertion on BST
--Video
-3.7 Introduction of Heap
-3.7 Introduction of Heap
--Video
-3.8 Construction of Heap
-3.8 Construction of Heap
--Video
-3.9 Operations on Heap
--Video
-3.10 General Tree
--Video
-4.1 Definition of Searching
--Video
-4.2 Searching of Sorted Array
-4.2 Searching of Sorted Array
--Video
-4.3 Definition of Hash Table
--Video
-4.4 Collision in Hash Table
-4.4 Collision in Hash Table
--Video
-4.5 Extension of Linear Probing
--Video
-4.6 Insertion Operation of Hash Table
--Video
-4.7 Search Operation of Hash Table
-4.7 Search Operation of Hash Table
--Video
-5.1 Introduction of Index
--Video
-5.2 Linear Index
-5.2 Linear Index
--Video
-5.3 2-3 tree index
-5.3 2-3 tree index
--Video
-5.4 Implementation of 2-3 tree
-5.4 Implementation of 2-3 tree
--Video
-5.5 B-Tree
-5.5 B-Tree
--Video
-5.6 Insertion Operation on B+ Tree
--Video
-5.7 Deletion Operation on B+ Tree
--Video
-6.1 Definition of Graph
--Video
-6.2 Implementation of Graph
--Video
-6.3 Adjacency Matrix
--Video
-6.4 Adjacency List
--Video
-6.5 Graph Traversal - DFS
--Video
-6.6 Graph Traversal - BFS
--Video
-6.7 Topological Sort
--Video
-6.8 Shortest Path Problem
--Video
-6.9 Single Source Shortest Path
--Video
-6.10 Dijkstra Algorithm
--Video
-7.1 Sorting Problem
--Video
-7.2 Insertion Sort
--Video
-7.3 Selection Sort
--Video
-7.4 Bubble Sort
--Video
-7.5 Shell Sort
--Video
-7.6 Quick Sort
--Video
-7.7 Heap Sort
--Video
-7.8 Comparison
--Video
