【排序算法之选择排序】
创始人
2025-06-01 10:21:13
0次

文章目录

  • 概要：本期主要学习排序算法中的选择排序，会着重讲解算法的核心思想、时空复杂度分析以及代码的实现。
  • 一、选择排序
  • 二、核心思想
  • 三、时空复杂度分析
  • 四、代码实现
  • 结尾

概要：本期主要学习排序算法中的选择排序，会着重讲解算法的核心思想、时空复杂度分析以及代码的实现。

一、选择排序

选择排序很类似插入排序，也会见数组分为已排序区域和未排序区域。它和插入排序的区别是：选择排序每次会将未排序区域中的最小元素插入已排序区域的末尾。

二、核心思想

假定有一个n个元素的无序数组(初始化 i = 0)：

  1. 选择数组中的第i元素作为最小值参照，与数组中其余的n-1个元素做对比。比较过程中动态标记其中最小的元素，完成一轮比较后，交换最小元素和第i个元素的位置。到这里，一轮排序结束，确定了一个元素的最终位置
  2. 执行n-1次上述过程，当i == n-1时，完成数组排序，并且数组为升序排列。
    跳转到这个网页，直观地感受选择排序吧：）

三、时空复杂度分析

时间复杂度的分析依旧从三个层面分析：最好、最坏和平均。

  1. 最好的情况是数组有序，需要执行n个元素的n轮比较，时间复杂度为O(n^2)。
  2. 最坏的情况是数组逆序，也需要执行n个元素的n轮比较，时间复杂度为O(n^2)。
  3. 一般情况下，选择排序也是需要执行n个元素的n轮比较，时间复杂度为O(n^2)。
    强调一点，选择排序不是稳定排序，排序执行过程中都会与未排序区域的最小值元素交换位置，这破坏了算法的稳定性。
    空间复杂度为O(1),因为只有在发生交换元素时才会占用常数级的空间。选择排序是原地排序算法。

四、代码实现

下面展示C++的实现源码：

void SortFuncation::SelectSort(QVector _vec)
{if(_vec.length() <= 1){return ;}QTime _beginTime = QTime::currentTime();qDebug()<int _iMin = i;for(int j = i;j < _iLen;j ++){if(_vec.at(_iMin) > _vec.at(j)){_iMin = j;}}/* 将未排序区域的最小元素插入已排序区域的末尾 */int _iTemp = _vec.at(i);_vec[i] = _vec[_iMin];_vec[_iMin] = _iTemp;}QTime _endTime = QTime::currentTime();qDebug()<

结尾

到这里，我们针对平均时间复杂度为O(n^2)的排序算法的学习已经结束了，下面浅浅做一些总结：

算法名称是否为原地排序是否为稳定排序最好的时间复杂度最坏的时间复杂度平均的时间复杂度
冒泡排序是是O(n)O(n^2)O(n^2)
插入排序是是O(n)O(n^2)O(n^2)
选择排序是否O(n^2)O(n^2)O(n^2)

欧克，今天的学习就到这，下期我们学习归并排序：）

词库加载错误:未能找到文件“E:\highferrum_mysql\Configuration\Dict_Stopwords.txt”。

上一篇：基于 Zynq+AD+DA 的振动台控制器测试与验证（四）

下一篇：时钟、晶振概念

相关内容

热门资讯

linux入门---制作进度条 了解缓冲区 我们首先来看看下面的操作： 我们首先创建了一个文件并在这个文件里面添加了...
C++ 机房预约系统（六）：学... 8、 学生模块 8.1 学生子菜单、登录和注销 实现步骤： 在Student.cpp的...
JAVA多线程知识整理 Java多线程基础 线程的创建和启动 继承Thread类来创建并启动 自定义Thread类的子类&#...
【洛谷 P1090】[NOIP... [NOIP2004 提高组] 合并果子 / [USACO06NOV] Fence Repair G ...
国民技术LPUART介绍 低功耗通用异步接收器（LPUART） 简介 低功耗通用异步收发器...
城乡供水一体化平台-助力乡村振... 城乡供水一体化管理系统建设方案 城乡供水一体化管理系统是运用云计算、大数据等信息化手段࿰...
程序的循环结构和random库...   第三个参数就是步长     引入文件时记得指明字符格式，否则读入不了 ...
中国版ChatGPT在哪些方面... 目录 一、中国巨大的市场需求 二、中国企业加速创新 三、中国的人工智能发展 四、企业愿景的推进 五、...
报名开启 | 共赴一场 Flu... 2023 年 1 月 25 日，Flutter Forward 大会在肯尼亚首都内罗毕...
汇编00-MASM 和 Vis... Qt源码解析 索引 汇编逆向--- MASM 和 Visual Studio入门 前提知识ÿ...
【简陋Web应用3】实现人脸比... 文章目录🍉 前情提要🌷 效果演示🥝 实现过程1. u...
前缀和与对数器与二分法 1. 前缀和 假设有一个数组，我们想大量频繁的去访问L到R这个区间的和，...
windows安装JDK步骤 一、 下载JDK安装包 下载地址：https://www.oracle.com/jav...
分治法实现合并排序(归并排序)... 🎊【数据结构与算法】专题正在持续更新中，各种数据结构的创建原理与运用✨...
在linux上安装配置node... 目录前言1，关于nodejs2，配置环境变量3，总结 前言...
Linux学习之端口、网络协议... 端口：设备与外界通讯交流的出口 网络协议： 　　网络协议是指计算机通信网...
Linux内核进程管理并发同步... 并发同步并发 是指在某一时间段内能够处理多个任务的能力，而 并行 是指同一时间能够处理...
opencv学习-HOG LO... 目录1. HOG(Histogram of Oriented Gradients,方向梯度直方图)1...
EEG微状态的功能意义 导读大脑的瞬时全局功能状态反映在其电场结构上。聚类分析方法一致地提取了四种头表面脑电场结构ÿ...
【Unity 手写PBR】Bu... 写在前面 前期积累： GAMES101作业7提高-实现微表面模型你需要了解的知识 【技...