C++堆排序的原理及实现

野性酷女 2022-11-15 11:17 143阅读 0赞

首先回顾下堆的数据结构的特点：

# 堆的描述 #

堆是一颗二叉树，这样的二叉树是局部有序的，任何节点与其兄弟节点之间都没有必然的顺序联系，但是**它与父子节点之间有大小顺序关系**，按照关系的不同，分为最大值堆和最小值堆：

*  最大值堆：子节点比父节点小的堆，根节点是树中最大的节点。
 *  最小值堆：子节点比父节点大的堆，根节点是树中最小的节点。

**堆是左平衡的树**，所以随着节点的增加，树会逐级从左至右增长。因此对于一个堆来说，一个比较好的表示左平衡二叉树的方式是：

将节点通过水平遍历的方式连续存储到一个数组中。假设有一个零索引数组，这表示数组中处于位置i处的节点，其父节点位于（i-1）/2处，计算时忽略小数部分。其左节点和右节点分别位于2i+1和2i+2处。这样的组织结构对于堆来说非常重要，因为通过它我们能够迅速定位堆的最后一个节点：**最后一个节点位于树中最深层的最右端**。

在数组中，父子节点下标的关系为：

>  *  root= (left-1)/2= (right-1)/2
>  *  left = 2\*root+1
>  *  right=2\*root+2

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1b2xhaWh1YTIwMTg_size_16_color_FFFFFF_t_70][]

比如值为19的节点的左右节点为9和18，它们在数组中的下标为2\*4+1=9,2\*4+2=10。

# 堆排序 #

堆排序是利用**堆**这种数据结构而设计的一种排序算法，堆排序是一种**选择排序，**它的最坏，最好，平均时间复杂度均为**O(nlogn)**，它也是**不稳定排序**。

在堆排序中，要排序的数据首先存储在一个堆中。从堆中一次取出一个节点，放置到有序数据集的尾部。当取出每个节点时，它的下一个节点就会浮现到堆的顶部。堆排序和快速排序有相同的时间复杂度，但在实际中，快速排序往往比堆排序复杂度略低，两者相差一个常量因子。

![25211cb42464e31d7da979c94e5979e8.png][]

排序完成后：变成一个最小值堆，此时，堆数组是升序排列的

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1b2xhaWh1YTIwMTg_size_16_color_FFFFFF_t_70 1][]

## 算法步骤 ##

具体的图解算法参考：[图解排序算法(三)之堆排序][Link 1]

**堆排序的基本思想是：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了**

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

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

堆排序的基本思路：

**a.将无需序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆;**

**　　b.将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端;**

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

#include <iostream>
    #include<vector>
    #include <algorithm>
    using namespace std;
    
    //在start 和end区间内，如果父节点小于子节点，就交换
    void max_heapify(int arr[], int start, int end)
    {
    	//建立父节点指标和子节点指标
    	int dad = start;
    	int son = dad * 2 + 1;//左子节点
    	while (son <= end)  //若子节点指标在范围内才做比较
    	{
    		if (son + 1 <= end && arr[son] < arr[son + 1]) //先比较两个子节点大小，选择最大的
    			son++;
    		if (arr[dad] > arr[son]) //如果父节点大于子节点代表调整完毕，直接跳出函数
    			return;
    		else  //否则交换父子内容再继续子节点和孙节点比较
    		{
    			swap(arr[dad], arr[son]);
    			dad = son;
    			son = dad * 2 + 1;
    		}
    	}
    }
    
    void heap_sort(int arr[], int len)
    {
    	//初始化，i从最后一个父节点开始调整
    	//堆数组的前一半为父节点，后一半为子节点
    	for (int i = len / 2 - 1; i >= 0; i--)
    		max_heapify(arr, i, len - 1);
    	//先将第一个元素和已经排好的元素前一位做交换，再从新调整(刚调整的元素之前的元素)，直到排序完毕
    	for (int i = len - 1; i > 0; i--)
    	{
    		swap(arr[0], arr[i]);
    		max_heapify(arr, 0, i - 1);
    	}
    }
    
    int main(void)
    {
    	int arr[] = { 3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6 };
    	int len = (int) sizeof(arr) / sizeof(*arr);
    	heap_sort(arr, len);
    	for (int i = 0; i < len; i++)
    		cout << arr[i] << ' ';
    	cout << endl;
    	return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1b2xhaWh1YTIwMTg_size_16_color_FFFFFF_t_70]: /images/20221022/26024366cbed473ca60c365d5ffdf84e.png
[25211cb42464e31d7da979c94e5979e8.png]: https://img-blog.csdnimg.cn/img_convert/25211cb42464e31d7da979c94e5979e8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1b2xhaWh1YTIwMTg_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20210331154228954.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1b2xhaWh1YTIwMTg=,size_16,color_FFFFFF,t_70
[Link 1]: https://www.cnblogs.com/chengxiao/p/6129630.html