数据结构与算法-选择排序

引言

        在计算机科学中,数据结构和算法是两个至关重要的基石。它们共同决定了程序的效率、可读性和可维护性。本文我们将聚焦于一种基础而直观的排序算法——选择排序,并探讨其内在的工作机制以及在实际应用中的优缺点。

一、什么是选择排序?

        选择排序(Selection Sort)是一种简单直观的排序算法。它的基本思想是在未排序序列中找到最小(或最大)元素,存放到排序序列的起始位置,然后再从剩余未排序元素中继续寻找最小(或最大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。

二、选择排序的步骤详解

  1. 初始化:首先,在待排序的数组中选出一个基准元素,通常我们选择第一个元素作为初始基准。

  2. 查找最小(或最大)值:遍历从第二个元素开始到数组结尾的所有元素,找出其中的最小(或最大)值及其索引。

  3. 交换位置:将找到的最小(或最大)值与其所在位置之前的基准元素交换位置,这样基准元素的位置就确定了,它左边的元素都比它小(或大),右边的则还没有比较过。

  4. 重复过程:之后,对剩余未排序的部分进行同样的操作,即选取剩余部分的第一个元素为新的基准,重复上述查找和交换的过程,直至整个序列有序。

三、选择排序的时间复杂度和空间复杂度

四、选择排序的优点与缺点

  1. 时间复杂度:由于无论哪种情况下都需要对数组进行n(n-1)/2次比较,因此选择排序的时间复杂度为O(n²),这在处理大量数据时效率较低。

  2. 空间复杂度:选择排序是原地排序算法,只需要常量级的额外空间,故其空间复杂度为O(1)。

优点

  • 实现简单,逻辑清晰,易于理解。
  • 不依赖于原始数据的特性,对输入数据的随机性不敏感。
  • 空间效率高,只需要常量级的辅助空间。

缺点

  • 效率相对低下,尤其对于大数据集,因其线性阶的比较次数导致性能瓶颈明显。
  • 不稳定排序,即相等元素的顺序可能会在排序过程中发生改变。

五、选择排序的图解过程

图解小结

1. 选择排序一共有数组大小-1次排序

2. 每一轮排序,又是一个循环,循环的规则:

2.1 先假定当前这个数是最小数

2.2 然后和后面的每一个数比较,如果发现有比当前更小的数,就重新确定最小数并记录其下标

2.3 当遍历到数组的最后时,就得到本轮最小数和其下标

2.4 交换

六、选择排序的代码实践 

1.展示每一次选择排序过程

        int minIndex1 = 0;
        int min1 = arr[0];
        for (int j = 0 + 1; j < arr.length; j++) {
            if (min1 > arr[j]) {
                min1 = arr[j];
                minIndex1 = j;
            }
        }
        if (minIndex1 != 0) {
            arr[minIndex1] = arr[0];
            arr[0] = min1;
        }
        System.out.println("第一轮的遍历为");
        System.out.println(Arrays.toString(arr));

        int minIndex2 = 1;
        int min2 = arr[1];
        for (int j = 1 + 1; j < arr.length; j++) {
            if (min2 > arr[j]) {
                min2 = arr[j];
                minIndex2 = j;
            }
        }
        if (minIndex2 != 1) {
            arr[minIndex2] = arr[1];
            arr[1] = min2;
        }
        
        System.out.println("第二轮的遍历为");
        System.out.println(Arrays.toString(arr));

2.总结规律得到过程  

    //    有上述规律可见
    public static void selectSort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            int minIndex = i;
            int min = arr[i];
            for (int j = 1 + i; j < arr.length; j++) {
                if (min > arr[j]) {
                    min = arr[j];
                    minIndex = j;
                }
            }
            if (minIndex != i) {
                arr[minIndex] = arr[i];
                arr[i] = min;
            }
            System.out.printf("第%d轮的遍历为", i + 1);
            System.out.println(Arrays.toString(arr));
        }
    }

七、总结

        尽管选择排序在效率上相比其他高级排序算法如快速排序、归并排序等存在劣势,但在某些特定场景下仍有其独特价值。例如,在内存资源非常有限的嵌入式系统或者硬件受限环境下,选择排序可以作为备选方案。此外,由于其实现简单,也常被用于教学示例,帮助初学者理解和掌握排序算法的基本思路。

        选择排序虽然在效率上并不占优,但在理解和实现上却极为简洁明了,对于初学者而言,它是理解排序算法原理的良好起点。在实际开发中,我们可以根据具体场景选择更为高效的排序算法如快速排序、归并排序等。然而,理解选择排序的底层逻辑有助于我们更好地掌握其他复杂的排序算法,也是提升编程素养的重要一步。

 

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

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

