排序之选择排序

文章目录

  • 前言
  • 一、直接选择排序
    • 1、直接选择排序基本思想
    • 2、直接选择排序代码实现
    • 3、直接选择排序的效率
  • 二、堆排序
    • 1、堆排序
    • 2、堆排序的效率


前言

选择排序的基本思想就是每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完。

一、直接选择排序

1、直接选择排序基本思想

在元素集合array[i]–array[n-1]中选择值最大(小)的数据元素,若它不是这组元素中的最后一个(第一个)元素,则将它与这组元素中的最后一个(第一个)元素交换,在剩余的array[i]–array[n-2](array[i+1]–array[n-1])集合中,重复上述步骤,直到集合剩余1个元素。
例如有如下一个数组。
在这里插入图片描述
先取最小值min在数组中下标为0,然后遍历数组每个元素,并且使每个元素和下标为min的元素比较,如果该元素小于下标为min的元素,就使min等于该元素的下标,然后继续向后比较。
在这里插入图片描述
在这里插入图片描述
当遍历一遍数组后,此时下标为min的元素为数组中最小的元素。
在这里插入图片描述
将下标为min的元素与下标为0的元素交换,使最小的元素在数组首位置,然后将min重新置为1,再次遍历数组寻找第二小的元素。
在这里插入图片描述

2、直接选择排序代码实现

在上述的演示中,每次遍历数组我们只找到了数组中未排序元素中最小的值,然后将该值放在排序好的元素之后。在代码实现时,我们稍微优化了一下,即定义min和max两个变量用来存数组中未排序元素中的最大值和最小值的下标,然后将最小值放在数组前面,最大值放在数组末尾。即每次遍历数组选择出最大值和最小值,然后放入相应的位置。

void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

void SelectSort(int* arr, int n)
{
	//记录数组的头尾下标
	int begin = 0;
	int end = n - 1;
	while (begin < end)
	{
		//另数组中未排序的首个元素的下标为未排序元素中的最大值和最小值
		int mini = begin;
		int maxi = begin;
		int i = 0;
		//从未排序的元素开始遍历数组
		for (i = begin+1; i <= end; i++)
		{
			//如果有元素比下标为mini的元素小,就让mini为该元素下标
			if (arr[i] < arr[mini])
			{
				mini = i;
			}
			//如果有元素比下标为maxi的元素大,就让max为该元素下标
			if (arr[i] > arr[maxi])
			{
				maxi = i;
			}
		}
		//然后将未排序中最小的元素和下标为begin的元素交换
		Swap(&arr[begin], &arr[mini]);
		//此时需要判断如果未排序中最大的元素的下标为begin的话,而执行过Swap(&arr[begin], &arr[mini]);语句后
		//原来begin下标的元素现在已经交换到下标为mini的位置了,所以此时未排序元素中最大的元素的下标为mini
		if (begin == maxi)
		{
			maxi = mini;
		}
		Swap(&arr[end], &arr[maxi]);
		++begin;
		--end;
	}
	
}

3、直接选择排序的效率

直接选择排序的复杂度为O(N2),并且就算数组元素为基本顺序有序,直接选择排序的复杂度也为O(N2) 。而当数组元素为基本顺序有序时,直接插入排序的复杂度可以达到O(N),并且只有数组元素逆序为直接插入排序的最差情况。所以综合考虑的话,直接选择排序的效率没有直接插入排序的高。

  1. 直接选择排序思考非常好理解,但是效率不是很好。实际中很少使用
  2. 时间复杂度:O(N^2)
  3. 空间复杂度:O(1)
  4. 稳定性:不稳定

二、堆排序

1、堆排序

选择排序的基本思想就是每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完。而堆结构的堆头结点存的就是整个堆中最大(最小)值,堆排序就是每次将堆中最大(最小)值取出,将堆头结点删除,再重新选出堆中最大(最小)值作为新堆头结点。所以堆排序也是选择排序的一种。
堆排序的详细讲解在下面这篇文章中,可以点击链接进行阅读。
c语言实现堆

