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

ops/2024/11/9 16:45:26/

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

目录

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/ops/6798.html

相关文章

PID 控制系统如何优化?

PID控制器是一种常用的反馈回路控制器&#xff0c;主要用于控制工程和工业系统中的连续运行过程。PID代表比例&#xff08;Proportional&#xff09;、积分&#xff08;Integral&#xff09;、微分&#xff08;Derivative&#xff09;&#xff0c;这三种控制方式组合在一起&…

关于macOS 10.13-10.15系统安装教程

关于macOS 10.13-10.15系统安装教程 1、关机状态按完电源键&#xff0c;或重启黑屏后&#xff0c;按住option键不放&#xff0c;直到进入启动菜单&#xff1b; 2、选择启动U盘&#xff0c;开始跑进度条&#xff0c;跑完后进入如下界面&#xff1a; 安装界面语言选择&#xff0c…

割点,LeetCode 928. 尽量减少恶意软件的传播 II

一、题目 1、题目描述 给定一个由 n 个节点组成的网络&#xff0c;用 n x n 个邻接矩阵 graph 表示。在节点网络中&#xff0c;只有当 graph[i][j] 1 时&#xff0c;节点 i 能够直接连接到另一个节点 j。 一些节点 initial 最初被恶意软件感染。只要两个节点直接连接&#xf…

npm install 太慢?解决方法

npm install 太慢的问题可能有多种原因&#xff0c;包括网络问题、npm源的问题以及电脑硬件性能等。以下是一些常见的解决方法&#xff1a; 更换npm源&#xff1a;默认的npm源可能位于国外&#xff0c;这可能导致下载速度较慢。你可以更换为国内的npm源&#xff0c;例如淘宝npm…

【2024官方文档版学习笔记】React 状态管理

系列文章目录 一、 React快速入门 二、React描述IU 三、React添加交互 四、React状态管理 文章目录 系列文章目录四、状态管理1. 用state响应输入1.1声明式UI和命令式UI的比较1.2 声明式实现UI1.2.1 定位组件中的不同视图状态1.2.2 确认触发状态改变的因素1.2.3 通过useState表…

邦芒面试:如何在面试中精准描述个人能力

在竞争激烈的职场中&#xff0c;个人能力无疑是求职者获得心仪职位的关键。面试时&#xff0c;被问及“请简单描述一下你的个人能力”几乎是每位求职者都难以避免的问题。如何恰到好处地展现自己的个人能力&#xff0c;成为求职者面试成功的重要一环。那么&#xff0c;在面试时…

三元运算符

介绍 条件表达式 ? 表达式 1: 表达式 2; 运算规则&#xff1a; 如果条件表达式为 true&#xff0c; 运算后的结果是表达式 1&#xff1b;如果条件表达式为 false&#xff0c; 运算后的结果是表达式 2&#xff1b; 使用细节 表达式 1 和表达式 2 要为可以赋给接收变量的类型…

【Spring Boot】深入解密Spring Boot日志:最佳实践与策略解析

&#x1f493; 博客主页&#xff1a;从零开始的-CodeNinja之路 ⏩ 收录文章&#xff1a;【Spring Boot】深入解密Spring Boot日志&#xff1a;最佳实践与策略解析 &#x1f389;欢迎大家点赞&#x1f44d;评论&#x1f4dd;收藏⭐文章 目录 Spring Boot 日志一. 日志的概念?…