归并排序 一、描述 归并排序（Merge sort）是建立在归并操作上的一种有效、稳定的排序算法, 该算法是采用分治法(Divide and Conquer）的一个非常典型的应用. 将已有序的子序列合并, 得到完全有序的序列 即先使每个子序列有序, 再使子序列段间有序. 若将两个有序表合并成一个有序表, 称为二路归并. \(\log n\)轮, 每轮 \(O(n)\) 次拷贝. 因此

选择排序 一、描述 选择排序是一种简单直观的排序算法, 无论什么数据进去都是 \(O(n^2)\) 的时间复杂度. 所以用到它的时候, 数据规模越小越好. 唯一的好处可能就是不占用额外的内存空间了吧. 只需要两个额外的空间来存放最小数据的引用与下标, 因此空间复杂度为 \(O(1)\). 与插入排序不同, 先做最麻烦的, 要进行 \(n-1\) 次比较才能获得最小的数据. 二、具体代码

冒泡排序 一、描述 冒泡排序（Bubble Sort）也是一种简单直观的排序算法. 它重复地走访过要排序的数列, 一次比较两个元素, 如果他们的顺序错误就把他们交换过来. 走访数列的工作是重复地进行直到没有再需要交换, 也就是说该数列已经排序完成. 这个算法的名字由来是因为越小的元素会经由交换慢慢 "浮" 到数列的顶端. 冒泡排序还有一种优化算法, 就是立一个 flag , 当

插入排序 一、描述 插入排序像什么？没错就像斗地主或者打麻将中码牌. 每次对一个牌进行排序, 从左到右是有先后顺序的. 和这个类似的叫做冒泡排序在后面也会提及. 插入排序是简单直接的排序方式之一. 代码非常短.每次保证前 i 个数据是有序的. 先做简单的事情 (第 1 轮最多有 1 次移动), 再做麻烦的事情 (最后一轮最多有 \(n - 1\) 次移动). 下标 0 的数据为岗哨

顺序查找与折半查找 一、节点结构 不同于书上的常用整数值来表示所需要存储的内容. 这里使用了键值对的形式来存储. 简而言之就是查找是查找整数表示的键, 返回的是字符串的值. 节点结构和整体初始化代码如下所示: 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495

关键路径 一、描述 拓扑排序是关键路径的一部分. 为什么会有这种说法呢？就像工程施工需要把所有前置条件完成才能继续, 这个所谓前置条件就是拓扑排序. 而关键路径要求的就是完成工程的最长时间. 关键路径长度, 其实是最远路径长度. 然而, 它并非最短路径的对偶问题. 正向算每个节点的最早开始时间, 逆向算每个节点的最晚开始时间. 当最早开始和最晚开始为一样的时候就说明这个节点是关键路

十字链表 一、描述 与邻接表不同, 十字链表法仅适用于存储有向图和有向网. 不仅如此, 十字链表法还改善了邻接表计算图中顶点入度的问题. 十字链表存储有向图的方式与邻接表有一些相同, 都以图中各顶点为首元节点建立多条链表, 同时为了便于管理, 还将所有链表的首元节点存储到同一数组(或链表)中. 归根到底就是弧做为一种节点, 顶点做为另一种节点并以顺序表的形式存储. 用十字链表存储