理解排序算法:冒泡排序、选择排序与归并排序

简介: 在计算机科学中,排序算法是基础且重要的概念。本文将介绍三种常见的排序方法:冒泡排序、选择排序和归并排序。我们将探讨它们的工作原理、特点和适用场景,以帮助读者更好地理解和选择合适的排序方法。

冒泡排序 

冒泡排序是一种简单的排序算法。它通过重复地遍历要排序的数列,一次比较两个元素,如果它们的顺序错误就把它们交换过来。这个过程重复进行,直到没有再需要交换的元素,此时数列已经排序完成。冒泡排序的特点是实现简单,但效率较低,特别是在处理大数据集时。

 

 

void BubbleSort(int* a, int n)//使用bool来进阶冒泡 ,当有一层不交换,就代表已经排完序,防止永久时间复杂度都是O(n^2)
{
	for (int j = 0; j < n; j++)
	{
		bool exange = false;
		for (int i = 1; i < n - j; i++)
		{
			if (a[i - 1] > a[i])
			{
				Swap(&a[i - 1], &a[i]);
				exange = true;
			}
		}
		if (exange == false)
			break;
	}

}

 冒泡排序的特性总结:

1. 冒泡排序是一种非常容易理解的排序

2. 时间复杂度:O(N^2)

3. 空间复杂度:O(1)

4. 稳定性:稳定

选择排序

 

选择排序是一种简单直观的排序算法,广泛应用于计算机科学教学和一些基础编程任务中。本文将详细介绍选择排序的工作原理、具体实现步骤、算法特点以及适用场景,帮助读者更好地理解和使用这种排序方法。

一、选择排序的工作原理

选择排序算法的基本思想是:

首先在未排序的序列中找到最小(或最大)的元素,然后将其放置在序列的起始位置,接着再从剩余未排序的元素中继续寻找最小(或最大)的元素,然后放到已排序序列的末尾。这个过程一直重复,直到所有元素都被排序。

二、选择排序的步骤

  1. 从未排序的序列中找到最小(或最大)的元素。
  2. 将找到的最小(或最大)元素与序列的第一个元素交换位置(如果最小元素就是第一个元素,则自身和自身交换)。
  3. 重复上述过程,每次交换后,排序序列的长度就增加一个元素,而未排序序列的长度减少一个元素。
  4. 当未排序序列的长度减少到0时,排序就完成了。

三、选择排序的特点

  • 简单直观:选择排序的算法逻辑简单,易于理解和实现。
  • 时间复杂度:在最好、最坏和平均情况下,时间复杂度都是O(n²)。
  • 不稳定排序:选择排序不是稳定的排序算法,相等的元素可能在排序过程中改变其原有的顺序。
  • 原地排序:选择排序不需要额外的存储空间,它是一种原地排序算法。

四、选择排序的适用场景

由于选择排序的效率较低,它通常不适用于数据量较大的排序任务。然而,在数据量较小或者对算法的时间复杂度要求不高的场景中,选择排序由于其实现的简单性,仍然是一个不错的选择。特别是在教学和学习算法的过程中,选择排序是理解基本排序概念的良好起点。

总结: 选择排序以其简单直观的特点,在编程教学和小规模数据处理中有着一席之地。虽然在处理大量数据时效率不高,但它作为基础排序算法,对于理解更复杂的排序技术提供了重要的基础。

void SelectSort(int* a, int n)
{
	int begin = 0;
	int end = n - 1;
	while (begin < end)
	{
		int mini = begin; 
		int max = begin;
		for (int i = begin+1; i <= end; ++i)
		{
			if (a[i] < a[mini])
			{
				mini = i;
			}
			if (a[i] > a[max])
			{
				max = i;
			}
		}
		Swap(&a[begin], &a[mini]);
		if (max == begin)
		{
			max = mini;
		}
		Swap(&a[end], &a[max]);
		begin++;
		end--;
	}
	
}

 归并排序

 

 

