十大排序——5.选择排序

embedded/2024/9/24 1:25:48/

这篇文章我们来介绍一下选择排序

目录

1.介绍

2.代码实现

3.小结与思考


1.介绍

选择排序:选择排序( Selection sort)是一种简单直观的排序算法。它的工作原理是每一趟从待排序的数据元素中选出最小(或最大)的一个元素,顺序放在已排好序的数列的最后,直到全部待排序的数据元素排完。

选择排序算法通过选择和交换来实现排序,其排序流程如下:

  1. 首先从原始数组中选择最小的1个数据,将其和位于第1个位置的数据交换。
  2. 接着从剩下的n-1个数据中选择次小的1个元素,将其和第2个位置的数据交换
  3. 然后,这样不断重复,直到最后两个数据完成交换。最后,便完成了对原始数组的从小到大的排序。


假如给定初始数据:(118,101,105,127,112)

一次排序:101,118,105,127,112

二次排序:101,105,118,127,112

三次排序:101,105,112,127,118

四次排序:101,105,112,118,127

(绿色为交换的数据)

每一趟在 n - i + 1 ( i=1, 2, ..., n-1 ) 个记录中选取关键字最小的记录作为有序序列中第 i 个记录。具体来说,假设长度为 n 的数组 arr,要按照从小到大排序,那么先从 n 个数字中找到最小值min1,如果最小值min1 的位置不在数组的最左端(也就是min1不等于arr[0]),则将最小值 min1 和 arr[0] 交换,接着在剩下的 n-1 个数字中找到最小值 min2,如果最小值 min2 不等于 arr[1],则交换这两个数字,依次类推,直到数组 arr 有序排列。算法时间复杂度为 O(n^2)

2.代码实现

下面看一下代码实现:

import java.util.Arrays;
//选择排序
public class ChooseSort {public static void main(String[] args) {int [] arr = new int [] {5,9,2,7,3,1,10};sort(arr);System.out.println(Arrays.toString(arr));}public static void sort(int []arr){for (int i = 0; i <arr.length ; i++) {//从第一个索引开始,遍历数组for (int j = i; j <arr.length ; j++) {//从当前索引位置开始,遍历后面的数组if (arr[j]<arr[i]){//后面的数组元素比它小,就交换他两的位置int temp = arr[i];arr[i]=arr[j];arr[j]=temp;}}}}
}

3.小结与思考

选择排序的思路还是很简单的。

就是给你一个无序数组,首先你要在里面找一个最大的,我们就假设最后一个是最大的,用一个变量 i 来记录它的位置,然后遍历这个数组,从头遍历,遍历的变量记为 j ,在遍历过程中,遇到 j 位置的数据比 i 位置的数据大的数值了,那么就交换 i 与 j 位置的数据,始终保持 i 位置的数据是最大的。第一轮遍历完成后,我们最大的数据就放到数组的末尾了,然后 i 的位置往前面移动,然后继续上面的流程。总体来说很简单。

我一开始看这个选择排序时,把这个和冒泡排序弄混了,心想这个和冒泡排序的核心思路不都是一样的嘛,不都是双重遍历,然后交换嘛。但是看了冒泡排序代码后,发现二者还是有很大区别的。

冒泡排序的双重遍历中关键在第二重遍历,它是让相邻的两个进行比较然后交换。而选择排序是一开始假定一个最大的,然后和整个数组中元素依次比较然后交换,这就是二者的本质区别。

下面还是来看一下二者的代码吧:


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

相关文章

通过Dockerfile 创建 kali-novnc

创建Dockerfile # 使用官方Kali镜像作为基础镜像 FROM kalilinux/kali-rolling# 设置工作目录 WORKDIR /app# 将当前目录下的所有文件复制到工作目录中 COPY ./run.sh . RUN chmod x /app/run.sh# 安装项目依赖 RUN apt update -y RUN apt upgrade -y# 安装中文字体支持 apt …

《Linux运维总结:Kylin V10+ARM架构CPU基于docker-compose一键离线部署redis6.2.8之容器版哨兵集群》

总结&#xff1a;整理不易&#xff0c;如果对你有帮助&#xff0c;可否点赞关注一下&#xff1f; 更多详细内容请参考&#xff1a;《Linux运维篇&#xff1a;Linux系统运维指南》 一、部署背景 由于业务系统的特殊性&#xff0c;我们需要面向不通的客户安装我们的业务系统&…

酷得智能 无人机方案开发

东莞市酷得智能科技有限公司&#xff0c;是一家专业的技术服务公司&#xff0c;致力于为各类智能硬件提供高效、稳定、安全的底层驱动解决方案。拥有一支经验丰富、技术精湛的团队&#xff0c;能够为客户提供全方位的底层驱动开发服务。 无人机功能介绍&#xff1a; 1、自动跟…

【春秋云境】CVE-2023-4450 jeect-boot queryFieldBySql接口RCE漏洞

靶场介绍 JeecgBoot 是一个开源的低代码开发平台&#xff0c;Jimureport 是低代码报表组件之一。当前漏洞在 1.6.1 以下的 Jimureport 组件库中都存在&#xff0c;由于未授权的 API /jmreport/queryFieldBySql 使用了 freemarker 解析 SQL 语句从而导致了 RCE 漏洞的产生。 开…

【QT】QChartView和QChart的一些图表设置

enum RubberBand {NoRubberBand 0x0,VerticalRubberBand 0x1,HorizontalRubberBand 0x2,RectangleRubberBand 0x3};在 Qt Charts 中&#xff0c;QChartView 类提供了一些方法和属性来控制图表的渲染和交互行为。这些方法包括 setRenderHint 和 setRubberBand&#xff0c;它…

【iOS安全】iOS ARM汇编

mov指令 MOV X22, X0 将X0的值移到X22中 参数传递 参数1&#xff1a;寄存器X0传递 参数2&#xff1a;寄存器X1传递 参数3&#xff1a;寄存器X2传递 参数4&#xff1a;寄存器X3传递 如果需要传递更多参数&#xff0c;会使用栈来传递 返回值 ARM架构下&#xff0c;通常使用…

废液收集系统物联网远程监控解决方案

废液收集系统物联网远程监控解决方案 在面对日益严峻的环保压力和严格的法律法规要求下&#xff0c;构建一套高效、智能的废液收集系统物联网远程监控解决方案显得尤为重要。该方案旨在通过深度融合物联网技术、云计算、大数据分析等先进手段&#xff0c;实现对废液收集系统的…

node基础 第二篇

01 ffmpeg开源跨平台多媒体处理工具&#xff0c;处理音视频&#xff0c;剪辑&#xff0c;合并&#xff0c;转码等 FFmpeg 的主要功能和特性:1.格式转换:FFmpeg 可以将一个媒体文件从一种格式转换为另一种格式&#xff0c;支持几乎所有常见的音频和视频格式&#xff0c;包括 MP…