logo头像

不忘初心,奋力前行

常用排序算法复杂度和稳定性情况总结

排序算法 平均时间复杂度 最好情况 最坏情况 空间复杂度 稳定性 冒泡排序 O(n2) O(n) O(n2) O(1) 稳定 选择排序 O(n2) O(n2) O(n2) O(1) 不稳定 插入排序 O(n2) O(n) O(n2) ...

KMP算法的简单理解

总结一些在网上看到的关于KMP算法的简单理解,目前我的理解还很初步,很多东西还似懂非懂,目前先贴下来,期待以后慢慢懂。 KMP算法的基本原理假设字符串S=BBC ABCDAB ABCDABCDABDE,搜索词P=ABCDABD。那么我...

中国大学MOOC-陈越、何钦铭-数据结构-2018春期末考试

一、判断题 1-1若用平方探测法解决冲突,则插入新元素时,若散列表容量为质数,插入就一定可以成功。(2分) F 1-2对N个不同的数据采用冒泡排序进行从大到小的排序,当元素基本有序时交换元素次数肯定最多。(2分) F 1-3_n_!是...

数据结构【浙江大学】(第11节)整理

第十一讲:散列查找11.1 散列表11.1.1 散列的基本思路编译处理时,设计变量及属性的管理: (1)插入:新变量定义。 (2)查找:变量的引用。 编译处理中对变量管理:动态查找问题。 利用查找树进行变量管理,由于两个变量名(字符串...

数据结构【浙江大学】(第10节)整理

第十讲:排序(下)10.1 快速排序10.1.1 算法概述策略:分而治之。 下面举个例子,假如一组数为13/81/92/43/65/31/57/26/75/0,我们对其进行排序。那么首先选择出一个主元,这里我们选择为65,那么将这组数...

数据结构【浙江大学】(第9节)整理

第九节:排序(上)9.1 概述对于之后应用到的一些说明: (1)void X_Sort(ElementType A[], int N) X为排序名称。 ①大多数情况下,为了简单起见,讨论从小到大的整数排序。 ②默认N为正整数。 ③只讨...

数据结构【浙江大学】(第8节)整理

第八讲:图(下)8.1 最小生成树问题8.1.1 最小生成树(Minimum Spanning Tree) 如图1所示。 图1 它是一棵树:无回路;|V|个顶点一定有|V|-1条边; 它是生成树:包含全部顶点;|V|-1条边都在图...