超全排序C语言实现

排序

文章目录

  • 排序
    • 插入排序
      • 直接插入排序
      • 折半查找插入排序
      • 希尔排序
    • 选择排序
      • 简单选择排序
      • 堆排序
        • 一、构建堆
          • **堆有以下性质**:
          • **堆的存储方式**:
          • **设计堆**
            • 数据结构
            • 堆的维护
            • 堆的初始化
            • 创建堆
            • 插入一个元素
            • 删除一个元素
            • 返回有效元素的个数
            • 获得优先级最高的元素
            • 全部代码
        • 二、使用堆进行排序
    • 交换排序
      • 冒泡排序
      • 快速排序

下面针对排序都是升序,且排序的元素都是整型。

插入排序

直接插入排序

原理:将无序的元素插入到有序的序列

基本思路:

  1. 将第一个元素作为一个有序序列,从第二个开始依次添加元素到有序序列中
  2. 现假设要添加第i个元素到有序序列中去,有序序列最后一个元素下标为i-1,我们只需要确定第i个元素在有序序列中的位置即可
  3. 在确定位置时,应满足如果要插入的元素小于前一个元素,那么前一个元素往后移,直到遇到插入元素大于等于前一个元素为止
  4. 要插入元素有n-1个,因此外循环为n-1;内循环是为当前元素找插入位置,判断条件为前面元素大于插入元素
void InsertSort(int* arr,int n){//i为第几个元素插入到有序序列中,j为遍历有序序列的下标//temp保存当前插入元素的值,因为前面元素要向后移动,覆盖插入元素的值,所以要保存int i,j,temp;for(i=1;i<n;i++){//从有序序列最后一个开始j=i-1;temp=arr[i];while(j>=0 && arr[j]>temp){//后移arr[j+1]=arr[j];j--;}//arr[j]<=temparr[j+1]=temp;}
}
image-20241113124112064

折半查找插入排序

原理:和直接插入排序相似,只是在找插入位置时,使用折半查找,减少了比较次数,但是元素移动次数没有改变

基本思路:

  1. 在有序序列中找插入元素的位置
