【排序算法】冒泡排序,选择排序,插入排序算法原理及Python代码实现

简介: 【排序算法】冒泡排序,选择排序,插入排序算法原理及Python代码实现

1.冒泡排序

1.1算法原理

从第一个元素开始,比较相邻元素的大小,如果大小顺序有误,则对调之后再进行下一个元素比较,经过这样不断交换之后,就可以找出最后一个元素的正确位置。接着再逐步进行交换,直到完成所有数据的排序关系为止。过程示意如下图:
2bb228b099984ab5b7dcb93250ebed2d.png

  • 优点:算法简单直接
  • 缺点:算法复杂度为O(n^2^)

1.2Python代码实现

def bubble_sort(lst):
    for i in range(len(lst)-1,0,-1):
        for j in range(i):
            if lst[j] > lst[j+1]:
                lst[j],lst[j+1] = lst[j+1],lst[j] # use tuple assignment

2.选择排序

2.1算法原理

第一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,然后再从剩余的未排序元素中寻找到最小(大)元素,然后放到已排序的序列的末尾。以此类推,直到全部待排序的数据元素的个数为零。过程示意如下图:
d09f4bf3e1e04361924c7575f927d06c.png

时间复杂度
选择排序的交换操作介于 0 和 (n - 1)次之间。选择排序的比较操作为 n (n - 1) / 2 次之间。选择排序的赋值操作介于 0 和 3 (n - 1) 次之间。比较次数O(n^2^),比较次数与关键字的初始状态无关,总的比较次数N=(n-1)+(n-2)+...+1=n(n-1)/2。交换次数O(n),最好情况是,已经有序,交换0次;最坏情况交换n-1次,逆序交换n/2次。交换次数比冒泡排序少多了,由于交换所需CPU时间比比较所需的CPU时间多,n值较小时,选择排序比冒泡排序快
*稳定性

选择排序是给每个位置选择当前元素最小的,比如给第一个位置选择最小的,在剩余元素里面给第二个元素选择第二小的,依次类推,直到第n-1个元素,第n个元素不用选择了,因为只剩下它一个最大的元素了。那么,在一趟选择,如果一个元素比当前元素小,而该小的元素又出现在一个和当前元素相等的元素后面,那么交换后稳定性就被破坏了。举个例子,序列5 8 5 2 9,我们知道第一遍选择第1个元素5会和2交换,那么原序列中两个5的相对前后顺序就被破坏了,所以选择排序是一个不稳定的排序算法。

  • 优点:比冒泡排序执行更少的交换
  • 缺点:最好最差的算法复杂度均为O(n^2^),算法不稳定

2.2Python代码实现

def selection_sort(lst):
    for fillslot in range(len(lst)-1,0,-1):
        position_of_max = 0
        for location in range(1,fillslot+1):
            if lst[location] > lst[position_of_max]:
                position_of_max = location
        lst[fillslot],lst[position_of_max] = lst[position_of_max],lst[fillslot]

3.插入排序

3.1算法原理

插入排序是指在待排序的元素中,假设前面n-1(其中n>=2)个数已经是排好顺序的,现将第n个数插到前面已经排好的序列中,然后找到合适自己的位置,使得插入第n个数的这个序列也是排好顺序的。按照此法对所有元素进行插入,直到整个序列排为有序的过程,称为插入排序。过程示意如下图:
c92f0092e4a04e629573bb847bbc71c4.png

时间复杂度
在插入排序中,当待排序数组是有序时,是最优的情况,只需当前数跟前一个数比较一下就可以了,这时一共需要比较N- 1次,时间复杂度为O(N)。
最坏的情况是待排序数组是逆序的,此时需要比较次数最多,总次数记为:1+2+3+…+N-1,所以,插入排序最坏情况下的时间复杂度为O(n^2^)。
平均来说,A[1..j-1]中的一半元素小于A[j],一半元素大于A[j]。插入排序在平均情况运行时间与最坏情况运行时间一样,是输入规模的二次函数。

  • 优点:比冒泡排序执行更少的交换,算法稳定
  • 缺点:算法复杂度为O(n^2^)

3.2Python代码实现

def insertion_sort(lst):
    for insert_num in range(1,len(lst)):
        position = insert_num - 1
        while lst[insert_num] < lst[position] and position >= 0:
            lst[position],lst[insert_num] = lst[insert_num],lst[position]
            insert_num -= 1
            position -= 1