简介: 归并排序是一种高效且稳定的排序算法,通过分治法实现对数据的高效排序。本文旨在详细介绍归并排序的工作原理、具体实现步骤、算法的特点以及适用场景,帮助读者深入理解并有效地应用这种排序方法。

一、归并排序的工作原理

归并排序的核心思想是将两个有序的数组合并成一个更大的有序数组。具体来说,它将原始数组分成两半,分别对这两半进行排序,然后将排序好的两个半部分合并在一起。这个过程是递归进行的,最终达到完全排序的目的。

二、归并排序的步骤

  1. 分解:将原始数组分解成两个大小大致相等的子数组。
  2. 解决:递归地对这两个子数组进行归并排序。
  3. 合并:将两个已排序的子数组合并成一个单一的已排序数组。

三、归并排序的特点

  • 高效稳定:归并排序在最坏、最好和平均情况下的时间复杂度均为O(n log n),是一种非常高效的排序算法。同时,它也是一种稳定的排序,即相等的元素在排序后会保持其原有顺序。
  • 分治策略:归并排序是分治法思想的典型应用,通过将问题分解为可管理的子问题来简化复杂性。
  • 额外空间需求:归并排序需要额外的空间来存储临时数组,这是它的一个缺点。

四、归并排序的适用场景

归并排序非常适合处理大数据集,特别是在数据无法一次性装入内存时。由于其稳定性和高效性,它广泛应用于数据库和文件系统等领域,是处理大规模数据排序的理想选择。

总结: 归并排序以其高效、稳定的特性,在大数据处理和复杂系统中占有重要位置。尽管需要额外的存储空间,但其优越的性能使其成为解决复杂排序问题的强大工具。

void _MergeSort(int* a, int begin, int end, int* tmp)//每次需要开辟数组且要对数组进行分区,所以调用子函数
{
	int mid = (begin + end) / 2;
	//[begin , mid] [mid +1, end]
	_MergeSort(a, begin, mid, tmp);
	_MergeSort(a, mid + 1, end, tmp);
	//后序逻辑 归并
	int begin1 = begin, end1 = mid;
	int begin2 = mid + 1, end2 = end;
	int i = begin;
	
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (a[begin1] < a[begin2])
		{
			tmp[i++] = a[begin1++];
		}
		else
		{
			tmp[i++] = a[begin2++];
		}
	}
		while (begin1 <= end1)
		{
			tmp[i++] = a[begin1++];
		}
		while (begin2 <= end2)
		{
			tmp[i++] = a[begin2++];
		}

		memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));

}
void MergeSort(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc fail");
		return;
	}
	_MergeSort(a, 0, n - 1, tmp);
	free(tmp);
}

 

总结: 在本系列博客文章中,我们深入探讨了三种经典的排序算法:冒泡排序、选择排序和归并排序。每种排序方法都有其独特的工作原理和应用场景,从简单直观的冒泡排序和选择排序到高效稳定的归并排序,这些算法为我们提供了不同的数据组织和处理方式。

冒泡排序以其实现的简单性和直观性而闻名,适合用于小数据集和教学目的。选择排序,尽管时间复杂度较高,但在需要减少交换次数的情况下仍是一个不错的选择。归并排序则以其高效率和稳定性在大数据处理中发挥重要作用,尤其适用于无法一次性装入内存的大规模数据集。

理解这些排序算法的原理和特点对于任何涉及数据处理的程序员来说都是至关重要的。它们不仅是计算机科学的基础,也是解决实际问题的强大工具。我们希望这些文章能够帮助读者更好地理解这些基本算法,并在适当的场合中作出恰当的选择。

感谢您阅读本系列关于排序算法的探索。我们期待在未来的文章中继续为您提供更多有价值的技术洞见和实用建议。

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

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

相关文章

cs环境部署

配置搭建cs工具 两种方式 cs工具 》狐狸工具箱,微信上搜索 或者cs - OneDrive (sharepoint.com)提取密码www.ddosi.org 需要云服务器&#xff08;个人猜测如果是靶场的话&#xff0c;可以采用一台所有主机都能访问的主机作为服务端配置&#xff09; 非docker方式搭建 将c…