相关文章

LeetCode 刷题 [C++] 第763题.划分字母区间

题目描述 给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段&#xff0c;同一字母最多出现在一个片段中。 注意&#xff0c;划分结果需要满足&#xff1a;将所有划分结果按顺序连接&#xff0c;得到的字符串仍然是 s 。 返回一个表示每个字符串片段的长度的列表。 …

如何在Vue中实现事件处理?

Vue是一种流行的JavaScript框架&#xff0c;广泛应用于前端开发。在Vue中&#xff0c;事件处理是一个非常关键的概念&#xff0c;可以帮助我们实现用户与页面的交互&#xff0c;今天我们就来探讨一下如何在Vue中实现事件处理。 首先&#xff0c;让我们先了解一下在Vue中如何绑…

微信小程序开发:接入阿里云人像动漫化api接口

前面我已经把腾讯云的人像转动漫化接口接到了我的小程序里&#xff0c;但是和阿里云的对比后&#xff0c;发现阿里云的效果会更好一些&#xff0c;且支持更多特效&#xff0c;如下&#xff1a; 我比较喜欢这个3D特效风格&#xff0c;动画3D也可以&#xff0c;大家拭目以待。 话…

波奇学Liunx:信号的产生,保存,处理

信号的产生&#xff0c;信号的保存&#xff0c;信号的处理 在操作系统中进程接受到信号会保存&#xff0c;产生 进程必须识别和能够处理信号&#xff0c;处理信号是进程的内置功能 进程收到信号时不一定会立即执行&#xff0c;所以进程必然有一套识别&#xff0c;保存&#xff…

Nodejs 第四十四章(redis基本使用)

字符串的操作 SET key value [NX|XX] [EX seconds] [PX milliseconds] [GET]key&#xff1a;要设置的键名。value&#xff1a;要设置的值。NX&#xff1a;可选参数&#xff0c;表示只在键不存在时才设置值。XX&#xff1a;可选参数&#xff0c;表示只在键已经存在时才设置值。…

MySQL字符集和比较规则

MySQL字符集和比较规则 字符集和比较规则简介 字符集&#xff1a; 描述字符与二进制数据的映射关系 比较规则&#xff1a;比较指定字符集中的字符的规则 字符集 我们知道&#xff0c;计算机无法直接存储字符串&#xff0c;实际存储的都是二进制数据。字符集是有限的&#xff…

windos 批量自定义 重命名

有时候需要批量重命名&#xff0c;window全选重命名格式又不能自定义&#xff0c;所以写了一个批处理文件来完成&#xff0c;可以自定义文件名格式 1.使用用方法 echo off setlocal enableextensions enabledelayedexpansion set i1 for /f %%i in (cd) do set var%%i for /r …

Python打发无聊时光:13.用pywin32库制作电脑本地快捷应用

第一步&#xff1a;新建一个simple_app.py 装库pywin32库 pip install pywin32 新建一个simple_app.py&#xff0c;复制下面代码&#xff0c;或者可以自己设计内容给 import tkinter as tkclass AnimatedGUI:def __init__(self, root):self.root rootself.root.title(&quo…

HTTP/2、HTTP/3分别解决了什么问题

总的来说就是HTTP/1.1是请求-响应模型导致队头阻塞问题&#xff0c;HTTP2是TCP层面导致队头阻塞问题 HTTP/2 多路复用&#xff0c;解决了HTTP/1.1队头阻塞问题 HTTP/1.1 的实现是基于请求-响应模型的。同一个连接中&#xff0c;HTTP 完成一个事务&#xff08;请求与响应&…

华为OD机试真题C卷-篇6

100分值题 宽度最小的子矩阵部门人力分配电脑病毒感染会议室占用时间段路口最短时间问题5G网络建设 宽度最小的子矩阵 给定一个n行 * m列的矩阵&#xff1b;给定一个k个整数的数组k_list&#xff1b;在n*m的矩阵中找一个宽度最小的子矩阵&#xff0c;该子矩阵包含k_list中所有…

