当前位置: 首页 > news >正文

八大排序——选择排序/堆排序

八大排序——选择排序/堆排序

目录

一、选择排序

二、堆排序

2.1 大顶堆(升序)

2.1.1 步骤

2.1.2 代码实现

2.2 小顶堆(降序)


一、选择排序

每一趟从待排序序列中找到其最小值,然后和待排序序列的第一个值进行交换,则此时这个值变有序,待排序序列个数-1,继续下一趟,直到待排序序列个数为1时结束

void Select_Sort(int arr[], int len)
{for (int i = 0; i < len - 1; i++){int min = i;for (int j = i; j < len; j++)//找最小值 用min保存下标{if (arr[j] < arr[min])//j指向的值比min的值更小,则min更新一下,更新为j{min = j;}}if (min != i){int tmp = arr[min];arr[min] = arr[i];arr[i] = tmp;}}
}

时间复杂度O(n^2) 循环嵌套都是

空间复杂度O(1)

稳定性:不稳定 

二、堆排序

:n个节点组成的有限集合,树有且只有一个根节点“ROOT”,树除了根节点之外剩余节点还可以组成m个互不相交的有限集合(称为子树)

 二叉树:每个节点最多有俩个孩子节点

满二叉树:一颗二叉树层数为k,且有2^-1和节点。换句话说,一个二叉树,有多少层就把多少层摆满。

完全二叉树:相较于满二叉树,可以少节点,但只能从最后一层,从右至左少节点

节点的度:孩子的个数

 叶子节点:度为0的节点,最外的一层

 非叶子节点:度不为0的节点

2.1 大顶堆(升序)

是一个特殊的完全二叉树,父节点都大于等于孩子节点

2.1.1 步骤

每次确定一个最大值,然后和最后一个位置进行交换

为什么每次都能获取一个最大值,因为堆排序的核心时维护一个大顶堆(默认升序),大顶堆的唯一特征是根节点是所有值中的最大值

1. 首先将给的数组,想象成一个完全二叉树

2.将这颗完全二叉树调整成一个大顶堆(首次调整是由内到外的调整:从最后一个非叶子节点作为根节点的分支二叉树开始调整,然后从右至左,从下之上

3. 将这课大顶堆的根节点(最大的值)和其最后一个节点进行交换,交换完成后,让此时这个节点断开连接,不参与后续排序、

4. 此时这颗完全二叉树不再是大顶堆,我们需要重新调整为大顶堆,不需要从上面那样从内到外调整,只需要调整最外层的

5. 反复执行三四直到大顶堆中剩下一个节点

2.1.2 代码实现

#include <stdio.h>// 函数声明,用于显示排序后的数组
void Show(int arr[], int len);// 调整堆的函数,使其满足大顶堆的性质
void Adjust_Heap(int arr[], int start, int end) {int tmp = arr[start]; // 保存当前起始节点的值int max_child = start * 2 + 1; // 初始化最大子节点索引为起始节点的左子节点// 循环,直到最后一个节点for (; max_child <= end; max_child = start * 2 + 1) {// 如果右子节点存在且大于左子节点,则更新最大子节点索引if (max_child + 1 <= end && arr[max_child + 1] > arr[max_child]) {max_child++;}// 如果最大子节点的值大于保存的起始节点的值,则交换它们if (arr[max_child] > tmp) {arr[start] = arr[max_child];start = max_child; // 更新起始节点为最大子节点} else {break; // 如果最大子节点的值不大于保存的起始节点的值,则结束循环}}arr[start] = tmp; // 将保存的起始节点的值放到最终位置
}// 堆排序函数
void Heap_Sort(int arr[], int len) {// 构建大顶堆for (int i = ((len - 1) - 1) / 2; i >= 0; i--) {Adjust_Heap(arr, i, len - 1); // 从最后一个非叶子节点开始调整堆}// 排序过程for (int i = 0; i < len - 1; i++) {int tmp = arr[0]; // 保存堆顶元素arr[0] = arr[len - 1 - i]; // 将堆顶元素与未排序部分的最后一个元素交换arr[len - 1 - i] = tmp; // 完成交换Adjust_Heap(arr, 0, len - 1 - i - 1); // 重新调整堆}
}// 主函数
int main() {int arr[] = { 10000, 20000, -100, 195, 71, 89, 42, 8, 902, 894, 194, 80, 194, 128, 90, 18, 490, 18, 409, 180, 95, 12, 489, 404 };int len = sizeof(arr) / sizeof(arr[0]); // 计算数组长度Heap_Sort(arr, len); // 调用堆排序函数对数组进行排序Show(arr, len); // 显示排序后的数组return 0;
}// 显示数组的函数
void Show(int arr[], int len) {for (int i = 0; i < len; i++) {printf("%d ", arr[i]); // 打印数组元素}printf("\n"); // 打印换行符
}

2.2 小顶堆(降序)

是一个特殊的完全二叉树,父节点都小于等于孩子节点。

http://www.xdnf.cn/news/102295.html

相关文章:

  • 第六章 QT基础:3、QT的打包和部署
  • JAVA----方法
  • 脂质体挤出器有哪些知名品牌?
  • 解锁webpack:对html、css、js及图片资源的抽离打包处理
  • 云贝餐饮 最新 V3 独立连锁版 全开源 多端源码 VUE 可二开
  • C# 文件读取
  • 极狐GitLab 的压缩和合并是什么?
  • AI赋能社区生态:虎跃办公的网址导航革新实践
  • 一 、环境的安装 Anaconda + Pycharm + PaddlePaddle
  • Execl 最佳字体和大小推荐[特殊字符]
  • 状态空间方程 —— 极点配置
  • 域名 → IP 的解析全过程
  • python异步协程async调用过程图解
  • Linux[指令与权限]
  • ZYNQ笔记(十三):双核 AMP 通信实验
  • 星火燎原:Spark技术如何重塑大数据处理格局
  • 8. kubernetes的service原理
  • MySQL 8 自动安装脚本(CentOS-7 系统)
  • 【哈希表】1399. 统计最大组的数目
  • 从零开始搭建Django博客③--前端界面实现
  • 如何批量为多张图片(JPG、PNG、BMP、WEBP 等格式)添加自定义水印保护
  • ApacheJmeter使用权威指南
  • 【AI】Trae的MCP配置及使用测试
  • 在统信UOS/麒麟Kylin OS操作系统中配置APT和GIT代理
  • 【论文阅读25】-滑坡时间预测-PFTF
  • 时分复用、频分复用和码分复用简要比较分析
  • Linux进程调度
  • AI PPT创作原理解析:让你的演示文稿更智能
  • Python内置函数---breakpoint()
  • 《算法笔记》10.4小节——图算法专题->最短路径 问题 D: 最短路径