相关文章
|
10天前
|
存储 缓存 算法
如何通过优化算法和代码结构来提升易语言程序的执行效率?
如何通过优化算法和代码结构来提升易语言程序的执行效率?
|
11天前
|
搜索推荐
插入排序算法的讲解和代码
【10月更文挑战第12天】插入排序是一种基础的排序算法,理解和掌握它对于学习其他排序算法以及数据结构都具有重要意义。你可以通过实际操作和分析,进一步深入了解插入排序的特点和应用场景,以便在实际编程中更好地运用它。
|
3天前
|
缓存 分布式计算 监控
优化算法和代码需要注意什么
【10月更文挑战第20天】优化算法和代码需要注意什么
13 0
|
5天前
|
算法 安全 数据安全/隐私保护
基于game-based算法的动态频谱访问matlab仿真
本算法展示了在认知无线电网络中,通过游戏理论优化动态频谱访问,提高频谱利用率和物理层安全性。程序运行效果包括负载因子、传输功率、信噪比对用户效用和保密率的影响分析。软件版本:Matlab 2022a。完整代码包含详细中文注释和操作视频。
|
23天前
|
机器学习/深度学习 算法 数据安全/隐私保护
基于MSER和HOG特征提取的SVM交通标志检测和识别算法matlab仿真
### 算法简介 1. **算法运行效果图预览**:展示算法效果,完整程序运行后无水印。 2. **算法运行软件版本**:Matlab 2017b。 3. **部分核心程序**:完整版代码包含中文注释及操作步骤视频。 4. **算法理论概述**: - **MSER**:用于检测显著区域,提取图像中稳定区域,适用于光照变化下的交通标志检测。 - **HOG特征提取**:通过计算图像小区域的梯度直方图捕捉局部纹理信息,用于物体检测。 - **SVM**:寻找最大化间隔的超平面以分类样本。 整个算法流程图见下图。
|
2天前
|
人工智能 算法 数据安全/隐私保护
基于遗传优化的SVD水印嵌入提取算法matlab仿真
该算法基于遗传优化的SVD水印嵌入与提取技术,通过遗传算法优化水印嵌入参数,提高水印的鲁棒性和隐蔽性。在MATLAB2022a环境下测试,展示了优化前后的性能对比及不同干扰下的水印提取效果。核心程序实现了SVD分解、遗传算法流程及其参数优化,有效提升了水印技术的应用价值。
|
3天前
|
机器学习/深度学习 算法 数据安全/隐私保护
基于贝叶斯优化CNN-LSTM网络的数据分类识别算法matlab仿真
本项目展示了基于贝叶斯优化(BO)的CNN-LSTM网络在数据分类中的应用。通过MATLAB 2022a实现,优化前后效果对比明显。核心代码附带中文注释和操作视频,涵盖BO、CNN、LSTM理论,特别是BO优化CNN-LSTM网络的batchsize和学习率,显著提升模型性能。
|
8天前
|
存储
基于遗传算法的智能天线最佳阵列因子计算matlab仿真
本课题探讨基于遗传算法优化智能天线阵列因子,以提升无线通信系统性能,包括信号质量、干扰抑制及定位精度。通过MATLAB2022a实现的核心程序,展示了遗传算法在寻找最优阵列因子上的应用,显著改善了天线接收功率。
|
10天前
|
监控 算法 数据安全/隐私保护
基于三帧差算法的运动目标检测系统FPGA实现,包含testbench和MATLAB辅助验证程序
本项目展示了基于FPGA与MATLAB实现的三帧差算法运动目标检测。使用Vivado 2019.2和MATLAB 2022a开发环境,通过对比连续三帧图像的像素值变化,有效识别运动区域。项目包括完整无水印的运行效果预览、详细中文注释的代码及操作步骤视频,适合学习和研究。
|
18天前
|
算法
基于粒子群算法的分布式电源配电网重构优化matlab仿真
本研究利用粒子群算法(PSO)优化分布式电源配电网重构,通过Matlab仿真验证优化效果,对比重构前后的节点电压、网损、负荷均衡度、电压偏离及线路传输功率,并记录开关状态变化。PSO算法通过迭代更新粒子位置寻找最优解,旨在最小化网络损耗并提升供电可靠性。仿真结果显示优化后各项指标均有显著改善。