数据结构与算法 排序算法-冒泡排序

「冒泡排序 Bubble Sort」通过连续地比较与交换相邻元素实现排序。这个过程就像气泡从底部升到顶部一样,因此得名冒泡排序。

我们可以利用元素交换操作模拟上述过程:从数组最左端开始向右遍历,依次比较相邻元素大小,如果“左元素 > 右元素”就交换它俩。遍历完成后,最大的元素会被移动到数组的最右端。

1
利用元素交换操作模拟冒泡

2
bubble_operation_step2

阅读更多

数据结构与算法 非线性数据结构-红黑树 RBT

基于BST存在的问题,一种新的树——平衡二叉查找树(Balanced BST)产生了。平衡树在插入和删除的时候,会通过旋转操作将高度保持在logN。其中两款具有代表性的平衡树分别为AVL树和红黑树。AVL树由于实现比较复杂,而且插入和删除性能差,在实际环境下的应用不如红黑树。

红黑树(Red-Black Tree,以下简称RBTree)的实际应用非常广泛,比如Linux内核中的完全公平调度器、高精度计时器、ext3文件系统等等,各种语言的函数库如Java的TreeMap和TreeSet,C++ STL的map、multimap、multiset等。

RBTree也是函数式语言中最常用的持久数据结构之一,在计算几何中也有重要作用。值得一提的是,Java 8中HashMap的实现也因为用RBTree取代链表,性能有所提升。

阅读更多

数据结构与算法 非线性数据结构-二叉树

「二叉树 Binary Tree」是一种非线性数据结构,代表着祖先与后代之间的派生关系,体现着“一分为二”的分治逻辑。与链表类似,二叉树的基本单元是节点,每个节点包含一个「值」和两个「指针」。

节点的两个指针分别指向「左子节点」和「右子节点」,同时该节点被称为这两个子节点的「父节点」。当给定一个二叉树的节点时,我们将该节点的左子节点及其以下节点形成的树称为该节点的「左子树」,同理可得「右子树」。

在二叉树中,除叶节点外,其他所有节点都包含子节点和非空子树。例如,在以下示例中,若将“节点 2”视为父节点,则其左子节点和右子节点分别是“节点 4”和“节点 5”,左子树是“节点 4 及其以下节点形成的树”,右子树是“节点 5 及其以下节点形成的树”。

阅读更多

数据结构与算法 非线性数据结构-二叉搜索树

「二叉搜索树 Binary Search Tree」满足以下条件:

  1. 对于根节点,左子树中所有节点的值 < 根节点的值 < 右子树中所有节点的值;
  2. 任意节点的左、右子树也是二叉搜索树,即同样满足条件 1.

二叉搜索树

二叉搜索树的操作

查找节点

给定目标节点值 num ,可以根据二叉搜索树的性质来查找。我们声明一个节点 cur ,从二叉树的根节点 root 出发,循环比较节点值 cur.valnum 之间的大小关系

阅读更多

数据结构与算法 非线性数据结构-散列表-哈希表

散列函数

散列函数是这样的函数:不论你给它什么东西,它都返回给你一个数字;

我们通过散列函数来创建一个空数组,给它什么输入,它就能给它特定的输出。比如先创建一个空数组,把apple当输入传给散列函数,函数返回3,那我们就可以把apple的价格比如4元存储到索引3处;

不断重复可以将这个数组填满,之后我们再向这个函数输入apple,它就会告诉我们价格存储在索引3处,时间复杂度为O(1);

阅读更多

数据结构与算法 非线性数据结构-树

树的基本概念

  1. 父节点:在树结构中,每一个节点只有一个前件,称为父节点,没有前件的称为根节点,简称树的根。
  2. 子节点和叶子节点:在树结构中每一个结点可以有多个后件,称为该结点的子节点,没有后件的节点称为叶子节点。
  3. :在树结构中,一个结点所拥有的后件个数称为该结点的度,所有结点中最大的度称为树的度。
  4. 深度:定义一棵树的根结点所在的层次为1,其他结点所在的层次等于它的父结点所在的层次加1。树的最大层次称为树的深度。
阅读更多

数据结构与算法 线性表-队列

「队列 Queue」是一种遵循先入先出(First In, First Out)规则的线性数据结构。顾名思义,队列模拟了排队现象,即新来的人不断加入队列的尾部,而位于队列头部的人逐个离开。

我们把队列的头部称为「队首」,尾部称为「队尾」,把将元素加入队尾的操作称为「入队」,删除队首元素的操作称为「出队」。

队列的先入先出规则

队列常用操作

队列的常见操作如下表所示。需要注意的是,不同编程语言的方法名称可能会有所不同。我们在此采用与栈相同的方法命名。

阅读更多