十大排序算法【2】---归并排序、计数排序、基数排序、桶排序、堆排序

news/2024/7/24 18:47:19/文章来源:https://blog.csdn.net/weixin_45690131/article/details/139295781

动画演示

排序算法动画:
https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html

1、归并排序

// 归并排序:用C++写比较简单易懂 
//时间复杂度O(nlog_2 n)空间复杂度O(n)
// 归并两个子数组的函数
// merge归并函数
void merge(std::vector<int>& data, int left, int mid, int right)
{int leftlength = mid - left + 1;int rightlength = right - mid;//把左右的数据存入新的数组中,并命名为L、Rstd::vector<int> L(leftlength), R(rightlength);for (int i = 0; i < leftlength; i++)L[i] = data[left + i];for (int j = 0; j < rightlength; j++)R[j] = data[mid + 1 + j];int i = 0;int j = 0;int k = left;while (i < leftlength && j < rightlength){if (L[i] <= R[j])//若是左边的小,放入原来数组中{data[k] = L[i];i++;//左边数组的下标++;}else//若是右边的小,放入原来数组中{data[k] = R[j];j++;//右边数组的下标++;}k++;//原来数组的下标++;}//复制剩余数据,这步是出现在最后的最终排序,应该是左边可能出现多余,中间的值加入了左边数组while (i<leftlength){data[k++] = L[i++];}while (j < rightlength){data[k++] = R[j++];}}// 归并排序 时间复杂度O(nlog_2 n) 空间复杂度O(n)
// left和right是数组的最小下标和最大下标
void MergeSort(std::vector<int>& data, int left,int right)
{if (left < right){int mid = left + (right - left)/2;MergeSort(data, left, mid);MergeSort(data, mid + 1, right);merge(data, left, mid, right);}
}

2、计数排序

// 计数排序CountingSort,小数据排序,数组中最大值比较小的情况
// 把所有的数计数,从小到大再排一遍
// 空间复杂度O(n+k),时间复杂度O(n+k),不算找最大值的时间
int* CountingSort(int data[], size_t size)
{if (data == NULL)return 0;//找到原数组中最大值int max = 0;for (size_t i = 0; i < size; i++){if (data[i] > max)max = data[i];}//新建一个计数的数组int* count = (int*)malloc(sizeof(int) * (max + 1));memset(count, 0, sizeof(int) * (max + 1));//计数for (int i = 0; i < size; i++){count[data[i]]++;}int index = 0;for (int i = 0; i <= max; i++){//有计数,原数组就添加一个while (count[i]>0){data[index++] = i;count[i]--;}}free(count);
}

3、基数排序

//基数排序RadixSort
//时间复杂度O(n*k)空间复杂度O(n+k)
//计数排序的优化,用0-9计数,把数据的个,十,百...等按照大小排序
//先排个位,再往后排
int* RadixSort(int data[], size_t size)
{int* temp = (int*)malloc(sizeof(int) * size);int count[10] = { 0 }; //找到原数组中最大值int max = 0;for (size_t i = 0; i < size; i++){if (data[i] > max)max = data[i];}int num = 0;//循环的次数,看有几位while (max>0){	num++;max /= 10;}int radix = 1;for (int j = 0; j < num; j++){memset(count, 0, sizeof(count));//构造count数组for (size_t i = 0; i < size; i++){int index = (data[i] / radix) % 10;//取个位数count[index]++;}//整合countfor (int m = 1; m < 10; m++){count[m] += count[m - 1];}//按照末尾排序for (int k = (int)(size - 1); k >= 0; k--){int index = (data[k] / radix) % 10;//取个位数temp[count[index] - 1] = data[k];count[index]--;}memcpy(data, temp, sizeof(int) * size);radix *= 10;}free(temp);return data;
}

4、桶排序

//桶排序BucketSort:
//时间复杂度O(n+k),空间复杂度O(n+k)
typedef struct BucketNode
{int value;BucketNode* next;
}BUCKNODE,*PBUCKNODE ;int* BucketSort(int data[], size_t size)
{//创建桶 二维数组PBUCKNODE* bucket = (PBUCKNODE*)malloc((size + 1)*sizeof(PBUCKNODE));//size+1个桶指针memset(bucket, 0, (size + 1) * sizeof(PBUCKNODE));//找到原数组中最大值int max = 0;for (size_t i = 0; i < size; i++){if (data[i] > max)max = data[i];}for (size_t i = 0; i < size; i++){int index = (data[i] * (int)size) / max;BUCKNODE* node = (BUCKNODE*)malloc(sizeof(BUCKNODE));node->next = NULL;node->value = data[i];PBUCKNODE* cur = bucket+index;//找到当前桶的地址if (*cur == NULL){*cur = node;//如果桶里面没有数据,把数据添加到桶里面}  else{PBUCKNODE temp = *cur;//桶的第一个元素指针if (temp->value > node->value)//进来的值小于第一个数据{node->next = temp;*cur = node;continue;}if (temp->next == NULL)//进来的值大于第一个数据{temp->next = node;continue;}while (temp->next != NULL)//桶里面有多个数据{if (temp->next->value > node->value)//如果新来的数据小于第二个{node->next = temp->next;temp->next = node;break;}if (temp->next->next == NULL)//新来的数据大于第二个,且如果第三个数据为空{temp->next->next = node;break;}temp = temp->next;}}}int j = 0;for (size_t i = 0; i <= size; i++){while (bucket[i] != NULL){data[j++] = bucket[i]->value;PBUCKNODE temp = bucket[i];bucket[i] = bucket[i]->next;//依次提出桶里面的元素free(temp);}}free(bucket);return data;
}

5、堆排序

//堆排序,把数组当成完全二叉树HeapSort
//时间和空间复杂度为O(nlog_2 n)
//更改根节点后面所有的数据排序
void Change(int data[], size_t size, int index)
{int left = 2 * index + 1;int right = 2 * index + 2;int maxIdx = index;//有子节点的话,判断有子节点是否更大if (left<(int)size && data[left]>data[maxIdx])maxIdx = left;if (right<(int)size && data[right]>data[maxIdx])maxIdx = right;if (maxIdx != index){int temp = data[index];data[index] = data[maxIdx];data[maxIdx] = temp;Change(data, size, maxIdx);//对后面的节点继续}
}
//先对倒数第二层的根节点中的数据排序,再依次向上继续排序,
//直到第一个根节点为最大值
//保存最大值,并把最后的叶子节点替换为第一个根节点,循环
int* HeapSort(int data[], size_t size)
{//找到最后一个根节点for (size_t i =  size / 2 - 1; i >= 0; i--){Change(data, size, i);//调整这个根节点下面所有子节点}//找到最后一个叶子节点for (size_t i = size - 1; i >= 1; i--){int temp = data[0];//交换完后。最大值被保存,不再继续排序data[0] = data[i];data[i] = temp;Change(data, i, 0);//调整所有子节点}return data;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_1054418.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Money Trees

思路分析: 利用双指针 l1始终作为起点,ri,不断更新终点 #include<iostream> #include<cstring> #include<string> #include<algorithm> #define int long long using namespace std; int w[2000005],h[2000005],s[2000005]; int t,n,m,l,r; signed m…

嵌入式单片机笔试题

DC-DC 和 LDO两者有何区别&#xff1f; DC-DC转换器&#xff08;直流-直流转换器&#xff09;和LDO&#xff08;低压差线性稳压器&#xff09;都是用于电源管理的设备&#xff0c;但它们在原理和特性上有一些显著的区别&#xff1a; 原理&#xff1a; DC-DC转换器通过改变输…

前端 CSS 经典:图片边框

前言&#xff1a;有这么一个业务&#xff0c;需要边框随着图片宽度的变化而变化&#xff0c;比如一些聊天的气泡框等。 实现原理&#xff1a;使用 border-image 属性 效果图&#xff1a; 实现代码&#xff1a; <!DOCTYPE html> <html lang"en"><he…

vue项目中使用json编辑器

实现效果&#xff1a; 借助插件json-editor-vue3实现效果如图一&#xff0c;如果嫌丑可以通过类名改一下样式如图二。 实现过程&#xff1a; 安装插件&#xff1a;npm install json-editor-vue3 文档链接&#xff1a;GitCode - 开发者的代码家园 <script setup name&quo…

day17

第一题 本题可以采用快速排序的思想&#xff0c;适应随机数指定和三指针划分数组为三个区域的思想&#xff1a; 其中指针的移动细节如上题故事&#xff0c;如下所示&#xff1a; 当a区域的商都大于k时&#xff0c;我们要查找的k位置元素就在左区域&#xff0c;我们进一步在左区…

【LORA协议栈】工作记录

一、硬件资源 MCU型号&#xff1a;STM32F401xE。Lora芯片&#xff1a;SX1276。硬件看门狗。ATT7022E三相电能专用计量芯片。 二、功能简介 作为一个组件&#xff0c;通过485与网关或者各种子设备连接在一起。支持boot升级。通过SPI与LORA芯片通信。接收和发送数据。有3路通信…

vue3 调用本地exe

1、注册表注册 在注册表中直接按照图2注册数据&#xff1b;也可以按照图3注册表的文件创建文档&#xff0c;然后点击打开&#xff0c;将会将注册表写入window系统。 图2 Windows Registry Editor Version 5.00 [HKEY_CLASSES_ROOT\F1] "URL:F1 Protocol Handler" &q…

Rust 赋能前端 -- 写一个 File 转 Img 的功能

所有耀眼的成绩,都需要苦熬,熬得过,出众;熬不过,出局 大家好,我是柒八九。一个专注于前端开发技术/Rust及AI应用知识分享的Coder 此篇文章所涉及到的技术有 Rustwasm-bindgen/js-sys/web-sysWeb WorkerWebAssemblyWebpack/Vite配置WebAssemblyOffscreenCanvas脚手架生成项…

Android Ktor 网络请求框架

Ktor 是一个由 JetBrains 开发的用于 Kotlin 编程语言的应用框架&#xff0c;旨在创建高性能的异步服务器和客户端应用程序。由于完全基于 Kotlin 语言&#xff0c;Ktor 能够让开发者编写出简洁、可读性强且功能强大的代码&#xff0c;特别适合那些已经熟悉 Kotlin 的开发人员。…

提取COCO 数据集的部分类

1.python提取COCO数据集中特定的类 安装pycocotools github地址&#xff1a;https://github.com/philferriere/cocoapi pip install githttps://github.com/philferriere/cocoapi.git#subdirectoryPythonAPI若报错&#xff0c;pip install githttps://github.com/philferriere…

ROS运行文件(LaunchFile)和参数(Parameter)

本文主要介绍ROS的Launch File和Parameter概念&#xff0c;通过Launch File启动单个或多个节点&#xff0c;并通过Parameter配置启动参数。 更多内容&#xff0c;访问专栏目录获取实时更新。 当你的应用中包含了很多工作包&#xff0c;每个工作包了又包含了多个节点时&#xff…

香橙派AIpro开发板初体验

香橙派AIpro开发板初体验 一、引言 在当前的AI发展浪潮中&#xff0c;边缘计算逐渐成为了研究的热点。香橙派AIpro开发板作为一款基于昇腾AI技术的开发板&#xff0c;凭借其强大的算力和丰富的接口&#xff0c;为AI边缘计算提供了强大的支持。最近&#xff0c;我也是拿到了官…

VUE3 学习笔记(6):data数据的监听、表单绑定、操作DOM

data数据的监听&#xff08;侦听&#xff09; 对于data的值的监听&#xff0c;可以用watch中与data中的参数命名一致的值做为函数进行获取监听变动前后的值再做逻辑判断&#xff0c;如下图所示。 示例代码 <template><div><p :class"classDemo">{…

用Python实现办公自动化

&#x1f482; 个人网站:【 摸鱼游戏】【神级代码资源网站】【工具大全】&#x1f91f; 一站式轻松构建小程序、Web网站、移动应用&#xff1a;&#x1f449;注册地址&#x1f91f; 基于Web端打造的&#xff1a;&#x1f449;轻量化工具创作平台&#x1f485; 想寻找共同学习交…

机器学习-3-特征工程的重要性及常用特征选择方法

参考特征重要性:理解机器学习模型预测中的关键因素 参考[数据分析]特征选择的方法 1 特征重要性 特征重要性帮助我们理解哪些特征或变量对模型预测的影响最大。 特征重要性是数据科学中一个至关重要的概念,尤其是在建立预测性任务的模型时。想象你正在尝试预测明天是否会下…

Docker部署SpringBoot项目(jar包+Mysql)

部署Java项目 项目准备准备Java项目镜像准备配置网络 部署项目细节展示 项目准备 准备Java项目 hmall项目是一个maven聚合项目&#xff0c;使用IDEA打开hmall项目&#xff0c;查看项目结构如图&#xff1a; 我们要部署的就是其中的hm-service&#xff0c;其中的配置文件采用…

开源与闭源:AI大模型发展路径的博弈

一、引言 在人工智能&#xff08;AI&#xff09;领域&#xff0c;大模型以其卓越的性能和广泛的应用前景&#xff0c;成为了近年来技术发展的热点。然而&#xff0c;在大模型的发展路径上&#xff0c;开源与闭源两种模式一直存在着激烈的博弈。本文将深入探讨这两种模式在大模…

python-合并排列数组 I

问题描述&#xff1a;合并两个按升序排列的整数数组a和b&#xff0c;形成一个新数组&#xff0c;新数组也要按升序排列。 问题示例&#xff1a;输入A[1],B[1],输出[1,1],返回合并后的数组。输入A[1,2,3,4],B[2,4,5,6],输出[1,2,2,3,4,4,5,6],返回合并所有元素后的数组。 完整代…

【旋转链表】python

目录 题目&#xff1a; 思路&#xff1a; 代码&#xff1a; 题目&#xff1a; 思路&#xff1a; 求链表长度&#xff1b;找出倒数第 k1 个节点&#xff1b; 3.链表重整&#xff1a;将链表的倒数第 k1 个节点和倒数第 k个节点断开&#xff0c;并把后半部分拼接到链表的头部。…

CTFHUB技能树——SSRF(一)

目录 一、SSRF(服务器端请求伪造) 漏洞产生原理: 漏洞一般存在于 产生SSRF漏洞的函数&#xff08;PHP&#xff09;&#xff1a; 发现SSRF漏洞时&#xff1a; SSRF危害&#xff1a; SSRF漏洞利用手段&#xff1a; SSRF绕过方法&#xff1a; 二、CTFHUB技能树 SSRF 1.Ht…