选择排序算法(Selection Sort)原理及实现

选择排序算法,运行效率不高,但是非常容易理解,算法复杂度为 O(n^{2}) 。

原理:

假设要排序的数组的长度为n,将数组先分为两个部分,一个是有序区域部分,另一个为无序区域部分。初始时有序部分中没有元素,所有的元素都在无序区域中。第 1 趟遍历无序区域中的 n 个元素,从中选出最小的元素作为有序区域的第一个元素;第 2 趟遍历无序区域中剩下的 n-1 个元素,选出最小的元素作为有序区域的第二个元素。可以看到每遍历无序区域一遍,就找到其中最小的元素放入有序区的尾部,这样只要遍历n遍就能将无序区域中的所有元素按照顺序放入有序区域中了,也就完成了排序的操作。

代码实现:

#include <stdio.h>

int main() {
    int a[10];
    int n = 0, i, j, k, t;
    while (scanf("%d", &a[n])) {//输入任意个数字,遇到0时结束输入,记录个数n
        if (a[n] == 0) break;
        n++;
    }
    for (i = 0; i < n - 1; i++) {//选择排序,遍历n-1遍
        // 从数组开头到第i个元素的区间为有序区域, 无序区域紧接着有序区域
        // 内层循环就是遍历无序区域找到无序区域中最小的元素
        for (j = i + 1, k = i; j < n; j++) {//a[k]记录无序区域中最小元素,k为最小元素的下标
            if (a[j] < a[k]) k = j;
        }
        if (k != i) { // 如果最小值不是第i个元素,则将 a[i] 和 a[k]交换
            t = a[i];
            a[i] = a[k];
            a[k] = t;
        }
    }
    for (i = 0; i < n; i++) {
        printf("%d ", a[i]);
    }
    return 0;
}

可以看出代码的实现并没有遍历 n 遍,而是 n-1 遍,这是因为当无序区域中剩下最后一个元素的时候,该元素是在有序区域之后的,即最后无序区域剩下一个元素时数组已经是有序的了。

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

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

相关文章

基于Spring Boot+Vue的智慧图书管理系统

末尾获取源码作者介绍&#xff1a;大家好&#xff0c;我是墨韵&#xff0c;本人4年开发经验&#xff0c;专注定制项目开发 更多项目&#xff1a;CSDN主页YAML墨韵 学如逆水行舟&#xff0c;不进则退。学习如赶路&#xff0c;不能慢一步。 一、项目简介 如今社会上各行各业&…

漫谈微服务网关

一、什么是服务网关 服务网关 路由转发 过滤器 1、路由转发&#xff1a;接收一切外界请求&#xff0c;转发到后端的微服务上去&#xff1b; 2、过滤器&#xff1a;在服务网关中可以完成一系列的横切功能&#xff0c;例如权限校验、限流以及监控等&#xff0c;这些都可以通过…

性能优化(CPU优化技术)-NEON指令详解

原文来自ARM SIMD 指令集&#xff1a;NEON 简介 &#x1f3ac;个人简介&#xff1a;一个全栈工程师的升级之路&#xff01; &#x1f4cb;个人专栏&#xff1a;高性能&#xff08;HPC&#xff09;开发基础教程 &#x1f380;CSDN主页 发狂的小花 &#x1f304;人生秘诀&#xf…

服务器版本命令查看

1、# uname &#xff0d;a &#xff08;Linux查看版本当前操作系统内核信息&#xff09; 2、# cat /proc/version &#xff08;Linux查看当前操作系统版本信息&#xff09; 3、# cat /etc/issue 或 cat /etc/redhat-release &#xff08;Linux查看版本当前操作系统发行版信息&…

前端项目,个人笔记(五)【图片懒加载 + 路由配置 + 面包屑 + 路由行为修改】

目录 1、图片懒加载 步骤一&#xff1a;自定义全局指令 步骤二&#xff1a;代码中使用 ​编辑步骤三&#xff1a;效果查看 步骤四&#xff1a;代码优化 2、封装组件案例-传对象 3、路由配置——tab标签 4、根据tab标签添加面包屑 4.1、实现 4.2、bug&#xff1a;需要…

k8s详细教程

Kubernetes详细教程 1. Kubernetes介绍 1.1 应用部署方式演变 在部署应用程序的方式上&#xff0c;主要经历了三个时代&#xff1a; 传统部署&#xff1a;互联网早期&#xff0c;会直接将应用程序部署在物理机上 优点&#xff1a;简单&#xff0c;不需要其它技术的参与 缺点…

QT 驾校系统界面布局编写