2、堆排序的效率

  1. 堆排序使用堆来选数,效率就高了很多。
  2. 时间复杂度:O(N*logN)
  3. 空间复杂度:O(1)
  4. 稳定性:不稳定

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

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

相关文章

pdfh5在线预览pdf文件

前言 pc浏览器和ios的浏览器都可以直接在线显示pdf文件&#xff0c;但是android浏览器不能在线预览pdf文件&#xff0c;如何预览pdf文件&#xff1f; Github: https://github.com/gjTool/pdfh5 Gitee: https://gitee.com/gjTool/pdfh5 使用pdfh5预览pdf 编写预览页面 <…

PSP - 蛋白质结构预测 OpenFold Multimer 模型训练参数与配置

欢迎关注我的CSDN&#xff1a;https://spike.blog.csdn.net/ 本文地址&#xff1a;https://spike.blog.csdn.net/article/details/132575709 OpenFold Multimer 是用于预测蛋白质多聚体结构的计算方法。基于OpenFold 的单体预测框架&#xff0c;利用深度学习技术&#xff0c;结…

Python Flask Web开发二:数据库创建和使用

前言 数据库在 Web 开发中起着至关重要的作用。它不仅提供了数据的持久化存储和管理功能&#xff0c;还支持数据的关联和连接&#xff0c;保证数据的一致性和安全性。通过合理地设计和使用数据库&#xff0c;开发人员可以构建强大、可靠的 Web 应用程序&#xff0c;满足用户的…

Mysql数据库(1)—索引

索引是什么&#xff1f; 索引是帮助MySQL高效获取数据的排好序的数据结构。常见的索引数据结构包括&#xff1a; 二叉树红黑树Hash表B-Tree mysql索引分类 按逻辑结构分类&#xff1a;B tree索引、Hash索引、Full-text索引。按物理存储分类&#xff1a; &#xff08;1&…

Linux命令awk详细用法

简介 awk 是一种强大的文本处理工具&#xff0c;用于在命令行环境下对文件或数据流进行逐行处理和分析。它是由 Alfred Aho、Peter Weinberger 和 Brian Kernighan 在 1977 年开发的&#xff0c;并以他们三人的姓氏命名。awk 在 Unix/Linux 系统中非常常见&#xff0c;也有 Win…

【Git】在idea中多分支开发如何——合并分支、处理冲突

博主简介&#xff1a;22级计算机科学与技术本科生一枚&#x1f338;博主主页&#xff1a;是瑶瑶子啦每日一言&#x1f33c;: “人间总有一两风&#xff0c;填我十万八千梦” 目录 一、背景二、具体操作 一、背景 我当前开发的分支——hfy我想将subject分支的最新代码拉取&…

银河麒麟V10(Tercel)服务器版安装 Docker

一、服务器环境 ## 查看系统版本&#xff0c;确认版本 cat /etc/kylin-release Kylin Linux Advanced Server release V10 (Tercel)## 操作系统 uname -p aarch64## 内核版本&#xff08;≥ 3.10&#xff09; uname -r 4.19.90-21.2.ky10.aarch64## iptables 版本&#xff08;…

PowerBuilder通过jdbc连接mysql

PowerBuilder,一个古老的IDE,打算陆续发些相关的,也许还有人需要,内容可能涉及其他作者,但基本都是基于本人实践整理,如涉及归属,请联系. 打开PB,菜单Tools--> system options,打开JAVA选项,点击新增文件&#xff08;白色文件图标&#xff09; 重要&#xff1a;需要在这里修…

实体店砍价营销活动制作技巧大公开

砍价营销是一种非常受欢迎的促销方式&#xff0c;可以吸引更多的顾客参与&#xff0c;提高销售量和品牌知名度。乔拓云网为您提供了一个简便而实用的砍价营销活动制作指南&#xff0c;让您轻松打造一场成功的砍价活动。 首先&#xff0c;您需要注册并登录乔拓云网账号&#xff…

简单了解网络传输介质

