首页 > 其他分享 >详解堆排序(内附代码实现)

详解堆排序(内附代码实现)

时间:2024-08-16 17:54:34浏览次数:17  
标签:大顶 arr 下标 int 内附 堆排序 详解 节点

堆排序有两个过程

下标为i的节点的父节点下标: (i-1)/2 整除

下标为i的节点的左孩子下标:i*2+1

下标为i的节点的右孩子下标:i*2+2

待排序序列为:

​ 2 3 8 1 4 9 10 7 16 14

1.建大顶堆

​ 首先建立无序堆

image-20240816173027907 然后建立大顶堆:从右往左,从下往上,递归的选择子节点最大的往上浮

首先14大于4,所以上浮

image-20240816173329115

​ 其次是16,上浮

image-20240816173415365

依次上浮,完毕后如图

image-20240816173816424

2.堆排序

​ 建立大顶堆后进行堆排序,我们将首尾的节点互换,拿到最大值

image-20240816174142799

然后对新的堆进行维护,维护的方式与建立大顶堆的方式一样,维护一次后如图

image-20240816174341753

依次交换堆顶和末尾元素,然后维护大顶堆

image-20240816174815909

image-20240816174851506

image-20240816174920506

.......往下递归即可,最后得到有序序列,至此完成堆排序。

代码如下:

#include<iostream>
using namespace std;
void print_arr(int arr【】, int n) {
    for (int i = 0; i < n; i++) {
        cout<< " " << arr【i】;
    }
    putchar('\n');
}
void swap(int *a,int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;

}

/*
arr 存贮数组
n 数组长度
i 代维护节点下标
*/
void heapify(int arr【】, int n, int i) {
    int largest = i;
    int lson = i * 2 + 1;
    int rson = i * 2 + 2;
    if (lson < n && arr【largest】 < arr【lson】)
    	largest = lson;
    if (rson < n && arr【largest】 < arr【rson】)
    	largest = rson;
    if (largest != i) {
   		swap(&arr【largest】, &arr【i】);
    	heapify(arr, n, largest);
    }
}

//堆排序入口
void heap_sort(int arr【】,int n){
//建堆
    for (int i = n / 2 - 1; i >= 0; i--) {
    heapify(arr, n, i);
	}
//排序
for (int i = n - 1; i >= 0; i--) {
    swap(&arr【i】, &arr【0】);
    heapify(arr, i, 0);
	}
}
int main() {
    int arr【】 = { 2,3,8,1,4,9,10,7,16,14 };
    int n = 10;
    print_arr(arr, n);
    heap_sort(arr, n);
    print_arr(arr, n);
    return 0;
}

标签:大顶,arr,下标,int,内附,堆排序,详解,节点
From: https://www.cnblogs.com/dwinternet/p/18363393

相关文章

  • 关于sizeof()与strlen()的详解与题例
    ......
  • InstructGPT: Training language models to follow instructions with human feedback
    文章目录1.InstructGPT目标2.数据集2.1SFT数据集2.2RM数据集2.3PPO数据集3.训练细节3.1SFT训练3.2RM训练3.3RLHF训练4.结论1.InstructGPT目标InstructGPT探讨了如何通过人类反馈来训练语言模型以更好地遵循用户的意图。通过对模型进行监督学习和强化......
  • windows ndis 详解
    1.WindowsNDIS详细讲解网络驱动程序接口规范(NetworkDriverInterfaceSpecification,NDIS)是MicrosoftWindows操作系统中的一个关键组件,它为网络硬件和协议之间提供了一个标准化的接口。本文将深入探讨NDIS的概念、结构、功能以及在现代网络通信中的重要性。1.NDIS简介......
  • 【Three.JS零基础入门教程】第六篇:物体详解
     前期回顾:【Three.JS零基础入门教程】第一篇:搭建开发环境【Three.JS零基础入门教程】第二篇:起步案例【Three.JS零基础入门教程】第三篇:开发辅助【Three.JS零基础入门教程】第四篇:基础变换【Three.JS零基础入门教程】第五篇:项目规划下面将进一步详解介绍Threejs中的常用......
  • 南瓜书公式详解------第七章(贝叶斯)
    式7.5R(c∣x)=......
  • 南瓜书公式详解------第五章(反向传播、波尔兹曼机)
    式5.2(感知学习参数更新)Δwi=η......
  • 南瓜书公式详解------第六章-1(支持向量机1)
    式6.8(支持向量机目标函数)L(w,b,......
  • 数据结构与算法详解
    目录一、引言二、数据结构1.数组(Array)定义特点应用场景总结表格2.链表(LinkedList)定义特点应用场景总结表格3.栈(Stack)定义特点应用场景总结表格4.队列(Queue)定义特点应用场景总结表格5.树(Tree)定义特点应用场景总结表格6.哈希表(HashTable)定......
  • 静态库与共享库详解
    静态库与共享库详解在开发和使用C语言编写程序时,库文件(Library)是一个重要的组成部分。库文件是目标文件的集合,可以被其他代码调用。将代码封装编译成库文件有助于简化使用、便于管理,并提高安全性和保密性。本文将详细介绍静态库和共享库(动态库),并演示如何创建和使用它们。......
  • SpringBoot整合日志功能(slf4j+logback)详解
     目录一、日志门面与日志实现1.1什么是日志门面和日志实现?1.2为什么需要日志门面?二、简介三、日志格式四、记录日志4.1使用日志工厂4.2 使用Lombok的@Slf4j注解五、日志级别5.1日志级别介绍5.2配置日志级别5.3指定某个包下的类使用某个级别5.4占位符打......