具体代码请看:NDKPractice项目的datastructure 1. 稳定排序和不稳定排序: 稳定排序概念:通俗地讲就是能保证排序前两个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序相同。在简单形式化一下,如果Ai = Aj,Ai原来在位置前,排序后Ai还是要在Aj位置前。 代表: 稳定排序:冒泡、插入、选择、归并 不稳定排序:希尔、快速排序、堆排序 2. 归并排序 每次合并操...

冒泡优化、插入和希尔排序 1. 冒泡排序优化 2. 插入排序 3. 插入排序优化 4.对比插入排序和选择排序 5.希尔排序(插入排序优化的再次优化) 具体代码请看:NDKPractice项目的datastructure 1. 冒泡排序优化 引用个冒泡排序优化 的链接 思维: 特点:适用于数组中大部分是排好序的数组,如果大部分都没排好序,那么花费的时间比原来的冒泡排序还多 2. 插入排序 特点:适用...

冒泡、选择排序 知识点: 1. 宏定义`Log`打印 2. rand() 随机 3. 冒泡排序 4. 选择排序 具体代码请看:NDKPractice项目的datastructure 知识点: 1. 宏定义Log打印 2. rand() 随机 3. 冒泡排序 思想:相邻两个数进行比较,如果前面的比后面的大,就进行交换,否则不需要交换 复杂度:时间复杂度和空间复杂度都是 O(n的平方) ,可以优化的 ...

二叉树序列化、优先级队列和堆排序 1. 二叉树的序列化和反序列化 1.1 序列化 1.2 反序列化 2. 优先级队列 3. 堆排序(升序采用大根堆,降序采用小根堆) 具体代码请看:NDKPractice项目的datastructure36heapsorting 1. 二叉树的序列化和反序列化 1.1 序列化 1.2 反序列化 2. 优先级队列 数组转二叉树规律(前提:index 从 1 开始): ...

二叉树常见操作、平衡二叉树 1. 二叉树分类 `完全二叉树`: `满二叉树`: 1.1 常用的操作树: 2. 二叉树的遍历 2.1 前序遍历 2.2 中序遍历 2.3 后序遍历 2.4 层序遍历 3. 根据`前序和中序遍历` 或 `后序和中序遍历`还原二叉树 4. 二叉树的深度: 5. 判断是否是平衡二叉树 具体代码请看:NDKPractice项目的datastructure35binarytre...

网站上的敏感词过滤是怎么实现的呢? 实际上,这些功能最基本的原理就是字符串匹配算法,也就是通过维护一个敏感词的字典,当用户输入一段文字内容后,通过字符串匹配算法来检查用户输入的内容是否包含敏感词。 BF、RK、BM、KMP 算法都是针对只有一个模式串的字符串匹配算法,而要实现一个高性能的敏感词过滤系统,就需要用到多模式匹配算法了。 1. 基于单模式和 Trie 树实现的敏感词过滤 多模式匹配算法,...

引言 栈与队列两种实现方法:数组及链表。 数组实现采用“基于下标访问”( Index-based access)的模式,而链表实现则是基于“节点”( Node)或“位置”( Position)的概念。无论是哪种实现方式,栈与队列的每一基本操作都可以在常数时间内完成。 栈ADT POP:移除栈定元素 操作 描述 push(x) ...

二项队列

数据结构和算法

  

2019-12-23 09:09:23

更多内容参考这篇文章 数据结构–二项队列分析及实现 众所周知,只需要一个数组,我们就能实现二叉堆。二叉堆的Insert,DeleteMin均能以 O(logN) 执行,BuildHeap 和 Merge 能够以 O(logN) 执行。 为了降低 Merge 复杂度,人们不得不使用指针,这就诞生了左式堆。左式堆本质上是一个二叉树,斜堆是左式堆的一个变体,各方面性能和左式堆相似。 左式堆(...

二叉查找树

数据结构和算法

  

2019-12-28 18:11:43

二叉查找树要求,在树中的任意一个节点,其左子树中的每个节点的值,都要小于这个节点的值,而右子树节点的值都大于这个节点的值。 通过上面的分析可知,我们的查找删除新增,其时间复杂度都和树的高度成正比,为O(height),遍历的时间复杂度是O(n),树的高度等于最大层数-1 包含 n个节点的完全二叉树中,第一层包含 1 个节点,第二层包含 2 个节点,第三层包含 4 个节点。 依次类推,下面一层节点个...

堆排序原理

数据结构和算法

  

2019-12-30 10:13:28

1、什么是堆? 堆是一种非线性结构,(本篇随笔主要分析堆的数组实现)可以把堆看作一个数组,也可以被看作一个完全二叉树,通俗来讲堆其实就是利用完全二叉树的结构来维护的一维数组 按照堆的特点可以把堆分为大顶堆和小顶堆 大顶堆:每个结点的值都大于或等于其左右孩子结点的值 小顶堆:每个结点的值都小于或等于其左右孩子结点的值 (堆的这种特性非常的有用,堆常常被当做优先队列使用,因为可以快速的访问到&ldqu...

栈:限定仅在表尾进行插入和删除操作的线性表。 栈的插入(进栈)和删除(出栈)操作如下图所示。     1.栈的顺序存储结构   用数组存放数据,top变量来指示栈顶元素在数组中的位置(栈顶指针)。一个长度为5的栈的示意图如下: 实现程序: 测试代码: 2.两栈共享空间   通过一个数组存放两个栈,能较好地利用空间。用top1和top2变量表示栈1和栈2的栈顶指针,两个栈的栈底分别位于数组...

用数组描述的链表,称为静态链表。 数组元素由两个数据域data和cur组成:data存放数据元素;cur相当于单链表中的next指针,称为游标。 某一静态链表结构如图所示(游标存放内容可参考程序中的说明1): 静态链表的优缺点: 静态链表实现程序:  ...

每个结点中只包含一个指针域的链表,称为单链表。 单链表的结构如图所示: 单链表与顺序存储结构的对比: 实现程序: 测试代码: 基本数据类型和引用类型各写了一个测试代码。  ...