数据结构与算法——简单排序-冒泡排序、插入排序,时间复杂度下界(图示、代码、时间复杂度、定理)

简介: 数据结构与算法——简单排序-冒泡排序、插入排序,时间复杂度下界(图示、代码、时间复杂度、定理)

简单排序

概述

排序函数一般的命名:

void X_Sort(ElementType A[], int N)

X为具体的排序名称,例如:冒泡、插入、希尔等等;


A[ ] 为要排序的主体;N为要排序的数据个数。 (N是正整数)


  • 大多数情况下,为简单起见,讨论从小到大的整数排序
  • 只讨论基于比较的排序(即 >  =  < 有定义)
  • 只讨论内部排序(即数据全部存在于内存内,没有内存外部的数据需要排序,相对应的为外部排序)
  • 稳定性:任意两个相等的数据,排序前后的相对位置不发生改变
  • 没有一种排序是任何情况下都表现最好的

冒泡排序

图示

 

代码 (C语言)

void Bubble_Sort(ElementType A[], int N)
{
    for(P = N -1; P >= 0; P--)
    {
        flag = 0;   //用于判断排序是否需要继续
        for(i = 0; i < P; i ++)  //一趟冒泡
        {
            if(A[i] > A[i+1])
            {
                Swap(A[i],A[i+1]);
                flag = 1;        
            }
        }
        if(flag = 0) break;  //如果全部扫描之后没有元素进行交换,则说明不需要再进行排序了,所以直接退出
    }  
}

时间复杂度

最好情况:顺序

最坏情况:逆序

插入排序

图示

 

代码(C语言)

void InsertionSort( ElementType A[], int N )
{ /* 插入排序 */
     int P, i;
     ElementType Tmp;
     
     for ( P=1; P<N; P++ ) {
         Tmp = A[P]; /* 取出未排序序列中的第一个元素*/
         for ( i=P; i>0 && A[i-1]>Tmp; i-- )
             A[i] = A[i-1]; /*依次与已排序序列中元素比较并右移*/
         A[i] = Tmp; /* 放进合适的位置 */
     }
}

时间复杂度

最好情况:顺序

最坏情况:逆序

问:给定初始序列{ 34,8,64,51,32,21 },冒泡排序和插入排序分别需要多少次元素交换才能完成?

把心中的答案记下来,我们先往下看:

时间复杂度下界

  • 对于下标i < j,如果A[ i ] > A[ j ],则称(i,j)是一对逆序对(inversion)
  • 序列{ 34,8,64,51,32,21 }中总共有九对逆序对

分别为:(34,8)(34,32)(34,21)(64,51)(64,32)(64,21)(51,32)(51,21)(32,21)


交换2个相邻元素正好消去1个逆序对

故而上面那道题目的答案是9,冒泡排序和插入排序的交换元素次数都为9次;因为序列中有9对逆序对,两个简单排序都是以交换相邻元素为主的,所以次数一致。


而如果冒泡和插入排序的元素个数为N,逆序对的个数为I,那么时间复杂度就为

如果序列基本有序,则冒泡、插入排序简单且高效。

定理

  1. 任意N个不同元素组成的序列平均具有N(N-1)/4个逆序对
  2. 任何仅以交换相邻两元素来排序的算法,其平均时间复杂度为

指的是下界)

这一意味着:要提高算法效率,我们必须:

  • 每次要消去不止1个逆序对!
  • 每次交换相隔较远的2个元素!

交换相隔较远的2个元素就有可能一次性消去不止1个逆序对

