八大排序(一)冒泡排序,选择排序,插入排序,希尔排序

一、冒泡排序

冒泡排序的原理是:从左到右,相邻元素进行比较。每次比较一轮,就会找到序列中最大的一个或最小的一个。这个数就会从序列的最右边冒出来。

以从小到大排序为例,第一轮比较后,所有数中最大的那个数就会浮到最右边;第二轮比较后,所有数中第二大的那个数就会浮到倒数第二个位置……就这样一轮一轮地比较,最后实现从小到大排序。

95b4e127dcdf46aeb00895cea64cfffa.gif

代码如下:

void BubbleSort(int* a, int n)
{for (size_t j = 0; j < n; j++){int exchange = 0;for (size_t i = 1; i < n-j; i++){if (a[i - 1] > a[i]){Swap(&a[i - 1], &a[i]);exchange = 1;}}if (exchange == 0){break;}}
}

冒泡排序时间复杂度

如果待排序序列的初始状态恰好是我们希望的排序结果(如升序或降序),一趟扫描即可完成排序。

所需的关键字比较次数C和记录移动次数M均达到最小值:

                                       e38b2c98c7fc40dc8f65c5d45cace00b.png

冒泡排序最好的时间复杂度为O(n)。

如果待排序序列是反序(如我们希望的结果是升序,待排序序列是降序)的,需要进行n-1趟排序。每趟排序要进行n-i次关键字的比较(1≤i≤n-1),且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下,比较和移动次数均达到最大值:

                                    0293cfb6ce314486889177adc2ce3045.png  

冒泡排序的最坏时间复杂度为O(N^2)
综上,因此冒泡排序总的平均时间复杂度为O(N^2)

冒泡排序是稳定的排序

 

二、选择排序

选择排序的工作原理是:第一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,然后再从剩余的未排序元素中寻找到最小(大)元素,继续放在起始位置知道未排序元素个数为0。

选择排序的步骤:

1>首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置。

2>再从剩余未排序元素中继续寻找最小(大)元素,然后放到未排序序列的起始位置。

3>重复第二步,直到所有元素均排序完毕。

20210808223821944.gif

选择排序代码实现:

//交换两个数据
void Swap(int* a, int* b)
{int temp = *a;*a = *b;*b = temp;
}//选择排序
void SelectSort(int* arr, int size)
{int i = 0;for (i = 0; i < size-1; i++){int min = i;int j = 0;for (j = i+1; j < size; j++){if (arr[j] < arr[min]){min = j;}}Swap(&arr[i], &arr[min]);}
}

思路优化:

以上算法是每次找出最小的放在指定位置,一共要找n-1次,如果我们每次不但找到最小的,还找到最大的,将最小的与左端交换,最大的与右端交换,那么就少了一半的遍历次数,从而提高效率。

  1. 变量begin和变量end是数组的两端,minmax分别找小和大的下标
  2. 先交换minbegin位置的数值,再交换maxend位置的数值
  3. begin右移,end左移,继续找大找小,继续交换
  4. 重复上述操作,直到遍历完所有数组

排序优化后问题

若是max的位置与begin重合,则begin先与min的位置交换,此时max位置的最大值被交换走,导致endmax交换的数值是错误的。

问题解决:

maxbegin重合时,beginmin交换后导致max指向的不再是最大值,所以当我们对begin交换后,就要对max进行一个修正,让max指向最大值,然后完成end的交换

1、max与begin重合,并且begin此时完成了交换,此时最大值已经交换到了min所指向的位置

2、对max进行修正并完成与end的交换

优化后代码: 

