
数据结构中排序和查找各种时间复杂度
(1)冒泡排序
冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较,交换也发生在这两个元素之间。所以相同元素的前后顺序并没有改变,所以冒泡排序是一种稳定排序算法。
(2)选择排序
选择排序是给每个位置选择当前元素最小的,比如给第一个位置选择最小的。…… 例子说明好多了。序列5 8 5 2 9, 我们知道第一遍选择第1个元素5会和2交换,那么原序列中2个5的相对前后顺序就被破坏了, 所以选择排序不稳定的排序算法
(3)插入排序
插入排序是在一个已经有序的小序列的基础上,一次插入一个元素。比较是从有序序列的末尾开始,也就是想要插入的元素和已经有序的最大者开始比起,如果比它大则直接插入在其后面,否则一直往前找直到找到它该插入的位置。如果和插入元素相等,那么插入元素把想插入的元素放在相等元素的后面。所以,相等元素的前后顺序没有改变。所以插入排序是稳定的。
(4)快速排序
快速排序有两个方向,左边的i下标一直往右走(往后),当a[i] <= a[center_index],其中center_index是中枢元素的数组下标,一般取为数组第0个元素。而右边的j下标一直往左走(往前),当a[j] > a[center_index]。如果i和j都走不动了,i <= j, 交换a[i]和a[j],重复上面的过程,直到i>j。 交换a[j]和a[center_index],完成一趟快速排序。在中枢元素和a[j]交换的时候,很有可能把前面的元素的稳定性打乱,比如序列为 5 3 3 4 3 8 9 10 11, 现在中枢元素5和3(第5个元素,下标从1开始计)交换就会把元素3的稳定性打乱,所以快速排序是一个不稳定的排序算法。(不稳定发生在中枢元素和a[j]交换的时刻)
(5)归并排序
归并排序是把序列递归地分成短序列,递归出口是短序列只有1个元素(认为直接有序)或者2个序列(1次比较和交换),然后把各个有序的段序列合并成一个有序的长序列。不断合并直到原序列全部排好序。相等时不发生交换。所以,归并排序也是稳定的排序算法。
(6)基数排序
基数排序是按照低位先排序,然后收集;再按照高位排序,然后再收集;依次类推,直到最高位。有时候有些属性是有优先级顺序的,先按低优先级排序,再按高优先级排序,最后的次序就是高优先级高的在前,高优先级相同的低优先级高的在前。基数排序基于分别排序,分别收集,所以其是稳定的排序算法。
(7)希尔排序(shell)
希尔排序是按照不同步长对元素进行插入排序,当刚开始元素很无序的时候,步长最大,所以插入排序的元素个数很少,速度很快;当元素基本有序了,步长很小,插入排序对于有序的序列效率很高。所以,希尔排序的时间复杂度会比o(n^2)好一些。由于多次插入排序,我们知道一次插入排序是稳定的,不会改变相同元素的相对顺序,但在不同的插入排序过程中,相同的元素可能在各自的插入排序中移动,最后其稳定性就会被打乱,所以shell排序是不稳定的。
(8)堆排序
我们知道堆的结构是节点i的孩子为2*i和2*i+1节点,大顶堆要求父节点大于等于其2个子节点,小顶堆要求父节点小于等于其2个子节点。在一个长为n的序列,堆排序的过程是从第n/2开始和其子节点共3个值选择最大(大顶堆)或者最小(小顶堆),这3个元素之间的选择当然不会破坏稳定性。但当为n/2-1,
n/2-2,
...1这些个父节点选择元素时,就会破坏稳定性。有可能第n/2个父节点交换把后面一个元素交换过去了,而第n/2-1个父节点把后面一个相同的元素没有交换,那么这2个相同的元素之间的稳定性就被破坏了。所以,堆排序是不稳定的排序算法
一、排序
排序法 平均时间 最差情形 稳定度 额外空间 备注
冒泡 O(n2) O(n2) 稳定 O(1) n小时较好
交换 O(n2) O(n2) 不稳定 O(1) n小时较好
选择 O(n2) O(n2) 不稳定 O(1) n小时较好
插入 O(n2) O(n2) 稳定 O(1) 大部分已排序时较好
Shell O(nlogn) O(ns) 1
快速 O(nlogn) O(n2) 不稳定 O(nlogn) n大时较好
归并 O(nlogn) O(nlogn) 稳定 O(1) n大时较好
堆 O(nlogn) O(nlogn) 不稳定 O(1) n大时较好
基数 O(logRB) O(logRB) 稳定 O(n) B是真数(0-9),R是基数(个十百)
二、查找
未写……
三 树图
克鲁斯卡尔算法的时间复杂度为O(eloge)
普里姆算法的时间复杂度为O(n2)
迪杰斯特拉算法的时间复杂度为O(n2)
拓扑排序算法的时间复杂度为O(n+e)
关键路径算法的时间复杂度为O(n+e)
数据分析咨询请扫描二维码
若不方便扫码,搜微信号:CDAshujufenxi
解析 F 边界检验:协整分析中的实用工具 在计量经济学的时间序列分析中,判断变量之间是否存在长期稳定的均衡关系(即协整关系) ...
2025-08-05大数据时代的隐患:繁荣背后的隐忧 当我们在电商平台浏览商品时,系统总能 “精准” 推送心仪的物品;当我们刷短视频时,算法 ...
2025-08-05CDA 数据分析师考试全解析 在当今数字化时代,数据已成为企业发展的核心驱动力,数据分析师这一职业也愈发受到重视。CDA 数据分 ...
2025-08-05CDA认证在国际市场上的认可度正在逐渐增长。CDA(Certified Data Analyst)认证,源自中国,面向全球,旨在提升数字化人才的数据 ...
2025-08-04本次活动市场价2000元,现面向会员免费开放,会员朋友更可以邀请一位非会员免费参加。 【活动目标】 ...
2025-08-04MySQL 统计连续每天数据:从业务需求到技术实现 在数据分析场景中,连续日期的数据统计是衡量业务连续性的重要手段 —— 无论是 ...
2025-08-04反向传播神经网络:突破传统算法瓶颈的革命性力量 在人工智能发展的历史长河中,传统算法曾长期主导着数据处理与模式识别领域 ...
2025-08-04CDA 数据分析师行业标准:构建数据人才的能力坐标系 在数据驱动决策成为企业核心竞争力的时代,CDA(数据分析师)行业标准作为 ...
2025-08-04评判两组数据与初始数据准确值的方法 在数据分析与研究中,我们常常会面临这样的情况:需要对通过不同方法、不同过程得到的两组 ...
2025-08-01通过 COX 回归模型诊断异常值 一、COX 回归模型概述 COX 回归模型,又称比例风险回归模型,是一种用于生存分析的统计方法。它能 ...
2025-08-01CDA 数据分析师报考条件详解:迈向专业认证的指南 在数据分析行业蓬勃发展的当下,CDA 数据分析师认证成为众多从业者提升专业 ...
2025-08-01K-S 曲线、回归与分类:数据分析中的重要工具 在数据分析与机器学习领域,K-S 曲线、回归和分类是三个核心概念与工具,它们各 ...
2025-07-31大数据时代对定性分析的影响 在大数据时代,海量、多样、高速且低价值密度的数据充斥着我们的生活与工作。而定性分析作为一 ...
2025-07-31CDA含金量分析 在数字经济与人工智能深度融合的时代,数据驱动决策已成为企业核心竞争力的关键要素。CDA(Certified Data Analys ...
2025-07-31SASEM 决策树:理论与实践应用 在复杂的决策场景中,如何从海量数据中提取有效信息并制定科学决策,是各界关注的焦点。SASEM 决 ...
2025-07-30SPSS 语法使用详解 在当今数据驱动的时代,SPSS( Statistical Package for the Social Sciences)作为一款功能强大的统计分析软 ...
2025-07-30人工智能对CDA数据分析领域的影响 人工智能对 CDA(Certified Data Analyst,注册数据分析师)数据分析领域的影响是全方位、多层 ...
2025-07-30MySQL执行计划中rows的计算逻辑:从原理到实践 MySQL 执行计划中 rows 的计算逻辑:从原理到实践 在 MySQL 数据库的查询优化中 ...
2025-07-29左偏态分布转正态分布:方法、原理与实践 左偏态分布转正态分布:方法、原理与实践 在统计分析、数据建模和科学研究中,正态分 ...
2025-07-29CDA 数据分析师的职业生涯规划:从入门到卓越的成长之路 在数字经济蓬勃发展的当下,数据已成为企业核心竞争力的重要来源,而 CD ...
2025-07-29