【三维重建】VastGaussian:用于大场景重建的大3D Gaussian(CVPR 2024)

题目&#xff1a;VastGaussian: Vast 3D Gaussians for Large Scene Reconstruction 来源&#xff1a;清华大学&#xff1b;华为诺亚&#xff1b;中国科学院 链接&#xff1a;https://vastgaussian.github.io/ 总结&#xff1a;VastGaussian&#xff1a;基于3D GS的分块优化重…

2024年天津市安全员B证证模拟考试题库及天津市安全员B证理论考试试题

题库来源&#xff1a;安全生产模拟考试一点通公众号小程序 2024年天津市安全员B证证模拟考试题库及天津市安全员B证理论考试试题是由安全生产模拟考试一点通提供&#xff0c;天津市安全员B证证模拟考试题库是根据天津市安全员B证最新版教材&#xff0c;天津市安全员B证大纲整理…

【Linux】Linux原生异步IO:AIO

1、IO模型 1.1 简述 相信大家在搜索的时候,都会看到下面这张图,IO的使用场景:同步、异步、阻塞、非阻塞,可以组合成四种情况: 同步阻塞I/O: 用户进程进行I/O操作,一直阻塞到I/O操作完成为止。同步非阻塞I/O: 用户程序可以通过设置文件描述符的属性O_NONBLOCK,I/O操作可…

世界的本质是旋转(5)-在复平面上驱动软件无线电SDR交换BPSK波形

在上一篇文章中&#xff0c;我们介绍了复平面、拍照采样的一些思维实验。从本节开始&#xff0c;转入现实应用&#xff0c;通过控制复平面向量的位置&#xff0c;实现一个完整的BPSK全双工通信通道。 发射方&#xff1a;通过控制复平面向量在各个时刻的位置来携带信息的技术&a…

Socks5代理协议:原理、应用与优势

在计算机网络中&#xff0c;代理协议是一种用于转发客户端请求的机制。Socks5是其中一种广泛使用的代理协议。它主要工作在传输层和应用层之间&#xff0c;位于OSI参考模型的第五层&#xff08;会话层&#xff09;。其设计初衷是为了帮助授权用户突破防火墙限制&#xff0c;获取…

【洛谷 P8682】[蓝桥杯 2019 省 B] 等差数列 题解(数学+排序+辗转相除法)

[蓝桥杯 2019 省 B] 等差数列 题目描述 数学老师给小明出了一道等差数列求和的题目。但是粗心的小明忘记了一部分的数列&#xff0c;只记得其中 N N N 个整数。 现在给出这 N N N 个整数&#xff0c;小明想知道包含这 N N N 个整数的最短的等差数列有几项&#xff1f; 输…

远程调用--webClient

远程调用webClient 前言1、创建webClient2、准备数据3、执行请求4、接收返回响应到的数据整体代码 前言 非阻塞、响应式HTTP客户端 1、创建webClient WebClient client WebClient.create();2、准备数据 Map<String,String> params new HashMap<>();params.pu…

google最新大语言模型gemma本地化部署

Gemma是google推出的新一代大语言模型&#xff0c;构建目标是本地化、开源、高性能。 与同类大语言模型对比&#xff0c;它不仅对硬件的依赖更小&#xff0c;性能却更高。关键是完全开源&#xff0c;使得对模型在具有行业特性的场景中&#xff0c;有了高度定制的能力。 Gemma模…

c语言游戏实战(10):坤坤的篮球回避秀

前言&#xff1a; 这款简易版的球球大作战是博主耗时两天半完成的&#xff0c;玩家需要控制坤坤在游戏界面上移动&#xff0c;来躲避游戏界面上方不断掉下来的篮球。本游戏使用C语言和easyx图形库编写&#xff0c;旨在帮助初学者了解游戏开发的基本概念和技巧。 在开始编写代…

php开发项目 docx,pptx,excel表格上传阿里云,腾讯云存储后截取第一页生成缩略图

服务器或者存储上传的word,ppt和excel表格需要截取内容展示的时候,就需要管理后台每次上传文件时根据不同文件类型截取图片保存起来,并讲图片的地址保存到数据字段中.网上搜索了很多相关文章遇到的坑不少,经过2天时间终于完成了,将代码和遇到的问题完整记录下来. 本文用的…