目录
相关文章
|
11天前
|
搜索推荐
【数据结构常见七大排序(三)上】—交换排序篇【冒泡排序】And【快速排序】
【数据结构常见七大排序(三)上】—交换排序篇【冒泡排序】And【快速排序】
【数据结构常见七大排序(三)上】—交换排序篇【冒泡排序】And【快速排序】
|
11天前
|
搜索推荐
【数据结构常见七大排序(二)】—选择排序篇【直接选择排序】And【堆排序】
【数据结构常见七大排序(二)】—选择排序篇【直接选择排序】And【堆排序】
|
11天前
|
搜索推荐 测试技术
【数据结构常见七大排序(一)】—插入排序篇【直接插入排序】And【希尔排序】
【数据结构常见七大排序(一)】—插入排序篇【直接插入排序】And【希尔排序】
|
21天前
|
算法 PHP
【php经典算法】冒泡排序,冒泡排序原理,冒泡排序执行逻辑,执行过程,执行结果 代码
【php经典算法】冒泡排序,冒泡排序原理,冒泡排序执行逻辑,执行过程,执行结果 代码
14 1
|
27天前
|
算法 Java 调度
Java数据结构与算法:拓扑排序
Java数据结构与算法:拓扑排序
|
5天前
|
传感器 算法
基于无线传感器网络的MCKP-MMF算法matlab仿真
MCKP-MMF算法是一种启发式流量估计方法,用于寻找无线传感器网络的局部最优解。它从最小配置开始,逐步优化部分解,调整访问点的状态。算法处理访问点的动态影响半径,根据带宽需求调整,以避免拥塞。在MATLAB 2022a中进行了仿真,显示了访问点半径请求变化和代价函数随时间的演变。算法分两阶段:慢启动阶段识别瓶颈并重设半径,随后进入周期性调整阶段,追求最大最小公平性。
基于无线传感器网络的MCKP-MMF算法matlab仿真
|
1天前
|
传感器 机器学习/深度学习 算法
基于GA遗传算法的WSN网络节点覆盖优化matlab仿真
本研究应用遗传优化算法于无线传感器网络(WSN),优化节点布局与数量,以最小化节点使用而最大化网络覆盖率。MATLAB2022a环境下,算法通过选择、交叉与变异操作,逐步改进节点配置,最终输出收敛曲线展现覆盖率、节点数及适应度值变化。无线传感器网络覆盖优化问题通过数学建模,结合遗传算法,实现目标区域有效覆盖与网络寿命延长。算法设计中,采用二进制编码表示节点状态,适应度函数考量覆盖率与连通性,通过选择、交叉和变异策略迭代优化,直至满足终止条件。
|
7天前
|
机器学习/深度学习 算法 数据挖掘
基于改进K-means的网络数据聚类算法matlab仿真
**摘要:** K-means聚类算法分析,利用MATLAB2022a进行实现。算法基于最小化误差平方和,优点在于简单快速,适合大数据集,但易受初始值影响。文中探讨了该依赖性并通过实验展示了随机初始值对结果的敏感性。针对传统算法的局限,提出改进版解决孤点影响和K值选择问题。代码中遍历不同K值,计算距离代价,寻找最优聚类数。最终应用改进后的K-means进行聚类分析。
|
9天前
|
算法 数据安全/隐私保护
基于GA遗传优化算法的Okumura-Hata信道参数估计算法matlab仿真
在MATLAB 2022a中应用遗传算法进行无线通信优化,无水印仿真展示了算法性能。遗传算法源于Holland的理论,用于全局优化,常见于参数估计,如Okumura-Hata模型的传播损耗参数。该模型适用于150 MHz至1500 MHz的频段。算法流程包括选择、交叉、变异等步骤。MATLAB代码执行迭代,计算目标值,更新种群,并计算均方根误差(RMSE)以评估拟合质量。最终结果比较了优化前后的RMSE并显示了SNR估计值。
25 7
|
6天前
|
算法
基于粒子群优化的图像融合算法matlab仿真
这是一个基于粒子群优化(PSO)的图像融合算法,旨在将彩色模糊图像与清晰灰度图像融合成彩色清晰图像。在MATLAB2022a中测试,算法通过PSO求解最优融合权值参数,经过多次迭代更新粒子速度和位置,以优化融合效果。核心代码展示了PSO的迭代过程及融合策略。最终,使用加权平均法融合图像,其中权重由PSO计算得出。该算法体现了PSO在图像融合领域的高效性和融合质量。