数据结构与算法系列之一:八大排序之堆排序


[toc]


堆排序

前言

  建议先看排序综述,传送门:数据结构与算法系列之一:八大排序综述

简介

  堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。

  通常堆是通过一维数组来实现的。在数组起始位置为0的情形中:

  • 父节点i的左子节点在位置 ${\displaystyle (2i+1)}$。
  • 父节点i的右子节点在位置 ${\displaystyle (2i+2)}$。
  • 子节点i的父节点在位置 ${\displaystyle floor((i-1)/2)}$。

  在堆的数据结构中,堆中的最大值总是位于根节点(在优先队列中使用堆的话堆中的最小值位于根节点)。堆中定义以下几种操作:

  • 最大堆调整(Max_Heapify):将堆的末端子节点作调整,使得子节点永远小于父节点。
  • 创建最大堆(Build_Max_Heap):将堆所有数据重新排序。
  • 堆排序(HeapSort):移除位在第一个数据的根节点,并做最大堆调整的递归运算。

步骤

  基于以上堆相关的操作,我们可以很容易的定义堆排序。例如,假设我们已经读入一系列数据并创建了一个堆,一个最直观的算法就是反复的调用del_max()函数,因为该函数总是能够返回堆中最大的值,然后把它从堆中删除,从而对这一系列返回值的输出就得到了该序列的降序排列。真正的原地堆排序使用了另外一个小技巧。堆排序的过程是:

  • 创建一个堆 ${\displaystyle H[0..n-1]}$。
  • 把堆首(最大值)和堆尾互换。
  • 把堆的尺寸缩小1,并调用shift_down(0),目的是把新的数组顶端数据调整到相应位置。
  • 重复步骤2,直到堆的尺寸为1。

演示

  wikipedia的大数据规模演示:


heapsort from wikipedia

代码

递归版

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
/*
* 堆排序递归版
*/

template <typename T>
void MaxHeapifyRecursive(T *array, int i, int heapSize) {
int sonl = 2 * i + 1;
int sonr = 2 * i + 2;
int dad = i;
if (sonl <= heapSize && array[sonl]>array[i]){ //如果左子结点大于父结点,则父结点指向子结点
dad = sonl;
}
if (sonr <= heapSize && array[sonr]>array[dad]){ //如果右子结点大于父结点,则父结点指向子结点
dad = sonr;
}
if (dad != i){ //如果dad != i则说明父结点不是最大值,交换后递归执行MaxHeapifyRecursive
swap(array[i], array[dad]);
MaxHeapifyRecursive(array, dad, heapSize);
}
}

template <typename T>
void HeapSort(T *array, const int length) {
if (array == NULL)
throw invalid_argument("Array must not be empty");
if (length <= 0)
return;

//初始化,i从最后一个父结点开始调整
for (int i = length / 2 - 1; i >= 0; --i){
//构建最大堆
MaxHeapifyRecursive(array, i, length - 1);
// MaxHeapifyIteration(array, i, length - 1);
}
//先将第一个元素和已经排好的元素前一位做交换,再从新调整(刚调整的元素之前的元素),直到排序完毕
for (int i = length - 1; i >= 0; --i){
swap(array[0], array[i]);
MaxHeapifyRecursive(array, 0, i - 1);
// MaxHeapifyIteration(array, 0, i - 1);
}
}

迭代版

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
/*
* 堆排序迭代版
*/

template <typename T>
void MaxHeapifyIteration(T *array, int left, int right) {
//建立父结点指针和子结点指针
int dad = left;
int son = dad * 2 + 1;
while (son <= right) { //若子结点指针在范围内才做比较
if (son + 1 <= right && array[son] < array[son + 1]) //先比较两个子结点的大小,选择最大的
son++;
if (array[dad] > array[son]) //如果父结点大于子结点代表调整完毕,直接跳出循环
return;
else { //否则交换父子内容在继续子结点和孙结点的比较
swap(array[dad], array[son]);
dad = son;
son = dad * 2 + 1;
}
}
}

template <typename T>
void HeapSort(T *array, const int length) {
if (array == NULL)
throw invalid_argument("Array must not be empty");
if (length <= 0)
return;

//初始化,i从最后一个父结点开始调整
for (int i = length / 2 - 1; i >= 0; --i){
//构建最大堆
// MaxHeapifyRecursive(array, i, length - 1);
MaxHeapifyIteration(array, i, length - 1);
}
//先将第一个元素和已经排好的元素前一位做交换,再从新调整(刚调整的元素之前的元素),直到排序完毕
for (int i = length - 1; i >= 0; --i){
swap(array[0], array[i]);
// MaxHeapifyRecursive(array, 0, i - 1);
MaxHeapifyIteration(array, 0, i - 1);
}
}

算法复杂度

  • 数据结构 数组
  • 最坏时间复杂度 ${\displaystyle O(n\log n)}$
  • 最优时间复杂度 ${\displaystyle O(n\log n)}$
  • 平均时间复杂度 ${\displaystyle O(n\log n)}$
  • 空间复杂度 ${\displaystyle O(n)}$ total, ${\displaystyle O(1)}$ auxiliary

分析

  原地堆排序已经是空间优化版本了,因为它不再需要申请额外的空间。

  整个算法的过程分为建堆和排序两个过程,首先对现有数组建立最大堆,然后一边提取堆顶的最大值,一边减小堆的尺寸,最后堆尺寸为1时,排序也就完成了。如果大家对整个算法的执行过程不太了解,可以看一下下面这两张图,第一张是建堆的过程示意图,第二张是排序的过程示意图。图片来自:http://bubkoo.com/2014/01/14/sort-algorithm/heap-sort/


bubblesort from wordzzzz


bubblesort from wordzzzz

系列教程持续发布中,欢迎订阅、关注、收藏、评论、点赞哦~~( ̄▽ ̄~)~

完的汪(∪。∪)。。。zzz

转自https://blog.csdn.net/u011475210

谢谢你请我吃糖,Mua
0%