586-堆排序算法的思想和性能分析

╰+哭是因爲堅強的太久メ 2022-09-12 02:48 170阅读 0赞

## 堆排序算法的思想 ##

**如果我们要从小到大排序，实现的就是大根堆  
如果我们要从大到小排序，实现的就是小根堆**

**我们实现的是从小到大排序：**  
首先，题目给我们的是一组原始的未排序的序列  
我们把存在数组中的元素，在逻辑上看成1个二叉堆

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16]  
**我们要做的第一件事是：**  
![在这里插入图片描述][8fb75195f3ea4111a15d3e80749a0b09.png]  
**第1个非叶子节点的下标：(最后一个节点的下标-1)/2**  
就是图中的值为8的节点  
然后进行一个大根堆的调整  
**和它的孩子进行比较进行判断，看看要不要下沉调整**  
大根堆：当前节点的值要大于它的两个孩子  
如果孩子的值大于当前节点，要和当前节点进行交换。  
![在这里插入图片描述][f11dcb423b4b4ca5ad68af0c6cab3b50.png]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_19_color_FFFFFF_t_70_g_se_x_16]  
**然后到值为2的元素，进行判断，看看要不要下沉调整**

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_18_color_FFFFFF_t_70_g_se_x_16]  
**然后到值为5的元素的节点，进行判断，看看要不要下沉调整**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 1]  
**调整完之后，只是个大根堆，只是把值最大的元素调整到堆顶而已，所以还不是有序的**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 2]  
**现在我们要做的事情是**：循环操作  
**把最大值和末尾的节点交换**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 3]  
**现在最大的元素12是在末尾节点，即在数组的末尾位置。**  
然后现在打破了大根堆的性质了，从0号位置开始继续进行堆的下沉调整，但是我们在调整的时候，就不要再考虑这个值为12的末尾节点了，我们相当于是每次靠这个大根堆，把当前序列中的最大值找出来，调整到堆顶，形成大根堆，然后把这个最大值和当前序列的末尾位置的元素交换。以此类推，就可以排序了。（每一趟少处理1个元素，即少处理当前序列的末尾那个元素）  
**所以，我们第二趟开始，从0号位置开始下沉调整的时候，就不要考虑12这个节点了，**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 4]  
然后把当前的堆顶元素11和当前处理的序列的末尾位置元素交换  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 5]

**然后开始第三趟下沉调整，从0号位置开始下沉调整，不考虑11和12了**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_19_color_FFFFFF_t_70_g_se_x_16 1]  
然后把堆顶元素9和当前序列的末尾位置元素2交换  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_18_color_FFFFFF_t_70_g_se_x_16 1]  
**然后开始第四趟下沉调整，从0号位置开始下沉调整，不考虑11和12和9了**  
**就是这样，以此类推下去，最后得到的就是一个有序的序列了**

## 堆排序算法的代码实现 ##

#include <iostream>
    using namespace std;
    
    //堆的下沉调整
    void siftDown(int arr[], int i, int size)
    {
        
    	int val = arr[i];
    	while (i < size / 2)
    	{
        
    		int child = 2 * i + 1;
    		if (child + 1 < size && arr[child + 1] > arr[child])
    		{
        
    			child = child + 1;
    		}
    
    		if (arr[child] > val)
    		{
        
    			arr[i] = arr[child];
    			i = child;//i继续指向它的孩子，继续调整
    		}
    		else
    		{
        
    			break;
    		}
    	}
    	arr[i] = val;
    }
    
    //堆排序
    void HeapSort(int arr[], int size)
    {
        
    	int n = size - 1;
    	//从第一个非叶子节点
    	for (int i = (n - 1) / 2; i >= 0; i--)//一直向上调整到0号位置-根，整个树就是大根堆 
    	{
        
    		siftDown(arr, i, size);//下沉调整 
    	}
    
    	//把堆顶元素和末尾元素进行交换，从堆顶开始进行下沉操作 
    	for (int i = n; i > 0; i--)
    	{
        
    		int tmp = arr[0];
    		arr[0] = arr[i];
    		arr[i] = tmp;
    
    		siftDown(arr, 0, i);//第三个参数，参与调整的元素的个数，每一趟少处理1个元素 
    	}
    }
    
    int main()
    {
        
    	int arr[10];
    	srand(time(NULL));
    
    	for (int i = 0; i < 10; i++)
    	{
        
    		arr[i] = rand() % 100 + 1;
    	}
    
    	for (int v : arr)
    	{
        
    		cout << v << " ";
    	}
    	cout << endl;
    
    	HeapSort(arr, 10);
    
    	for (int v : arr)
    	{
        
    		cout << v << " ";
    	}
    	cout << endl;
    }

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 6]

## 堆排序算法的性能分析 ##

1、每一趟下沉调整，都是树的高度，是logn  
2、每一趟结束，都是要把堆顶元素和当前序列的末尾位置元素交换。  
所以就是把n个元素放到堆顶。  
**所以时间复杂度是O(nlogn)**  
**堆的好处是**：不管元素是有序的，还是乱序的，**最好，最差，平均的时间复杂度都是O(nlogn)**，而且**空间复杂度是O(1)**

**归并排序的最好，最差，平均的时间复杂度都是O(nlogn)，但是空间复杂度是O(logn)**

**对于快速排序算法来说，排的速度很快，但是快排有最差的情况：数据已经有序（正序或者逆序），此时的时间复杂度是O(n^2)了，而且快排有空间复杂度：O(logn)，递归的时候函数的栈占用的空间**

**堆排序是不稳定的：**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_17_color_FFFFFF_t_70_g_se_x_16]  
8的兄弟节点9肯定是在前面存储的，另一个9是在后面存储的  
但是在进行大根堆的调整的时候，由于8和9的父节点11小，所以这个8和9就不会向上调整了。  
但是7这个节点，为父节点，值是小于它的右孩子9的，进行下沉调整，9调整上来了，  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_18_color_FFFFFF_t_70_g_se_x_16 2]  
**现在这个9变到了前面了，两个相同值的元素的相对位置发生了变化，所以是不稳定的。**

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/00940b420c494ae28e90ead581f5e01e.png
[8fb75195f3ea4111a15d3e80749a0b09.png]: /images/20220828/49323deb1af04a1e979aa221d42fe793.png
[f11dcb423b4b4ca5ad68af0c6cab3b50.png]: /images/20220828/b516f6f11fe644878496df6f67afcdfa.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_19_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/eededb23243a4672adbc20aa6dbc2cc1.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_18_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/6e7f8e14890545be9246b12be9951e19.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/4e2a5a5571b64221acb950073a71e093.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220828/6937120c1fc14329b97cc8ac45ce62e5.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 3]: /images/20220828/555651fc048d4d69a615f7bcbcb5a4d4.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 4]: /images/20220828/a72e451ca3c44de8976286a38e8c742d.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 5]: /images/20220828/258971b413f04184b802d73a7dc9f528.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_19_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/e52b6c9698714850b3aa39ae060f47f7.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_18_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/b96af6a41d694d44b4f1e8f3cc964c0b.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 6]: /images/20220828/7ebf85f6682c46ddbe20ef66b4e2cf00.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_17_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/24b20d6bf8164a569872aa3f44f487ee.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_18_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220828/0ffc9d8853374eb398dca9666d5ee21c.png