//交换两个数据
void Swap(int* a, int* b)
{int temp = *a;*a = *b;*b = temp;
}//选择排序
void SelectSort(int* arr, int size)
{int begin = 0;int end = size - 1;while (begin < end){int max = begin;int min = begin;int i = 0;for (i = begin+1; i <= end; i++){if (arr[i] < arr[min]){min = i;}if (arr[i] > arr[max]){max = i;}}Swap(&arr[begin], &arr[min]);if (begin == max)				//修正max{max = min;}Swap(&arr[end], &arr[max]);begin++;end--;}
}

选择排序时间复杂度:

时间复杂度:O(n^2)
空间复杂度:O ( 1 )
​选择排序是不稳定的排序

三、插入排序

直接插入排序是一种简单的插入排序法,对数组进行一个遍历,每次都对待排的数据按照大小顺序插入到一个有序数组中的特定位置,直到所有的数据全部插入完毕,就得到一个有序数列。

​ 插入排序的算法非常简单,依次对每一个元素进行单趟排序就行了,由于要前一个数比较则只需要从1开始遍历n-1

                                   813242d2ff544526b82a2ee67f06d5bc.png   

当插入第i(i>=1)个元素时,前面的array[0],array[1],…,array[i-1]已经排好序,此时用array[i]的排序码与array[i-1],array[i-2],…的排序码顺序进行比较,找到插入位置即将array[i]插入,原来位置上的

元素顺序后移

20210223174254141.gif

插入排序代码:

void InsertSort(int* arr, int size)
{int i = 0;for (i = 1; i < size; i++){int end = i;int temp = arr[end];	//记录待排数值while (end > 0){if (arr[end-1] > temp)	//若前一个数大于待排数值,则后移一位{arr[end] = arr[end-1];end--;}else{break;}}// arr[end-1] = temp;是之前的错误,现已修正arr[end] = temp;	//将数据放入插入位置}
}

插入排序的时间复杂度:

1. 元素集合越接近有序,直接插入排序算法的时间效率越高
2. 时间复杂度:O(N^2)
3. 空间复杂度:O(1),它是一种稳定的排序算法
4. 稳定性:稳定

四、希尔排序

希尔排序法又称缩小增量法。希尔排序法的基本思想是:先选定一个整数,把待排序文件中所有记录分成个组,所有距离为的记录分在同一组内,并对每一组内的记录进行排序。然后,取,重复上述分组和排序的工作。当到达=1时,所有记录在统一组内排好序。

0b5e3b84b85d427d84e260a1f6733a5e.png

1. 希尔排序是对直接插入排序的优化。

2. 当gap > 1时都是预排序,目的是让数组更接近于有序。当gap == 1时,数组已经接近有序的了,这样就会很快。这样整体而言,可以达到优化的效果。我们实现后可以进行性能测试的对比。

3. 希尔排序的时间复杂度不好计算,因为gap的取值方法很多,导致很难去计算,因此在好些树中给出的

14642c0b17cc41a496c808ed6214b234.gif#pic_center

希尔排序代码实现:

void ShellSort(int* arr, int size)
{int gap = size;while (gap > 1){gap = gap / 2;	//调整希尔增量int i = 0;for (i = 0; i < size - gap; i++)	//从0遍历到size-gap-1{int end = i;int temp = arr[end + gap];while (end >= 0){if (arr[end] > temp){arr[end + gap] = arr[end];end -= gap;}else{break;}}arr[end + gap] = temp;	//以 end+gap 作为插入位置}}
}

希尔排序的时间复杂度:

希尔排序的时间复杂度不好计算,因为gap的取值方法很多,导致很难去计算,因此在好些书中给出的希尔排序的时间复杂度都不固定:

 

1e38ca2f0beb4bebb4be6a06a8edcabf.png

 

时间复杂度:O(n^1.3)

稳定性:不稳定

 

 

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

verilog学习笔记(1)module实例化

兜兜转转又回来学硬件了&#xff0c;哎&#xff0c;命啊&#xff01; 我的答案&#xff08;有bug&#xff09;&#xff1a; module top_module ( input a, input b, output out );wire w1;wire w2;wire w3;mod_a mod_a_inst1(.in1(w1),.in2(w2),.out(w3) );assign w1 a…

基于微信小程序的房屋租赁系统设计与实现(源码+lw+部署文档+讲解等)

文章目录 前言运行环境说明用户微信小程序端的主要功能有&#xff1a;户主微信小程序端的主要功能有&#xff1a;管理员的主要功能有&#xff1a;具体实现截图详细视频演示为什么选择我自己的网站自己的小程序&#xff08;小蔡coding&#xff09;有保障的售后福利 代码参考论文…

解决 Github port 443 : Timed out

解决方法 打开代理页面 打开 设置 --> 网络与Internet --> 查找代理 记录下当前系统代理的 IP 地址和端口号 如上图所示&#xff0c;地址与端口号为&#xff1a;127.0.0.1:7890 注意修改成自己的IP和端口号 git config --global http.proxy http://127.0.0.1:7890 gi…

Spring面试题12:Spring中IOC的优缺点是什么?IOC依赖注入方式有哪些

该文章专注于面试,面试只要回答关键点即可,不需要对框架有非常深入的回答,如果你想应付面试,是足够了,抓住关键点 面试官:Spring中IOC的优缺点是什么? IOC(Inversion of Control,控制反转)是Spring框架的一个重要特性,它实现了对象的创建和依赖关系的管理的反转。…

【Linux】Linux环境配置安装

目录 一、双系统&#xff08;特别不推荐&#xff09; 安装双系统的缺点&#xff1a; 安装双系统优点&#xff08;仅限老手&#xff09;&#xff1a; 二、虚拟机centos7镜像&#xff08;较为推荐推荐&#xff09; 虚拟机的优点&#xff1a; 虚拟机的缺点&#xff1a; ​ …

6年Android开发前10月的总结,写给正在求职的安卓开发

进入大厂工作对许多人来说已经是一种挑战&#xff0c;但只要充分准备&#xff0c;很多问题都可以逐步解决。当然&#xff0c;运气也起到了一定的作用&#xff0c;但最终还是与自身的努力密不可分。运气是实力的一部分&#xff0c;因为自助者天助。 每到10月进行总结时&#xff…

数据结构与算法(二)

文章目录 数据结构与算法(二)1 时间复杂度、空间复杂度、排序算法和二分法1.1 简单的排序算法1.2 二分查找2 异或运算、进一步认识对数器的重要性2.1 不用额外变量交换两个数的值2.2 不用额外变量交换数组中两个数的值2.3 一个数组中有一种数出现了奇数次,其他数都出现了偶数…

读写分离MySQL

利用Mycat控制后台数据库的读写分离和负载均衡 利用主从复制思想,实现读写分离,主库写,从库读 从库最好不要写,因为从库写入的数据不能同步到主库,只有主库写的数据才能同步到从库 balance属性值对应的含义(负载均衡) 一主一从读写分离的弊端 主节点Master宕机以后,业务系统…

docker 操作redis

1查看容器 2进入容器 exec表示在运行的容器中执行命令it表示以终端交互的方式执行命令/bin/bash表示需要指定的命令 3进入容器后可通过redis-cli命令连接容器内的redis服务器&#xff0c;可通过set创建变量&#xff0c;get获取变量的值 4key * 查看所有key 通过ping 查看redi…

【深度学习实验】前馈神经网络(final):final

目录 一、实验介绍 二、实验环境 1. 配置虚拟环境 2. 库版本介绍 三、实验内容 0. 导入必要的工具包 1. 构建数据集&#xff08;IrisDataset&#xff09; 2. 构建模型&#xff08;FeedForward&#xff09; a. __init__(初始化) b. forward(前向传播) 3.整合训练、评估…

golang优先级坑

看如下代码&#xff0c;我本以为a1, a2是相同的 package mainimport "fmt"func main() {b, c, d : 1, 0, 1a1 : b ^ c&(^d) // 1 ^a2 : c ^ b&(^d) // 0 ^fmt.Println(a1, a2) // 1 0 }但结果却是不同的&#xff0c;在golang中&的优先级^和&#xff5c;…

罗德里格斯公式

1.点乘 A ⃗ ⋅ B ⃗ ∣ A ⃗ ∣ ∣ B ⃗ ∣ c o s ⟨ A ⃗ , B ⃗ ⟩ \vec{A} \cdot \vec{B} \left | \vec{A} \right | \left | \vec{B} \right | cos\left \langle \vec{A}, \vec{B} \right \rangle A ⋅B ​A ​ ​B ​cos⟨A ,B ⟩ 对应几何意义&#xff1a;向量 A ⃗…

众佰诚:抖音店铺开网店前期需要投入多少

随着互联网的迅猛发展&#xff0c;电子商务已经成为了商业领域中的一股不可忽视的力量。而在电子商务中&#xff0c;抖音店铺已经成为了一个备受关注的平台&#xff0c;吸引了众多创业者和商家的关注。那么&#xff0c;在开设抖音店铺并转型为网店之前&#xff0c;究竟需要投入…

SVN的基本使用

一、SVN介绍 SVN&#xff08;Subversion&#xff09;是一个开源的版本控制系统&#xff0c;它专门用于管理文件和目录的变更。SVN 提供了一种集中式的版本控制方案&#xff0c;其中有一个中央仓库存储所有文件的历史记录和变更。 SVN使用方式相对简单&#xff0c;可以通过命令…

ROS 基础教程

欢迎访问我的博客首页。 ROS 基础教程 1.urdf 文件1.1 在 Rviz 中显示 urdf1.1.1 定义 urdf1.1.2 在 Rviz 中查看 urdf 1.2 在 Gazebo 中显示 urdf1.2.1 定义 urdf1.2.2 在 Gazebo 中查看 urdf 2.建图-仿真2.1 模型 1.urdf 文件 假设我们的工作空间是 ws_ros。我们自己实现的包…

有效保护敏感数据的最佳实践

在当今数据驱动的环境中&#xff0c;数据就是力量&#xff0c;组织仍然高度关注如何利用其数据进行 BI、分析和其他业务驱动计划。 事实上&#xff0c;最近的研究表明&#xff0c;数据领导者的主要动机是对高质量分析洞察的需求&#xff0c;而不是合规性。 然而&#xff0c;…

Centos7原生hadoop环境,搭建Impala集群和负载均衡配置

Centos7原生hadoop环境&#xff0c;搭建Impala集群和负载均衡配置 impala介绍 Impala集群包含一个Catalog Server (Catalogd)、一个Statestore Server (Statestored) 和若干个Impala Daemon (Impalad)。Catalogd主要负责元数据的获取和DDL的执行&#xff0c;Statestored主要负…

greenhills compiler 2021.1.4 for x86 Linux

greenhills compiler 2021.1.4 for x86 Linux 2692407267qq.com&#xff0c;更多内容请见http://user.qzone.qq.com/2692407267/

ipad触控笔有必要买原装吗?ipad2023手写笔推荐

目前&#xff0c;在无纸教学、无纸办公的大背景下&#xff0c;电容笔得到了广泛的关注。只是&#xff0c;对于这两支电容笔的不同之处&#xff0c;不少人并不是很清楚。其实这两种电容笔都很好区分&#xff0c;第一种是主动电容笔&#xff0c;也就是我们常用的电容式屏幕&#…

JavaWeb开发-06-SpringBootWeb-MySQL

一.MySQL概述 1.安装、配置 官网下载地址&#xff1a;https://dev.mysql.com/downloads/mysql/ 2.数据模型 3.SQL简介 二.数据库设计-DDL 1.数据库 官网&#xff1a;http:// https://www.jetbrains.com/zh-cn/datagrip/ 2.表&#xff08;创建、查询、修改、删除&#xff09; #…