ue5材质预览界面ue 变黑

发现在5.2和5.1上都有这个bug 原因是开了ray tracing引起的&#xff0c;这个bug真是长时间存在&#xff0c;类似的bug还包括草地上奇怪的影子和地形上的影子等等 解决方法也很简单&#xff0c;就是关闭光追&#xff08;不是…… 就是关闭预览&#xff0c;在材质界面preview sc…

10基于matlab的悬臂梁四节点/八节点四边形单元有限元编程(平面单元)

悬臂梁&#xff0c;有限元编程。基于matlab的悬臂梁四节点/八节点四边形单元有限元编程&#xff08;平面单元&#xff09;&#xff0c;程序有详细注解&#xff0c;可根据需要更改参数&#xff0c;包括长度、截面宽度和高度、密度、泊松比、均布力、集中力、单元数量等。需要就拍…

【算法】递归、搜索与回溯算法

文章目录 一. 名词解释1. 递归1.1 什么是递归&#xff1f;1.2 为什么会用到递归&#xff1f;1.3 如何理解递归&#xff1f;1.4 如何写好一个递归&#xff1f; 2. 遍历和搜索3. 回溯和剪枝 二. 递归系列专题1. 汉诺塔问题2. 合并两个有序链表3. 反转链表4. 两两交换链表中的节点…

关于Anaconda的安装和环境部署(此章专为新手制定)

目录 Anaconda简介 一、软件下载&#xff08;地址&#x1f447;&#xff09; 2&#xff1a;点击下载 3&#xff1a;版本选择&#xff1a; 4&#xff1a;Anaconda的安装包就下载完成了 2&#xff1a;恭喜你&#xff0c;看到这里已经完成安装了 三、部署环境 1&#xff1…

什么是 AWS IAM?如何使用 IAM 数据库身份验证连接到 Amazon RDS(上)

驾驭云服务的安全环境可能很复杂&#xff0c;但 AWS IAM 为安全访问管理提供了强大的框架。在本文中&#xff0c;我们将探讨什么是 AWS Identity and Access Management (IAM) 以及它如何增强安全性。我们还将提供有关使用 IAM 连接到 Amazon Relational Database Service (RDS…

C++类模板分文件编写

问题&#xff1a; 类模板中成员函数创建时机是在调用阶段&#xff0c;导致分文件编写时链接不到 解决&#xff1a; 解决方式最常用的&#xff1a;将声明和实现写到同一个文件&#xff0c;并更改后缀名为.hpp&#xff0c;hpp是约定的名称&#xff0c;并不是强制的

Windows/Linux混合刻录后,Windows显示空白盘解决思路

概述 因为工作环境问题&#xff0c;需要在Windows和Linux之间来回光盘刻录&#xff0c;没有多余光盘的时候经常多次使用&#xff0c;同一光盘在Windows刻录文件到Linux&#xff0c;然后从Linux刻录文件到Windows&#xff0c;Windows用“类似U盘”格式化的光盘&#xff0c;在Wi…

洛谷 P8802 [蓝桥杯 2022 国 B] 出差

文章目录 [蓝桥杯 2022 国 B] 出差题目链接题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1 提示 思路解析CODE [蓝桥杯 2022 国 B] 出差 题目链接 https://www.luogu.com.cn/problem/P8802 题目描述 A \mathrm{A} A 国有 N N N 个城市&#xff0c;编号为 1 … N …

三天精通Selenium Web 自动化 - Selenium(Java)环境搭建

1 下载JDK JDK下载地址&#xff1a;http://www.oracle.com/technetwork/java/javase/downloads/jdk8-downloads-2133151.html 2 安装和配置JDK 安装目录尽量不要有空格 D:\Java\jdk1.8.0_91; D:\Java\jre8设置环境变量&#xff1a; “我的电脑”->右键->“属性”->…

LeetCode刷题日志-73矩阵置零