// 1 2 4 5 7 9   e==6
//mid=2,4<6,low=mid+1=3
//mid=4,7>e,high=mid-1=3初始化低位和高位:low = 0,high = len - 1,表示查找的初始范围是数组的从头到尾。
避免加法溢出:mid = low + (high - low) / 2;,避免 low + high 可能导致的溢出问题。
查找过程:
如果 arr[mid] < e,则说明目标元素 e 应该插入到 mid 的右边,即更新 low = mid + 1。
如果 arr[mid] > e,则目标元素 e 应该插入到 mid 的左边,即更新 high = mid - 1。
如果 arr[mid] == e,说明目标元素已经存在,可以直接返回当前位置+1。
返回插入位置:
当 low 大于 high 时,目标元素没有找到,low 位置就是元素 e 应该插入的位置。
int BinarySearchInsertPosition(int* arr, int len, int e) {int low = 0, high = len - 1;// 避免加法溢出,防止 high + low 可能导致溢出int mid = low + (high - low) / 2;// 查找插入位置while (low <= high) {if (arr[mid] < e) {// 如果中间元素小于目标元素,则查找右半部分low = mid + 1;} else if (arr[mid] > e) {// 如果中间元素大于目标元素,则查找左半部分high = mid - 1;} else {// 如果中间元素等于目标元素,返回当前的 mid,表示可以插入到该位置return mid + 1;}// 重新计算中间索引mid = low + (high - low) / 2;}// 如果没有找到相等的元素,low 就是应该插入的位置return low;
}void Bsearch_InsertSort(int* arr,int n){int i,j,temp;for(i=1;i<n;i++){j=i-1;temp=arr[i];//查找应插入位置int pos=BinarySearchInsertPosition(arr,n,temp);//移动元素for(int k=i;k>pos;k--){arr[k]=arr[k-1];}arr[pos]=temp;}
}
image-20241113132116845

希尔排序

原理:希尔排序又叫缩小增量排序法,设置一个增量dx,将待排序序列进行分组,如果dx=5的话,那么待排序序列足够长的话,会被分为5组,即[(0,5,10,15…),(1,6,11,16…)…(4,9,14,19)](这里的数字都是下标),在这5组在组内分别排序后,每次从这5个分组按序取一个元素,直到所有元素取完;之后dx=2,再次分组排序,最后dx=1,就是直接插入排序。

基本步骤:

  1. 初始化步长,通常设置为数组长度的一半

  2. 对每个分组进行插入排序

    void ShellSort(int* arr,int n){int i,j,temp;for(int gap=n/2;gap>0;gap/=2){for(i=gap;i<n;i++){temp=arr[i];j=i;while(j>=gap&&arr[j-gap]>temp){arr[j]=arr[j-gap];j-=gap;}arr[j]=temp;}}
    }
    解释:假设数组的长度为16,第一次时,gap=8,i从815,分为了8组,依次和前面的i-gap进行比较排序第二次时,gap=4,i从415,每次从第二个元素开始排序。要保证下一个元素排序时,前面的元素是有序的,如果从1215排序,前面3个元素不一定是有序的因此必须从gap开始,第一个元素有序,这样是正确的。然后依次轮到第一组的第二个元素,第二组的第二个元素,第三组的第二个元素,第四组的第二个元素。
    
    image-20241113154216849

选择排序

简单选择排序

void SelectionSort(int* arr,int n){int i,j,temp;//每次选择一个小的元素到序列最前面,只需选择n-1个元素就可以让序列有序for(i=0;i<n-1;i++){//j从i开始for(j=i;j<n;j++){if(arr[i]>arr[j]){temp=arr[i];arr[i]=arr[j];arr[j]=temp;}}}
}

堆排序

一、构建堆

堆排序要利用一个数据结构——堆,根据堆顶元素的不同意义,分为大顶堆和小顶堆。所以下面先介绍堆的性质和如何创建堆等。

堆有以下性质
  • 堆中某个节点的值不大于或不小于其父节点的值

  • 堆总是一棵完全二叉树(因此可以使用数组来存储)

堆的存储方式

从堆的概念可知,堆是一棵完全二叉树,因此可以层序的规则采用顺序的方式来高效存储。

  • 假设i为节点在数组中的下标,则有:

  • 如果i为0,则i表示的节点为根节点,否则i节点的双亲节点为 (i - 1)/2。

  • 如果2 * i + 1 小于节点个数,则节点i的左孩子下标为2 * i + 1,否则没有左孩子。

  • 如果2 * i + 2 小于节点个数,则节点i的右孩子下标为2 * i + 2,否则没有右孩子。

设计堆

​ 下面我们都以大顶堆为例。

数据结构
#define MAXSIZE_HEAP 100 
typedef struct Heap{int *arr;int Size;//堆的大小int usedSize;//现有多少个元素
}MyHeap;
堆的维护
  1. 向上调整

    向上调整主要用于新元素添加到堆中去时,用于和父节点进行比较交换,以维护堆的性质。

    基本步骤:

    • 不断和父节点作比较,判断是否交换,一直到根节点
    void shiftUp(MyHeap* heap,int child){//获得父节点的下标int parent=(child-1)/2;while(child>0){if(heap->arr[parent]>=heap->arr[child]){//满足大顶堆的性质,结束调整break;}else{//做交换int temp=heap->arr[parent];heap->arr[parent]=heap->arr[child];heap->arr[child]=temp;//交换之后影响上面的树,继续调整child=parent;parent=(child-1)/2;}}
    }
    
  2. 向下调整

    向下调整主要用于堆的创建和堆顶元素发生改变时。

    void shiftDown(MyHeap* heap,int parent){//有孩子的话,左孩子一定有int child=2*parent+1;while(child<heap->usedSize){if(child+1<heap->usedSize&&heap->arr[child+1]>heap->arr[child]){//如果右孩子存在且大于左孩子的值,获得要和孩子节点交换的下标child=child+1;}if(heap->arr[parent]>=heap->arr[child]){//如果父节点大于等于孩子节点,满足大顶堆性质break;}else{//交换int temp=heap->arr[parent];heap->arr[parent]=heap->arr[child];heap->arr[child]=temp;//交换之后可能会影响下面的子树,如果交换的这个孩子节点有孩子的话,调整这棵子树。parent=child;child=2*parent+1;}}
    }
    
堆的初始化
//Size为指定的初始化堆的大小
void InitHeap(MyHeap* heap, int* arr, int len, int Size) {heap->arr = (int*)malloc(sizeof(int) * Size);heap->Size = Size;heap->usedSize = 0;for (int i = 0; i < len; i++) {heap->arr[i] = arr[i];heap->usedSize++;}
}
创建堆

基本步骤:

  • 找到最后一个非叶子节点
  • 不断向下调整,直到到达根节点,全部调整完成,堆也就创建好了
void CreateHeap(MyHeap* heap){//找到最后一个叶子节点的父节点,从这里开始向下调整,这时,整棵树还是比较乱的int StartRoot=(heap->usedSize-1-1)/2;for(;StartRoot>=0;StartRoot--){shiftDown(heap,StartRoot);}
}
插入一个元素

插入元素都从最后一个位置插入

void offer(MyHeap* heap,int e){//先判断堆是否还可以添加元素if(heap->usedSize==heap->Size){//堆满了,扩容int* temp=(int*)malloc(sizeof(int)*2*heap->Size);for(int i=0;i<heap->Size;i++){temp[i]=heap->arr[i];}free(heap->arr);heap->arr=temp;heap->Size=2*heap->Size;}heap->arr[(heap->usedSize)++]=e;//插入元素后,进行向上调整shiftUp(heap,heap->usedSize-1);
}
删除一个元素

删除元素一定是堆顶元素,因为我们总是获得优先级最高的元素。

int poll(MyHeap* heap){if(heap->usedSize>0){int ret=heap->arr[0];heap->arr[0]=heap->arr[heap->usedSize-1];//向下调整shiftDown(heap,0);(heap->usedSize)--;return ret;}else{printf("Heap is empty.");exit(1);}}
返回有效元素的个数
int size(MyHeap* heap){return heap->usedSize;
}
获得优先级最高的元素
int peek(MyHeap* heap){if(heap->usedSize>0){return heap->arr[0];}else{printf("Heap is empty.");exit(1);}
}
全部代码
#define MAXSIZE_HEAP 100 
typedef struct Heap{int *arr;int Size;//堆的大小int usedSize;//现有多少个元素
}MyHeap;void shiftUp(MyHeap* heap,int child);
void shiftDown(MyHeap* heap,int parent);
void InitHeap(MyHeap* heap,int* arr,int len,int Size);
void CreateHeap(MyHeap* heap);
void offer(MyHeap* heap,int e);
int poll(MyHeap* heap);
int size(MyHeap* heap);
int peek(MyHeap* heap);//--------------------------------------------------------------
void shiftUp(MyHeap* heap,int child){//获得父节点的下标int parent=(child-1)/2;while(child>0){if(heap->arr[parent]>=heap->arr[child]){//满足大顶堆的性质,结束调整break;}else{//做交换int temp=heap->arr[parent];heap->arr[parent]=heap->arr[child];heap->arr[child]=temp;//交换之后影响上面的树,继续调整child=parent;parent=(child-1)/2;}}
}void shiftDown(MyHeap* heap,int parent){//有孩子的话,左孩子一定有int child=2*parent+1;while(child<heap->usedSize){if(child+1<heap->usedSize&&heap->arr[child+1]>heap->arr[child]){//如果右孩子存在且大于左孩子的值,获得要和孩子节点交换的下标child=child+1;}if(heap->arr[parent]>=heap->arr[child]){//如果父节点大于等于孩子节点,满足大顶堆性质break;}else{//交换int temp=heap->arr[parent];heap->arr[parent]=heap->arr[child];heap->arr[child]=temp;//交换之后可能会影响下面的子树,如果交换的这个孩子节点有孩子的话,调整这棵子树。parent=child;child=2*parent+1;}}
}//Size为指定的初始化堆的大小
void InitHeap(MyHeap* heap, int* arr, int len, int Size) {heap->arr = (int*)malloc(sizeof(int) * Size);heap->Size = Size;heap->usedSize = 0;for (int i = 0; i < len; i++) {heap->arr[i] = arr[i];heap->usedSize++;}
}void CreateHeap(MyHeap* heap){//找到最后一个叶子节点的父节点,从这里开始向下调整,这时,整棵树还是比较乱的int StartRoot=(heap->usedSize-1-1)/2;for(;StartRoot>=0;StartRoot--){shiftDown(heap,StartRoot);}
}void offer(MyHeap* heap,int e){//先判断堆是否还可以添加元素if(heap->usedSize==heap->Size){//堆满了,扩容int* temp=(int*)malloc(sizeof(int)*2*heap->Size);for(int i=0;i<heap->Size;i++){temp[i]=heap->arr[i];}free(heap->arr);heap->arr=temp;heap->Size=2*heap->Size;}heap->arr[(heap->usedSize)++]=e;//插入元素后,进行向上调整shiftUp(heap,heap->usedSize-1);
}int poll(MyHeap* heap){if(heap->usedSize>0){int ret=heap->arr[0];heap->arr[0]=heap->arr[heap->usedSize-1];//向下调整shiftDown(heap,0);(heap->usedSize)--;return ret;}else{printf("Heap is empty.");exit(1);}}int peek(MyHeap* heap){if(heap->usedSize>0){return heap->arr[0];}else{printf("Heap is empty.");exit(1);}
}int size(MyHeap* heap){return heap->usedSize;
}
二、使用堆进行排序
void HeapSort(int* arr,int len){MyHeap heap;//初始化堆的数据InitHeap(&heap,arr,len,len);//构建大顶堆CreateHeap(&heap);//对于n个元素,要进行poll操作n-1次for(int i=1;i<len;i++){arr[len-i]=poll(&heap);}arr[0]=peek(&heap);
}
image-20241113233306569

交换排序

冒泡排序

void Bubble(int* arr,int n){int i,j,temp;//i控制轮数,每次会将一个大的元素,只需要移动n-1个元素之后,整个序列就有序了for(i=0;i<n-1;i++){int flag=1;for(j=0;j<n-1-i;j++){if(arr[j]>arr[j+1]){temp=arr[j];arr[j]=arr[j+1];arr[j+1]=temp;flag=0;}}if(flag==1){//表明所有元素有序break;}}
}

快速排序

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

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

笔记整理—linux驱动开发部分(11)中断上下文

触摸屏分为两种&#xff0c;一种为电阻式触摸屏&#xff0c;另一种为电容式触摸屏。电阻式触摸屏&#xff08;x、x-、y、y-、AD&#xff09;有两种接口&#xff0c;一种为SOC自带的接口&#xff08;miscinput或platform&#xff09;&#xff0c;第二种为外部IC&#xff0c;通过…

网络编程示例之开发板测试

编译elf1_cmd_net程序 &#xff08;一&#xff09;设置交叉编译环境。 &#xff08;二&#xff09;查看elf1_cmd_net文件夹Makefile文件。查看当前编译规则&#xff0c;net_demo是编译整个工程&#xff0c;clean是清除工程。 &#xff08;三&#xff09;输入命令。 &#xff0…

【GD32】(一) 开发方式简介及标准库开发入门

文章目录 0 前言1 开发方式选择2 标准库模板的创建3 遇到的问题和解决方法 0 前言 因为项目关系&#xff0c;需要使用GD32。之前对此早有耳闻&#xff0c;知道这个是一个STM32的替代品&#xff0c;据说甚至可以直接烧录STM32的程序&#xff08;一般是同型号&#xff09;&#x…

Java NIO 核心知识总结

NIO 简介 在传统的 Java I/O 模型&#xff08;BIO&#xff09;中&#xff0c;I/O 操作是以阻塞的方式进行的。也就是说&#xff0c;当一个线程执行一个 I/O 操作时&#xff0c;它会被阻塞直到操作完成。这种阻塞模型在处理多个并发连接时可能会导致性能瓶颈&#xff0c;因为需…

Spring如何解决循环依赖的问题

Spring 如何解决循环依赖的问题 Spring 是通过三级缓存来解决循环依赖问题&#xff0c;第一级缓存里面存储完整的Bean实例&#xff0c;这些实例是可以直接被使用的&#xff0c;第二级缓存存储的是实例化后但是还没有设置属性值的Bean实例&#xff0c;也就是Bean里面的 依赖注入…

深度图变换器的新突破:DeepGraph

人工智能咨询培训老师叶梓 转载标明出处 在图变换器领域&#xff0c;尽管其全局注意力机制在图结构数据处理上显示出了巨大潜力&#xff0c;但现有的图变换器模型却普遍较浅&#xff0c;通常不超过12层。这一现象引发了学者们对于“增加层数是否能进一步提升图变换器性能”的深…

单体架构 IM 系统之 Server 节点状态化分析

基于 http 短轮询模式的单体架构的 IM 系统见下图&#xff0c;即客户端通过 http 周期性地轮询访问 server 实现消息的即时通讯&#xff0c;也就是我们前面提到的 “信箱模型”。“信箱模型” 虽然实现非常容易&#xff0c;但是消息的实时性不高。 我们在上一篇文章&#xff08…

阿里云通义大模型团队开源Qwen2.5-Coder:AI编程新纪元

&#x1f680; 11月12日&#xff0c;阿里云通义大模型团队宣布开源通义千问代码模型全系列&#xff0c;共6款Qwen2.5-Coder模型。这些模型在同等尺寸下均取得了业界最佳效果&#xff0c;其中32B尺寸的旗舰代码模型在十余项基准评测中均取得开源最佳成绩&#xff0c;成为全球最强…

计算机网络(8)数据链路层之子层

上一篇已经讲到数据链路层可以分为两个子层&#xff0c;这次将重点讲解子层的作用和ppp协议 数据链路层的子层 数据链路层通常被分为两个子层&#xff1a; 逻辑链路控制子层&#xff08;LLC&#xff0c;Logical Link Control&#xff09;&#xff1a; LLC子层负责在数据链路…

【操作系统】输入/输出(I/O)管理

王道笔记 一、I/O管理描述 1.1 I/O设备的概念和分类 1.1.1 什么是I/O设备 “I/O”就是“输入/输出”&#xff08;Input/Output&#xff09; I/O设备机会可以将数据输入到计算机&#xff0c;或者可以接收计算机输出数据的外部设备&#xff0c;属于计算机中的硬件部件。下图就…

Day44 | 动态规划 :状态机DP 买卖股票的最佳时机IV买卖股票的最佳时机III309.买卖股票的最佳时机含冷冻期

Day44 | 动态规划 &#xff1a;状态机DP 买卖股票的最佳时机IV&&买卖股票的最佳时机III&&309.买卖股票的最佳时机含冷冻期 动态规划应该如何学习&#xff1f;-CSDN博客 本次题解参考自灵神的做法&#xff0c;大家也多多支持灵神的题解 买卖股票的最佳时机【…

Koa进阶:掌握中间件和参数校验的艺术

目录 一、首先下载依赖 二、在index.js中引入koa-parameter&#xff0c;一般挂载这个中间件时会放在注册请求体的后面 三、使用实例 四、如果跟我们所需求的参数不同&#xff0c;返回结果直接会返回422 koa-parameter一般是用来校验请求传过来的参数是否是自己所需要的的 G…

opencv(c++)----图像的读取以及显示

opencv(c)----图像的读取以及显示 imread: 作用&#xff1a;读取图像文件并将其加载到 Mat 对象中。参数&#xff1a; 第一个参数是文件路径&#xff0c;可以是相对路径或绝对路径。第二个参数是读取标志&#xff0c;比如 IMREAD_COLOR 表示以彩色模式读取图像。 返回值&#x…

git config是做什么的?

git config是做什么的&#xff1f; git config作用配置级别三种配置级别的介绍及使用&#xff0c;配置文件说明 使用说明git confi查看参数 默认/不使用这个参数 情况下 Git 使用哪个配置等级&#xff1f; 一些常见的行为查看配置信息设置配置信息删除配置信息 一些常用的配置信…

【计算机网络】【传输层】【习题】

计算机网络-传输层-习题 文章目录 10. 图 5-29 给出了 TCP 连接建立的三次握手与连接释放的四次握手过程。根据 TCP 协议的工作原理&#xff0c;请填写图 5-29 中 ①~⑧ 位置的序号值。答案技巧 注&#xff1a;本文基于《计算机网络》&#xff08;第5版&#xff09;吴功宜、吴英…

【二叉搜素树】——LeetCode二叉树问题集锦:6个实用题目和解题思路

文章目录 计算布尔二叉树的值求根节点到叶节点的数字之和二叉树剪枝验证二叉搜索树二叉搜索树中第K小的元素二叉树的所有路径 计算布尔二叉树的值 解题思路&#xff1a; 这是一个二叉树的布尔评估问题。树的每个节点包含一个值&#xff0c;其中叶子节点值为 0 或 1&#xff0…

2023年MathorCup数学建模A题量子计算机在信用评分卡组合优化中的应用解题全过程文档加程序

2023年第十三届MathorCup高校数学建模挑战赛 A题 量子计算机在信用评分卡组合优化中的应用 原题再现&#xff1a; 在银行信用卡或相关的贷款等业务中&#xff0c;对客户授信之前&#xff0c;需要先通过各种审核规则对客户的信用等级进行评定&#xff0c;通过评定后的客户才能…

嵌入式开发套件(golang版本)

1. watchdog&#xff08;软件看门狗&#xff1a;守护升级&#xff09; 2. gate&#xff08;主程序&#xff09; 3. web&#xff08;api版本 升级包&#xff09; OTA 升级流程 watchdog启动后检查守护进程gate是否正在运行&#xff0c;如果没有&#xff0c;api对比版本号&am…

解压专家 2.4.12| 多功能解压缩工具,支持密码共享、音乐播放和歌词匹配。

解压专家是一款功能强大的解压缩软件&#xff0c;提供了类似于WIFI万能钥匙的密码分享功能&#xff0c;帮助用户快速获取共享的解压密码。作为专业的解压缩工具&#xff0c;它支持多种常见和不常见的压缩包格式&#xff0c;如ZIP、RAR、7z、TAR.GZ和ISO等&#xff0c;并且还支持…

并发编程(10)——内存模型和原子操作

文章目录 十、day101. 内存模型基础1.1 对象和内存区域1.2 改动序列 2. 原子操作及其类型2.1 原子操作2.2 原子类型2.3 内存次序2.4 std::atomic_flag2.4.1 自旋锁 2.5 std::atomic&#xff1c;bool&#xff1e;2.6 std::atomic<T*>2.7 标准整数原子类型2.8 std::atomic&…