算法基础 | 常用排序算法小结(一)

简介: 算法基础 | 常用排序算法小结

日常吹水

说到这个算法,

可能瞬间大家就觉得那些灰机昏膏素什么的比这个生动活泼多了。

那么,正走在算法之路上的你,

是否还在苦苦寻求修仙之路?

是否被各种排序算法欺负得苦不堪言?

那还等什么,快进来看看

带你全程装逼加一路向西!

刺不刺激?高不高能?

微信图片_20220420152123.jpg


内容提要:

*排序常用术语介绍

*冒泡排序

*选择排序

*插入排序

*希尔排序

*归并排序

*快速 排序

排序基础知识


⚫排序的定义

将杂乱无章的数据元素,通过一定的方法按关键字顺序排列的过程叫做排序。说得再通俗点,比如将一个班的人(数据元素)按照身高(关键字)站位,高的站前面,矮的站后面咯。



⚫ 排序的分类

排序可分为内排序和外排序。

所谓内排序就是所有的数据和操作都在内存中完成。

而外排序就是说需要排序的数据太大,无法全部塞进内存,需要在内存和外存之间多次数据交换才能完成的排序。


⚫算法优劣的术语说明

⚫稳定:如果Ai=Aj,开始Ai在Aj前面,排完序之后Ai依然在Aj前面。

⚫不稳定:

如果Ai=Aj,开始Ai在Aj前面,而排完序以后Ai有可能跑到Aj后面去了。

⚫时间复杂度:一个算法执行完所消耗的时间。

⚫空间复杂度:执行一个算法需要消耗的内存空间大小。


⚫常见算法的复杂度及稳定性

微信图片_20220420152130.jpg

好了看完上面一堆头(dan)疼的术语介绍,

接下来将为大家介绍几种常用的内部排序算法,

开始我们的表演。

微信图片_20220420152137.jpg1

冒泡排序(Bubble Sort)


⚫常规冒泡排序

冒泡排序算是比较好理解的了。想小编当年入门的时候,就是仰仗着冒泡大法,从此踏入红尘,一去不返……呃这个扯远了,为什么叫冒泡呢?这个后面再解释。为了更好的说明问题,还是用一个数组A[n],以升序(降序方法一样)为例,来给大家一一讲解。


⚫基本原理:


1)从序列的最左边开始,将两两相邻的两个元素(例如A[0]和A[1], A[1]和A[2], A[2]和A[3]等等)进行比较。将小的放左边,将大的放右边。例如A[i] > A[i+1],那么就交换A[i]和A[i+1]的位置。那么经过一轮比较交换以后,A[n]里的值必然是A[0]~A[n]中的最大值。


2) 对剩下的元素A[0]~A[n-1]也进行上述操作。完成后A[n-1]里面存的就是A[0]~A[n-1]中的最大值。


3) 不断对剩下的元素进行上述操作,直到剩下元素只有A[0]时,排序完成。


看不懂嘛?那来试试图片吧:

微信图片_20220420152142.jpg

好了,讲完了基本原理,来看看具体代码是如何实现的吧。

微信图片_20220420152146.jpg

可以看到,在冒泡后,相等元素的位置并不会改变。因此,冒泡算法是稳定的。


冒泡排序改进版

此方法可称为定向冒泡排序,它和冒泡排序的不同之处在于,定向冒泡从左到右把最大数搬到最后面的时候,再反向从右往左把最小值搬到最左边。这种方法稍微比传统冒泡好上那么一丢丢。具体实施看代码。

微信图片_20220420152151.jpg

不理解嘛?没关系,小编还为大家准备了动态图。

微信图片_20220420152156.gif

定向冒泡的优势,比如对序列{4, 5, 6, 7, 8, 2}排序,传统冒泡要访问5次序列,而定向冒泡排序只需要访问一次就OK了。


相关文章
|
1月前
|
机器学习/深度学习 算法 安全
【无人机三维路径规划】基于非支配排序的鲸鱼优化算法NSWOA与多目标螳螂搜索算法MOMSA求解无人机三维路径规划研究(Matlab代码实现)
【无人机三维路径规划】基于非支配排序的鲸鱼优化算法NSWOA与多目标螳螂搜索算法MOMSA求解无人机三维路径规划研究(Matlab代码实现)
|
1月前
|
机器学习/深度学习 运维 算法
基于非支配排序遗传算法NSGAII的综合能源优化调度(Matlab代码实现)
基于非支配排序遗传算法NSGAII的综合能源优化调度(Matlab代码实现)
184 0
基于非支配排序遗传算法NSGAII的综合能源优化调度(Matlab代码实现)
|
1月前
|
机器学习/深度学习 算法 安全
【无人机三维路径规划】多目标螳螂搜索算法MOMSA与非支配排序的鲸鱼优化算法NSWOA求解无人机三维路径规划研究(Matlab代码实现)
【无人机三维路径规划】多目标螳螂搜索算法MOMSA与非支配排序的鲸鱼优化算法NSWOA求解无人机三维路径规划研究(Matlab代码实现)
|
2月前
|
机器学习/深度学习 算法 安全
【无人机3D路径规划】基于非支配排序遗传算法NSGAII的无人机3D路径规划研究(Matlab代码实现)
【无人机3D路径规划】基于非支配排序遗传算法NSGAII的无人机3D路径规划研究(Matlab代码实现)
156 1
|
1月前
|
机器学习/深度学习 算法 安全
【微电网】【创新点】基于非支配排序的蜣螂优化算法NSDBO求解微电网多目标优化调度研究(Matlab代码实现)
【微电网】【创新点】基于非支配排序的蜣螂优化算法NSDBO求解微电网多目标优化调度研究(Matlab代码实现)
|
2月前
|
机器学习/深度学习 算法 安全
【优化调度】基于matlab非支配排序遗传算法求解车辆充电调度优化问题研究(Matlab代码实现)
【优化调度】基于matlab非支配排序遗传算法求解车辆充电调度优化问题研究(Matlab代码实现)
|
1月前
|
存储 算法 搜索推荐
软考算法破壁战:从二分查找到堆排序,九大排序核心速通指南
专攻软考高频算法,深度解析二分查找、堆排序、快速排序核心技巧,对比九大排序算法,配套动画与真题,7天掌握45%分值模块。
85 1
软考算法破壁战:从二分查找到堆排序,九大排序核心速通指南
|
1月前
|
供应链 算法 Java
【柔性作业车间调度问题FJSP】基于非支配排序的多目标小龙虾优化算法求解柔性作业车间调度问题FJSP研究(Matlab代码实现)
【柔性作业车间调度问题FJSP】基于非支配排序的多目标小龙虾优化算法求解柔性作业车间调度问题FJSP研究(Matlab代码实现)
|
27天前
|
机器学习/深度学习 算法 安全
【无人机三维路径规划】基于非支配排序的鱼鹰优化算法NSOOA求解无人机三维路径规划研究(Matlab代码实现)
【无人机三维路径规划】基于非支配排序的鱼鹰优化算法NSOOA求解无人机三维路径规划研究(Matlab代码实现)
|
2月前
|
传感器 并行计算 算法
【无人机编队】基于非支配排序遗传算法II NSGA-II高效可行的无人机离线集群仿真研究(Matlab代码实现)
【无人机编队】基于非支配排序遗传算法II NSGA-II高效可行的无人机离线集群仿真研究(Matlab代码实现)
195 3

热门文章

最新文章