【ARM 嵌入式 C 入门及渐进 10 -- 冒泡排序 选择排序 插入排序 快速排序 归并排序 堆排序 比较介绍】

文章目录

    • 排序算法小结
    • 排序算法C实现
    • 排序方法的稳定性

在这里插入图片描述

排序算法小结

C语言中常用的排序算法包括冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序。下面我们来一一介绍:

  • 冒泡排序(Bubble Sort):冒泡排序是通过比较相邻元素的大小进行排序。如果当前元素比下一个元素大,就交换它们两个的位置。重复这个过程直到最后,最大的元素就会“冒”到数组的最后。然后再从头开始重复这个过程,但是最后一个元素不再考虑。这个过程会一直进行,直到没有元素需要交换,也就是整个数组已经排序完成。冒泡排序的时间复杂度是O(n^2)
  • 选择排序(Selection Sort):选择排序是每次从未排序的元素中选择最小(或最大)的元素放到未排序元素的开始位置,直到所有元素都已排序。选择排序的时间复杂度也是O(n^2)
  • 插入排序(Insertion Sort):插入排序的思路是将未排序的元素依次插入到已排序元素的适当位置。开始时,第一个元素被认为已排序,然后将第二个元素和它比较,决定第二个元素在已排序元素中的位置,然后再将第三个元素和已排序的元素比较,依次进行。插入排序的时间复杂度是O(n^2)
  • 快速排序(Quick Sort):快速排序是一种使用分治策略的排序算法。它的基本思想是选择一个基准元素,将数组分为两部分,一部分的元素都比基准元素小,另一部分的元素都比基准元素大。然后对这两部分再分别进行快速排序。快速排序最坏的时间复杂度是O(n^2),但是在平均情况下,快速排序的时间复杂度是O(n log n)
  • 归并排序(Merge Sort):归并排序也是一种使用分治策略的排序算法。它的基本思想是将数组分为两半,分别对它们进行归并排序,然后将两个已排序的子数组合并成一个完整的已排序数组。归并排序的时间复杂度是O(n log n)
  • 堆排序(Heap Sort):堆排序是基于二叉堆的一种排序方法。首先将数组构建成一个最大堆或最小堆,然后依次移除堆顶的元素,并调整堆以保持堆的性质,直到堆为空,此时数组已排序。堆排序的时间复杂度是O(n log n)

总的来说,这些排序算法各有各的优点和适用场景,例如,冒泡排序、选择排序和插入排序适用于小规模数据或者部分有序数据,而快速排序、归并排序和堆排序通常适用于大规模数据排序。

排序算法C实现

#include <stdio.h>//冒泡排序:
void bubbleSort(int arr[], int n)
{int i, j;for (i = 0; i < n-1; i++) {for (j = 0; j < n-i-1; j++) {if (arr[j] > arr[j+1]) {int temp = arr[j];arr[j] = arr[j+1];arr[j+1] = temp;}}}
}
//选择排序:
void selectionSort(int arr[], int n)
{int i, j, minIndex, temp;for (i = 0; i < n-1; i++) {minIndex = i;for (j = i+1; j < n; j++) if (arr[j] < arr[minIndex]) {minIndex = j;}temp = arr[minIndex];arr[minIndex] = arr[i];arr[i] = temp;}
}
//插入排序:
void insertionSort(int arr[], int n)
{int i, key, j;for (i = 1; i < n; i++) {key = arr[i];j = i - 1;while (j >= 0 && arr[j] > key) {arr[j + 1] = arr[j];j = j - 1;}arr[j + 1] = key;}
}
//快速排序:
int partition(int arr[], int low, int high)
{int pivot = arr[high];int i = (low - 1);for (int j = low; j <= high- 1; j++) {if (arr[j] <= pivot) {i++;swap(&arr[i], &arr[j]);}}swap(&arr[i + 1], &arr[high]);return (i + 1);
}
void quickSort(int arr[], int low, int high)
{if (low < high) {int pi = partition(arr, low, high);quickSort(arr, low, pi - 1);quickSort(arr, pi + 1, high);}
}
//归并排序:
void merge(int arr[], int l, int m, int r)
{int i, j, k;int n1 = m - l + 1;int n2 = r - m;int L[n1], R[n2];for (i = 0; i < n1; i++) {L[i] = arr[l + i];}for (j = 0; j < n2; j++) {R[j] = arr[m + 1+ j];}i = 0;j = 0;k = l;while (i < n1 && j < n2) {if (L[i] <= R[j]) {arr[k] = L[i];i++;} else {arr[k] = R[j];j++;}k++;}while (i < n1) {arr[k] = L[i];i++;k++;}while (j < n2) {arr[k] = R[j];j++;k++;}
}
void mergeSort(int arr[], int l, int r)
{if (l < r) {int m = l+(r-l)/2;mergeSort(arr, l, m);mergeSort(arr, m+1, r);merge(arr, l, m, r);}
}
//堆排序:
void heapify(int arr[], int n, int i)
{int largest = i;int l = 2*i + 1;int r = 2*i + 2;if (l < n && arr[l] > arr[largest]) {largest = l;}if (r < n && arr[r] > arr[largest]) {largest = r;}if (largest != i) {swap(&arr[i], &arr[largest]);heapify(arr, n, largest);}
}
void heapSort(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[0], &arr[i]);heapify(arr, i, 0);}
}

