排序算法之选择排序篇

embedded/2024/11/28 22:03:09/

在这里插入图片描述

思想:

每次从未排序的部分找出最小的元素,将其放到已排序部分的末尾

从数据结构中找到最小值,放到第一位,放到最前面,之后再从剩下的元素中找出第二小的值放到第二位,以此类推。

实现思路:

  1. 遍历数据结构,找到最小值,放到第一位
  2. 从剩下的部分找到第二小的值,放到第二位
  3. 重复上述过程,直到整个排序完成

视频实现:

文字描述如上,以下是选择排序的视频全过程

选择排序全过程

代码实现:

接下来是选择排序的代码实现:

java"> //传入一个数组,用来进行排序  
public static void SelectionSort(int[] arr){  //外层循环是用来控制排序的层次的  for(int  i = 0 ; i< arr.length-1; i++){  int minIndex = i;  //内层循环是为了在没有进行排序的元素中找到最小的元素  for(int j = i+1 ; j< arr.length;j++){  if(arr[j]  < arr[minIndex]){  minIndex = j;  }  }  int temp = arr[i];  arr[i] = arr[minIndex];  arr[minIndex] = temp;  }  
}

外层循环是用来控制排序的层次的 ,所以如下:

for(int i = 0; i < arr.length-1; i++)

内层循环的目的是为了在没有进行排序的元素中找到最小的元素

for(int j = i-1; j < arr.length; j++)

时间复杂度分析:

啊~ 选择排序的时间复杂度嘛,哼哼,这个问题可是很有意思的哦!让我给你详细分析一下,保证你完全明白!(。•̀ᴗ•́。)

选择排序时间复杂度分析:

选择排序的基本思想就是 每次从未排序的部分找出最小的元素,将其放到已排序部分的末尾。它的核心是通过两层循环来完成排序:外层循环控制排序轮次,内层循环负责找最小值。

1. 外层循环的复杂度

外层循环从数组的第一个元素开始,到倒数第二个元素为止。假设数组的长度为 n,那么外层循环的次数就是 n - 1。所以外层循环的复杂度是 O(n)。

2. 内层循环的复杂度

对于每次外层循环,内层循环会从外层循环当前位置之后的元素开始,遍历剩下的所有元素。具体来说:

  • 第一次外层循环:内层循环会从第 1 个元素开始遍历到最后一个元素,总共遍历 n-1 次。
  • 第二次外层循环:内层循环会从第 2 个元素开始遍历到最后一个元素,总共遍历 n-2 次。
  • 第三次外层循环:内层循环会从第 3 个元素开始遍历到最后一个元素,总共遍历 n-3 次。
  • 以此类推……直到最后一次外层循环只遍历一个元素。

所以内层循环的总遍历次数就是:
[
(n-1) + (n-2) + (n-3) + \dots + 1
]
这个和是一个等差数列,我们可以使用等差数列求和公式:
[
S = \frac{n(n-1)}{2}
]
所以内层循环的复杂度是 O(n²)。

3. 总时间复杂度

选择排序的总时间复杂度是外层循环和内层循环的复杂度之和。

  • 外层循环:O(n)
  • 内层循环:O(n²)

因此,选择排序的总时间复杂度是 O(n²)

4. 空间复杂度

选择排序是一个 原地算法>排序算法,意味着它只需要常数级别的额外空间。只用了一个变量 minIndex 来记录最小值的位置,空间复杂度就是 O(1)

总结:

  • 时间复杂度:选择排序的时间复杂度是 O(n²),因为它有两层嵌套循环。
  • 空间复杂度:空间复杂度是 O(1),因为它是一个原地排序,不需要额外的空间。

为什么时间复杂度是 O(n²)?

  • 选择排序每一次外层循环都会执行一次内层循环,内层循环的次数逐步递减,但总体来说,它的时间复杂度是平方级的(O(n²))。

http://www.ppmy.cn/embedded/141272.html

相关文章

蓝牙循环搜索并连接. Android辅助功能以及锁的灵活运用

现在需要实现个工具, android设备要不断自动的去搜索附近蓝牙打印机,然后进行配对,连接打印数据. 根据测试发现有两个技术难点 第一个是一些设备链接打印机后,会弹出进行配对的对话框,有些设备还会让你输入配对密码进行配对,如果用人工去点击,就不是自动去搜索配对,并打印了…

黑马程序员Java项目实战《苍穹外卖》Day01

苍穹外卖-day01 课程内容 软件开发整体介绍苍穹外卖项目介绍开发环境搭建导入接口文档Swagger 项目整体效果展示&#xff1a; ​ 管理端-外卖商家使用 ​ 用户端-点餐用户使用 当我们完成该项目的学习&#xff0c;可以培养以下能力&#xff1a; 1. 软件开发整体介绍 作为一…

在 Spring Boot 中构造 API 响应的最佳实践

在平时的开发和项目中&#xff0c;我们一定会涉及到接口对接的功能&#xff0c;由于不同开发人员的编码习惯不同&#xff0c;API报文在项目中通常是"百花齐放"的。 不但增加工作难度&#xff0c;往往也是扯皮的大头&#xff0c;如果能统一报文格式&#xff0c;不但能…

【设计模式】【行为型模式(Behavioral Patterns)】之责任链模式(Chain of Responsibility Pattern)

1. 设计模式原理说明 责任链模式&#xff08;Chain of Responsibility Pattern&#xff09; 是一种行为设计模式&#xff0c;它允许你将请求沿着处理者链进行发送。每个处理者都可以处理请求&#xff0c;或者将其传递给链上的下一个处理者。这种模式使得多个对象都有机会处理请…

67 mysql 的 间隙锁

前言 我们这里主要是 来看一下 mysql 中的 间隙锁 间隙锁 主要存在的地方一般就是在 查询主键查询不到, 索引查询查询不到 的场景 然后 我们这里来调试一下 这里的整个流程, 间隙锁的加锁 以及 间隙锁的使用, 以及 间隙锁的释放 从逻辑上来说 间隙锁 锁定的是一个区间, 按照…

mysql-分析并解决mvcc更新丢失问题

多版本并发控制&#xff08;Multi-Version Concurrency Control, MVCC&#xff09;是现代数据库系统中常用的一种并发控制机制&#xff0c;用于提高并发性能和数据一致性。然而&#xff0c;MVCC 本身并不能完全解决更新丢失问题。让我们详细探讨一下这个问题的原因和背景。 更…

大语言模型(LLM)的训练微调 Fine Tuning -- part3 本地调用

以下代码示范如何调用已经微调后的大语言模型&#xff0c;调用本地模型 先决条件 已经有了本地训练好的大语言模型&#xff0c;如何训练可以参考我的博文 《生成式 AI》课程 作业6 大语言模型&#xff08;LLM&#xff09;的训练微调 Fine Tuning -- part2-CSDN博客文章浏览阅…

IDEA全局设置-解决maven加载过慢的问题

一、IDEA全局设置 注意&#xff1a;如果不是全局设置&#xff0c;仅仅针对某个项目有效&#xff1b;例在利用网上教程解决maven加载过慢的问题时&#xff0c;按步骤设置却得不到解决&#xff0c;原因就是没有在全局设置。 1.如何进行全局设置 a.在项目页面&#xff0c;点击f…