思路一&#xff1a; 用一个同样大小的矩阵记录0的位置&#xff0c;然后遍历矩阵置0&#xff0c; 空间复杂度为O&#xff08;mn&#xff09; class Solution {public void setZeroes(int[][] matrix) {int [][] matrix_new new int[matrix.length][matrix[0].length];for(int …

postgresql自带指令命令系列三

目录 简介 bin目录 28.pg_verifybackup 29.pg_waldump 30.postgres 31.postmaster -> postgres 32.psql 33.reindexdb 34.vacuumdb 35.vacuumlo 总结&#xff1a; 简介 在安装postgresql数据库的时候会需要设置一个关于postgresql数据库的PATH变量 export PATH/…

1845_emacs中一个中文乱码问题分析解决

Grey 全部学习内容汇总&#xff1a;GitHub - GreyZhang/editors_skills: Summary for some common editor skills I used. 1845_emacs中一个中文乱码问题分析解决 曾经有一次放弃过我自己的emacs配置&#xff0c;一个原因就是中文的支持。感觉我的配置跟其他人的配置显得有些…

优雅玩转实验室服务器(一)登录服务器

这篇文章更加偏向于使用python程序进行研究的朋友们 原料 Windows主机实验室Linux服务器&#xff08;可以访问互联网&#xff09;一点点耐心 step.0 windows terminal is all you need 别跟我说什么putty&#xff0c;什么winscp&#xff0c;我就是单推Win11自带的软件——win…

deepface:实现人脸的识别和分析

deepface介绍 deepface能够实现的功能 人脸检测&#xff1a;deepface 可以在图像中检测出人脸的位置&#xff0c;为后续的人脸识别任务提供基础。 人脸对齐&#xff1a;为了提高识别准确性&#xff0c;deepface 会将检测到的人脸进行对齐操作&#xff0c;消除姿态、光照和表…

Python 进阶(十六):二进制和ASCII码的转换(binascii 模块)

大家好&#xff0c;我是水滴~~ 本文详细介绍了Python中的binascii模块及其使用方法。通过binascii模块&#xff0c;我们可以方便地进行二进制和ASCII字符串之间的转换操作。文章中包含大量的示例代码&#xff0c;希望能够帮助新手同学快速入门。 《Python入门核心技术》专栏总…

【unity】【WebRTC】从0开始创建一个Unity远程媒体流app-设置输入设备

【项目源码】 包括本篇需要的脚本都打包在项目源码中,可以通过下面链接下载: 【背景】 目前我们能投射到远端浏览器(或者任何其它Peer)的媒体流只有默认的MainCamera画面,其实我们还可以通过配置输入来传输操作输入信息,比如键鼠等。 【追加input processing组件】 …

在AWS Lambda中使用FFmpeg处理m3u8视频流

大纲 1 部署有FFmpeg功能的Lambda环境1.1 部署层1.2 部署代码1.2.1 FFmpeg指令1.2.2 代码 2 配置Lambda角色权限2.1 选择角色类型2.2 设置权限2.3 保存角色2.4 绑定角色 参考文献 在直播里领域&#xff0c;我们经常需要对视频流进行处理。FFmpeg则是该领域中处理的利器。这篇文…

Spring 面向切面编程(AOP)

一、aop介绍 &#xff08;一&#xff09;前言 一般的后端开发流程是纵向开发&#xff0c;就是controller&#xff08;控制层&#xff09;->service&#xff08;业务层&#xff09;->mapper&#xff08;数据持久层&#xff09;&#xff0c;Spring采用动态代理技术可以在…

关于mars3d通过zIndex参数实现控制图层层级叠加效果说明

问题&#xff1a; 1.项目中使用了GraphicLayer、GeoJSONLayer、ArcGISLayer&#xff0c;期望mars3d能够提供方法进行设置每个图层的zindex顺序 解决方案&#xff1a; 1.首先在mars3d的开发教程中查询三个Layer属于的图层类型&#xff0c;GraphicLayer、GeoJSONLayer均属于矢…