首页 > 编程语言 >算法与数据结构——简单排序算法(选择、冒泡、插入)

算法与数据结构——简单排序算法(选择、冒泡、插入)

时间:2024-09-26 10:36:28浏览次数:7  
标签:数据结构 nums 复杂度 元素 算法 冒泡 数组 排序 插入排序

简单排序算法

时间复杂度均为O(n2)

选择排序

选择排序(selection sort)的工作原理非常简单:开启一个循环,每轮从未排序区间选择最小的元素,将其放到已排序的区间的末尾。

算法流程

设数组长度为n,选择排序的算法流程如下。

  1. 初识状态下,所有元素未排序,即未排序(索引)区间为[1, n-1]。
  2. 选取区间[0,n-1]中的最小元素,将其与索引0处的元素交换。完成后,数组前1一个元素已排序。
  3. 选取区间[1,n-1]中的最小元素,将其与索引1处的元素交换,完成后,数组前2个元素已排序。
  4. 以此类推。经过n - 1轮选择与交换后,数组前 n-1个元素已排序。
  5. 仅剩的一个元素必定是最大元素,无需排序,因此数组排序完成。
/*选择排序*/
void selectionSort(vector<int> &nums){
	int n = nums.size();
	// 外循环:未排序区间为[i , n-1]
	for (int i = 0; i < n - 1; ++i){
		int  k = i;
		// 内循环:找到未排序区间的最小元素
		for (int j = i; j < n; ++j){
			if (nums[j] < nums[k])
				k = j;
		}
		// 将该最小元素与未排序区间的首个元素交换
		swap(nums[i], nums[k]);
	}
}

算法特性

相关文章

  • 操作系统-页面置换算法
    简介期末考试中常考的页面置换算法可能有三种,分别是先进先出(FIFO),最佳置换(OPT)和最久未使用(LRU)本篇文章会用一道例题来讲解这三种算法的思路和解题过程;题目假设有这样一个操作系统,其内存中有3个空闲页面框(题目也有可能是描述成M3,M是Memory的简写)。进程依次请求页面号为以下序......
  • 强联通分量——Tarjan算法
    Tarjan算法详解参考文章:强连通分量Tarjan算法是一种用于寻找有向图中强联通分量(StronglyConnectedComponents,SCCs)的算法。它是由RobertTarjan在1972年提出的,基于深度优先搜索(DFS)和栈的数据结构。基本概念强联通分量:在一个有向图中,如果一组节点中任意两个节点都可以互相......
  • Tarjan算法缩点
    Tarjan算法缩点一.Tarjan算法缩点详解在图论中,缩点是指将有向图中的强联通分量(SCCs)缩成单个节点,从而得到一个更简单的图结构,称为缩点图或SCC图。Tarjan算法不仅可以用来寻找强联通分量,还可以用来进行缩点操作。基本概念强联通分量:在一个有向图中,如果一组节点中任意两个节点都......
  • 算法-复杂度分析
    复杂度分析不依赖具体的执行环境不用具体的测试数据在算法实现前,我们在脑海就可以评估算法的性能评估一个算法的性能:本质上就是评估这个算法代码执行的时间N为数据规模 大O复杂度表示法表示算法的性能,通常看最差的情况,算法运行的上界O(n) T=5n+2常数不重要,复杂......
  • 【算法】C++KMP算法的简洁实现
    目录简介next数组匹配完整代码简介对于朴素的字符串匹配算法,如果想在主串中寻找到第一次出现子串的位置,需要依次枚举主串中的每一个位置作为起始位置进行匹配尝试,如果主串中存在许多与子串相似结构的部分,那么朴素算法会进行大量的无用枚举,时间复杂度非常之高。KMP算法......
  • 【算法题】63. 不同路径 II-力扣(LeetCode)-”如果起点有障碍物,那么便到不了终点“
    【算法题】63.不同路径II-力扣(LeetCode)-”如果起点有障碍物,那么便到不了终点“1.题目下方是力扣官方题目的地址63.不同路径II一个机器人位于一个mxn网格的左上角(起始点在下图中标记为“Start”)。机器人每次只能向下或者向右移动一步。机器人试图达到网格......
  • 【算法】笔试题记录
    哇今天做了道特别有意思的题。编程就给了两道,第一题特别简单,a、b两个数,每次选其中一个数*2,这样操作两次,问最后得到的两数之和的期望值是多少。简单吧?因为每次选择都有两种可能性,操作两次后就会有四种可能的结果(22)。其中有两个结果是重复的(2a,2b),剩下两个分别是(a,4b)和(4a,......
  • matlab实验三(冒泡排序,sort函数,斜抛运动与绘图,循环确定(银行存利息))
    1.在MATLAB中使用循环结构对给定的数列A=[33,689,-705,2024,-6,29]进行升序排序。(注意:不可以使用任何MATLAB自带的排序函数直接操作。)%给定数列A=[33,689,-705,2024,-6,29];%获取数列长度n=length(A);%冒泡排序算法fori=1:n-1forj=1:n-i......
  • 【鸟类识别系统】+计算机毕设项目+卷积神经网络算法+人工智能+深度学习+模型训练+Pyth
    一、介绍鸟类识别系统。本系统采用Python作为主要开发语言,通过使用加利福利亚大学开源的200种鸟类图像作为数据集。使用TensorFlow搭建ResNet50卷积神经网络算法模型,然后进行模型的迭代训练,得到一个识别精度较高的模型,然后在保存为本地的H5格式文件。在使用Django开发Web网页端操作......
  • 【动物识别系统】计算机毕设项目案例+Python卷积神经网络算法+模型训练+人工智能+深度
    一、介绍动物识别系统。本项目以Python作为主要编程语言,并基于TensorFlow搭建ResNet50卷积神经网络算法模型,通过收集4种常见的动物图像数据集(猫、狗、鸡、马)然后进行模型训练,得到一个识别精度较高的模型文件,然后保存为本地格式的H5格式文件。再基于Django开发Web网页端操作界面,实现......