MainWindow::MainWindow(QWidget *parent): QMainWindow(parent), ui(new Ui::MainWindow) {ui->setupUi(this);this->resize(ui->label_img->width(),ui->label_img->height());//图片自适应窗口大小ui->label_img->setScaledContents(true);//图片置…

ES集群和分片以及脑裂

文章目录 概要一、概念二、节点角色三、master节点脑裂四、参考 概要 在工作中不可避免会用到ES&#xff0c;而用到ES就不得使用其集群模式了。 单节点的话不得不面临两个重大缺陷&#xff1a;单点故障&#xff08;高可用&#xff09;和海量数据存储搜索。 ES通过集群模式解决…

竞争优势:大型语言模型 (LLM) 如何重新定义业务策略

人工智能在内容创作中的突破 在当今快节奏的商业环境中&#xff0c;像 GPT-4 这样的大型语言模型 (LLM) 不再只是一种技术新颖性&#xff1b; 它们已成为重新定义跨行业业务战略的基石。 从增强客户服务到推动创新&#xff0c;法学硕士提供了企业不容忽视的竞争优势。 1. 加强…

LVGL:拓展部件——键盘 lv_keyboard

一、概述 此控件特点&#xff1a; 特殊Button矩阵&#xff1a;lv_keyboard 本质上是一个经过定制的按钮矩阵控件。每个按钮都可以独立触发事件或响应。预定义的键映射&#xff1a;lv_keyboard 自带了一套预设的按键布局和对应的字符映射表&#xff0c;开发者可以根据需要选择…

Spring MVC入门(4)

请求 获取Cookie/Session 获取Cookie 传统方式: RequestMapping("/m11")public String method11(HttpServletRequest request, HttpServletResponse response) {//获取所有Cookie信息Cookie[] cookies request.getCookies();//打印Cookie信息StringBuilder build…

WPF —— 控件模版和数据模版

1:控件模版简介: 自定义控件模版&#xff1a;自己添加的样式、标签&#xff0c;控件模版也是属于资源的一种&#xff0c; 每一个控件模版都有一唯一的 key&#xff0c;在控件上通过template属性进行绑定 什么场景下使用自定义控件模版&#xff0c;当项目里面多个地方…

K8s的Pod出现Init:ImagePullBackOff问题的解决,(以calico网络插件为例)

问题描述&#xff1a; 对于这类问题的解决思路应该都差不多&#xff0c;本文以calico插件安装为例&#xff0c;发现有个Pod的镜像没有pull成功 第一步&#xff1a;查看这个pod的描述信息 kubectl describe pod calico-node-t9rql -n kube-system从上图发现是docker拉取"…

基于Lealfet.js展示Turf.js生成的平滑曲线实践

目录 前言 一、问题的由来 1、创建网页框架 2、创建map对象 3、构建点位&#xff0c;生成路线 二、Turf.js平滑曲线改造 1、官网方法介绍 2、0.4弯曲度曲线 3、0.85弯曲度曲线 4、0.1度弯曲曲线 5、综合对比 总结 前言 在很多的关于路线的gis应用中&#xff0c;我们…

详细教---用Django封装写好的模型

本次我们要用自己写好的热销词条爬虫代码来演示如何用Django把我们写好的模型封装。 第一步&#xff1a;代码准备 热搜词条搜集代码&#xff1a; import requests from lxml import etreeurl "https://tophub.today/n/KqndgxeLl9" headers{User-Agent: Mozilla/5.…

如何本地部署1Panel面板

文章目录 前言1. Linux 安装1Panel2. 安装cpolar内网穿透3. 配置1Panel公网访问地址4. 公网远程访问1Panel管理界面5. 固定1Panel公网地址 前言 1Panel 是一个现代化、开源的 Linux 服务器运维管理面板。高效管理,通过 Web 端轻松管理 Linux 服务器&#xff0c;包括主机监控、…

NLP---Bert分词

目录&#xff1a; Q&#xff1a;bert分词步骤1&#xff1a;构建N * N 的相关性矩阵&#xff0c;计算相邻两个字的相关性&#xff0c;低的话&#xff08;<阈值&#xff09;就切割。2&#xff1a;将A词进行mask计算出A的embedding&#xff0c;然后将AB两个词一起mask&#xff…

除了大众点评,中国未来还会产生多少家这样的人工智能公司? - 学习Yelp公司的软件工程-评价和推荐系统

原文作者&#xff1a;Jason Sleight&#xff0c;ML&#xff08;Machine Learning&#xff09;平台集团技术负责人 翻译&#xff1a;数字化营销工兵 了解数据是Yelp成功的重要组成部分。为了将我们的消费者与当地优秀的企业联系起来&#xff0c;我们每天为各种任务提供数百万条建…

【0274】从shared init file或local init file加载relation cache(2 - 1)

上一篇&#xff1a; 【0273】深入分析 relcache&#xff08;relation descriptor cache&#xff09;初始化第一阶段&#xff08;1&#xff09; 【0264】深入分析relcache&#xff08;relation descriptor cache&#xff09;缓存初始化第2阶段&#xff08;2&#xff09; 1. 前…

JSONP 实现跨域请求案例

后端使用 express 搭建&#xff0c;案例代码如下&#xff1a; const express require(express)const app express() const PORT 3000app.get(/data, (req, res) > {const jsonData {name: Alan,age: 666,city: GD}const callback req.query.callback // 获取前端中的回…
最新文章