排序方法的稳定性

用某排序方法对一个关键码序列进行递增排序时,对于其中关键码相同的元素,若该方法可保证在排序前后这些元素的相对位置不变,则称该排序方法是稳定的。
在这里插入图片描述

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

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

相关文章

android 8.1 disable unsupported sensor

如果device不支持某种sensor,可以在android/frameworks/base/core/java/android/hardware/SystemSensorManager.java里将其disabled掉。以disable proximity sensor为例。 public SystemSensorManager(Context context, Looper mainLooper) {synchronized(sLock) {if (!sNativ…

MWeb Pro for Mac:博客生成编辑器,助力你的创作之旅

在当今数字化时代&#xff0c;博客已经成为了许多人记录生活、分享知识和表达观点的重要渠道。而要打造一个专业、美观且易于管理的博客&#xff0c;选择一款强大的博客生成编辑器至关重要。今天&#xff0c;我向大家推荐一款备受好评的Mac软件——MWeb Pro。 MWeb Pro是一款专…

flutter深研

https://www.douyin.com/video/7020336319058627853 关闭系统风扇 在 Windows 操作系统上安装和配置 Flutter 开发环境 - Flutter 中文文档 - Flutter 中文开发者网站 - Flutter 下载Git - Downloading Package 推荐使用迅雷下载 系统配置要求 要想安装和运行 Flutter&#xf…

使用FastAPI部署Ultralytics YOLOv5模型

YOLO是You Only Look Once(你只看一次)的缩写&#xff0c;它具有识别图像中的物体的非凡能力&#xff0c;在日常应用中会经常被使用。所以在本文中&#xff0c;我们将介绍如何使用FastAPI的集成YOLOv5&#xff0c;这样我们可以将YOLOv5做为API对外提供服务。 Python有几个web框…

如何将 ruby 打包类似于jdk在另一台相同架构的机器上面开箱即用

需求 目前工作中使用到了ruby作为java 项目的中转语言&#xff0c;但是部署ruby的时候由于环境的不同会出现安装依赖包失败的问题&#xff0c;如何找到一种开箱即用的方式类似于java 中的jdk内置jvm这种方式 解决 TruffleRuby 完美解决问题&#xff0c;TruffleRuby 是使用 T…

基于STC系列单片机实现外部中断0控制按键调节定时器0产生PWM(脉宽调制)的功能

#define uchar unsigned char//自定义无符号字符型为uchar #define uint unsigned int//自定义无符号整数型为uint sbit PwmOut P1^0;//位定义脉宽调制输出为单片机P1.0脚 uchar PwmTimeCount;//声明脉宽调制时间计数变量 uchar PwmDutyCycle;//声明脉宽调制占空比变量 void Ti…

Apache服务的搭建与配置(超详细版)

前言 Apache是一种常见的Web服务器软件&#xff0c;广泛用于Linux和其他UNIX操作系统上。它是自由软件&#xff0c;可以通过开放源代码的方式进行自由分发和修改。Apache提供了处理静态和动态内容的能力&#xff0c;而且还支持多种编程语言和脚本&#xff0c;如PHP、Python和P…

python数据可视化

内容主要介绍了python模块matplotlib即seaborn数据可视化 matplotlib模块通过import matplotlib.pyplot as plt生成图形&#xff0c;如生成图形没展示&#xff0c;可调用plt.show()方法展示图形&#xff1b; 对于颜色属性设置&#xff0c;既可以使用十六进制颜色表达(#7777aa…

cdrx8和2020哪个版本更好用?有什么区别

经过多年的发展&#xff0c;cdr推出了很多优秀的版本&#xff0c;并顺应时代的发展更新了多项功能。随着cdr推出的软件版本增多&#xff0c;小伙伴们可选择的产品也在增多&#xff0c;那么该怎么选择呢&#xff1f;本文会给大家介绍cdrx8和2020的区别&#xff0c;CDRX8和2020哪…

Pytorch 猫狗识别案例

猫狗识别数据集https://download.csdn.net/download/Victor_Li_/88483483?spm1001.2014.3001.5501 训练集图片路径 测试集图片路径 训练代码如下 import torch import torchvision import matplotlib.pyplot as plt import torchvision.models as models import torch.nn as…

基于静电放电算法的无人机航迹规划-附代码

基于静电放电算法的无人机航迹规划 文章目录 基于静电放电算法的无人机航迹规划1.静电放电搜索算法2.无人机飞行环境建模3.无人机航迹规划建模4.实验结果4.1地图创建4.2 航迹规划 5.参考文献6.Matlab代码 摘要&#xff1a;本文主要介绍利用静电放电算法来优化无人机航迹规划。 …

0基础学习PyFlink——用户自定义函数之UDF

大纲 标量函数入参并非表中一行&#xff08;Row&#xff09;入参是表中一行&#xff08;Row&#xff09;alias PyFlink中关于用户定义方法有&#xff1a; UDF&#xff1a;用户自定义函数。UDTF&#xff1a;用户自定义表值函数。UDAF&#xff1a;用户自定义聚合函数。UDTAF&…

1400*C. Team(模拟构造)

Problem - 401C - Codeforces 解析&#xff1a; 因为0不能相邻&#xff0c;所以0之间最少 n-1 个位置&#xff0c;最多 n1 个位置&#xff0c;如果 m<n-1显然不符题意。 并且1最多连续两个&#xff0c;所以 m>2*n2 同样不符题意。 其余情况构造即可 #include<bits/st…

【嵌入式】【GIT】如何迁移老的GIF到新的仓库时使用LFS功能并保持LOG不变

一、正常迁移流程 假设有仓库 ssh://old/buildroot-201902 需要迁移到新的仓库 ssh://old/buildroot-201902时,我们可以使用以下命令来完成: # 下载老的仓库 git clone ssh://old/buildroot-201902 # 向新的仓库上传所有的tags git push ssh://new/buildroot-201902 --tag…

【网络安全】Seeker内网穿透追踪定位

Seeker追踪定位对方精确位置 前言一、kali安装二、seeker定位1、ngrok平台注册2、获取一次性邮箱地址3、ngrok平台登录4、ngrok下载5、ngrok令牌授权6、seeker下载7、运行seeker定位8、运行隧道开启监听9、伪装链接10、用户点击&#xff08;获取定位成功&#xff09;11、利用经…

Rust-虽然9天过去了,结果是没有结果(Docker容器的端口映射问题)

​ 这篇文章收录于Rust 实战专栏。这个专栏中的相关代码来自于我开发的笔记系统。它启动于是2023年的9月14日。相关技术栈目前包括&#xff1a;Rust&#xff0c;Javascript。关注我&#xff0c;我会通过这个项目的开发给大家带来相关实战技术的分享。 前言 上上周了吧&#xf…

机器学习(六)构建机器学习模型

1.9构建机器学习模型 我们使用机器学习预测模型的工作流程讲解机器学习系统整套处理过程。 整个过程包括了数据预处理、模型学习、模型验证及模型预测。其中数据预处理包含了对数据的基本处理&#xff0c;包括特征抽取及缩放、特征选择、特征降维和特征抽样&#xff1b;我们将…

Linux的简介和环境搭建

简介 Linux是一套免费使用和自由传播的类Unix操作系统&#xff0c;是一个基于POSIX和Unix的多用户、多任务、支持多线程和多CPU的操作系统。它能运行主要的Unix工具软件、应用程序和网络协议。它支持32位和64位硬件。Linux继承了Unix以网络为核心的设计思想&#xff0c;是一个…

Python构造代理IP池提高访问量

目录 前言 一、代理IP是什么 二、代理IP池是什么 三、如何构建代理 IP 池 1. 从网上获取代理 IP 地址 2. 对 IP 地址进行筛选 3. 使用筛选出来的 IP 地址进行数据的爬取 四、总结 前言 爬虫程序是批量获取互联网上的信息的重要工具&#xff0c;在访问目标网站时需要频…

#stm32整理(一)flash读写

以这篇未开始我将进行stm32学习整理为期一个月左右完成stm32知识学习整理内容顺序没有一定之规写到哪想到哪想到哪写到哪&#xff0c;主要是扫除自己知识上的盲区完成一些基本外设操作。 以stm32f07为例子进行flash读写操作 stm32flash简介 参考资料正点原子和野火开发手册 …