目录 一、同轴电缆 二、双绞线 三、光纤 四、串口电缆 一、同轴电缆 10BASE前面的数字表示传输带宽为10M&#xff0c;由于带宽较低、现在已不再使用。 50Ω同轴电缆主要用来传送基带数字信号&#xff0c;因此也被称作为基带同轴电缆&#xff0c;在局域网中得到了广泛的应用…

【函数栈帧解析:代码的迷人堆积和无限嵌套】

本章重点 一、何为函数栈帧 二、函数栈帧特性 - 同栈 - 后进先出 三、认识内存空间布局图 四、认识相关寄存器 五、认识相关汇编命令 六、测试代码&#xff1a; 七、函数栈帧全过程 要解决的问题​​​​​​​ 局部变量是怎么创建的&#xff1f;为什么局部变量的值是随机值&am…

echarts图表共用一个 timeline(A表 timeline 同时控制B表)

先看效果: 再看代码(部分): let barOption = {baseOption: {height: 350,timeline: {x: cen

部署项目至服务器

安装conda https://zhuanlan.zhihu.com/p/489499097 个人租借的服务器如何进行端口的开放呢&#xff1f; 防火墙设置&#xff1a; 添加规则设置&#xff1a; 即可&#xff1b; 通常下租借的服务器没有防火墙设置 相关链接&#xff1a; https://blog.csdn.net/weixin_4520…

SAP-MM-冲销凭证布局变更

业务场景&#xff1a; 仓管员在冲销物料凭证时MBST&#xff0c;显示行很少&#xff0c;只有7行&#xff0c;提出需求调整布局为多行&#xff0c;但是MBST没有调整布局功能&#xff0c; 解决&#xff1a;点击“定制本地布局-选项-字体设置”调整字体大小 跟据需求调整字体&…

正中优配:什么叫融资融券

融资融券是股市中常见的一种买卖方法。融资是指投资者通过某些途径借到资金&#xff0c;用以购买股票。融券是指投资者借股票卖出&#xff0c;并承诺在未来某一时点将股票偿还。 融资融券的实质是一种杠杆买卖&#xff1a;投资者通过融资或融券&#xff0c;增加了自己的资金量…

30个惊艳的数据可视化作品,让你感受“数据之美”!

‍ 在一个信息大爆炸的时代&#xff0c;每天都有很多的新消息、新发现、新趋势向我们狂轰乱炸而来。在这个过程中&#xff0c;我们既是数据的生产者&#xff0c;也是数据的使用者&#xff0c;然而初次获取和存储的原始数据总是杂乱无章的。 要想数据达到生动有趣、让人一目了…

什么是 ORAM

参考文献&#xff1a; [GO96] Goldreich O, Ostrovsky R. Software protection and simulation on oblivious RAMs[J]. Journal of the ACM (JACM), 1996, 43(3): 431-473.[Batcher68] Batcher K E. Sorting networks and their applications[C]//Proceedings of the April 30…

206.Flink(一):flink概述,flink集群搭建,flink中执行任务,单节点、yarn运行模式,三种部署模式的具体实现

一、Flink概述 1.基本描述 Flink官网地址:Apache Flink — Stateful Computations over Data Streams | Apache Flink Flink是一个框架和分布式处理引擎,用于对无界和有界数据流进行有状态计算。 2.有界流和无界流 无界流(流): 有定义流的开始,没有定义结束。会无休止…

【webpack】HMR热更新原理

本文&#xff1a;参考文章 一、HMR是什么&#xff0c;为什么出现 1、出现的原因 之前&#xff0c;应用的加载、更新都是一个页面级别的操作&#xff0c;即使单个代码文件更新&#xff0c;整个页面都要刷新&#xff0c;才能拿到最新的代码同步到浏览器&#xff0c;导致会丢失…

【C语言】循环语句详解

✨个人主页&#xff1a; Anmia.&#x1f389;所属专栏&#xff1a; C Language &#x1f383;操作环境&#xff1a; Visual Studio 2019 版本 目录 1.什么是循环结构&#xff1f; 2.while循环 while流程图 while语句中的break和continue break continue 3.for循环 for流…