数据结构

Ch3 算法分析

原目录：数据结构

查看语雀原文

1. 时间成本

一个算法运行的总时间主要和两点有关：

1. 执行每条语句的耗时
2. 执行每条语句的频率

前者取决于计算机，编译器和操作系统；后者取决于程序本身和输入，因此：

\(总时间 = 每条语句耗时*每条语句频率 + 指令成本\)

通过以上公式可知分析程序执行的时间成本关键在分析"语句频率"，我们通常使用的方法--"渐进分析"

渐进分析

定义：渐进分析是指当输入规模（n）很大，或者说达到极限（微积分意义上），对算法进行研究，此时我们可以在频率分析中忽略幂次较低的项和某些系数。

数学语言：

在频率分析中可能产生冗长的表达式，如：

\(\frac{N(N-1)(N-2)}{6}=\frac{N^3}{6}-\frac{N^2}{2}+\frac{N}{3}\)

根据渐进分析定义

\(\lim_{n \to \infty}\frac{\frac{N(N-1)(N-2)}{6}}{\frac{1}{6}N^3}=1\)

则原式可近似为

\(\frac{N(N-1)(N-2)}{6}\sim\frac{1}{6}N^3,增长率数量级N^3\)

给出一般的近似方式（来自《算法》）

\(g(N)\sim af(N),其中f(N)=N^b(logN)^c \\【a,b,c为常数;对数不标注底数，因为通常系数a可弥补;f(n)通常被称为g(N)的增长数量级】\)

上限\(O\)

"大欧表示法"

定义：\(T(n)表示算法实际运行时间,f(n)是上限的一个函数表示:对于非负函数T(n),如果存在两个正常数c和n_0,对任意n>n_0,有T(n)\leq cf(n)则称T(n)在集合O(f(n))中\)

意义：对于问题的所有输入（包括最差情况），只要输入规模足够大\((n>n_0)\)，算法总能够在\(cf(n)\)步以内完成

下限\(\Omega\)

"大欧米伽表示法"

定义：\(T(n)表示算法实际运行时间,g(n)是下限的一个函数表示:对于非负函数T(n),如果存在两个正常数c和n_0,对任意n>n_0,有T(n)\geq cg(n)则称T(n)在集合\Omega(g(n))中\)

意义：对于问题的所有输入（包括最优情况），只要输入规模足够大\((n>n_0)\)，算法最快能够在\(cg(n)\)步以内完成

平均\(\Theta\)

"大西塔表示法"

当算法开销增长率的上下限相等时，即算法既在\(O(f(n))\)又在\(\Omega(g(n))\)中，可以用\(\Theta(h(n))\)表示

给定一个反映算法时间开销的表达式时，其上下限通常相等，因为此时运行时间函数已经被表示了出来，渐进分析过程已经确定，则\(f(n)\)可确定

常见增长率

注意：平方级别和立方级别的算法对于大规模的问题是不可用的，许多问题的平方级解法可以有线性对数级别算法代替

2. 空间成本

数据结构主要的目的是存储数据，提供简单高效的访问，为此每个数据结构都有附加的"结构性开销（overhead）"，不同算法的空间成本主要来自于使用数据结构的结构性开销

以Java为例

以下以Java为例讨论不同数据结构的空间成本，已知Java原始数据类型常见内存需求：

• 对象

对象使用内存 = 所有实例变量内存 + 对象本身开销(一般为16字节，包括一个指向对象的类的引用，垃圾收集信息，同步信息，且一般内存的使用都会被填充为8字节的倍数)

eg：一个Integer对象使用24字节开销 = 16字节对象开销 + 4字节int开销 + 4字节填充

• 链表

嵌套的非静态(内部)类，如Node类，还需要额外8字节用于一个指向外部类的引用

eg：一个Node对象使用40字节开销 = 16字节对象本身 + 指向Item和Node对象的引用各需要8字节 + 8字节额外开销

• 数组

Java中数组被视为对象，数组都需要24字节的头信息(16字节对象开销+4字节保存长度+4字节填充);一个对象的数组实际上是对象的引用的数组，除了对象元素的开销还有对象引用的开销;而二维数组是一个数组的数组，每个数组都是一个对象：

一般数组：一个N个int的数组开销(24+4N)字节 = 24字节头信息 + 4N数组元素开销

对象数组：一个含有N个Node对象的数组开销(24+40N+8N)字节 = 24字节头信息 + 40N对象元素开销 + 8N对象引用开销

二维数组：一个M*N的double类型数组开销()字节 = 24字节头信息 + 8M字节所有对象引用开销 + 24M元素数组开销 + 8MN所有double变量开销

• String对象

String对象在库中定义

public class String
{
	private char[] value;
	private int offset;
	private int count;
	private int hash;
	...
}

String的标准实现含有4个实例变量：一个指向字符数组的引用(8字节)和三个int值(各4字节)，第一个int值描述的是字符数组中的偏移量，第二个int值是一个计数器(字符串的长度)，第三个int值是一个散列值，因此：

一个String对象开销40字节() = 16字节对象开销 + 3*4int开销 + 8字节引用开销 + 4个填充字节

但这只是除了字符数组之外字符串所需的内存空间，所有字符所需的内存需要另记，因为String的char数组常常在多个字符串之间共享，因为String对象不可变.这种设计使String的实现可以在多可对象有相同value[]数组时节省内存

Ch4 线性表/栈/队列

原目录：数据结构

查看语雀原文

1. 线性表 List

顺序表

顺序表把表中元素定义为存储在数组的相邻元素中，其中curr称为"栅栏"，指向当前位置

实现

ArrayList.java

时间开销

单链表

链表基于指针，可以动态的为新元素分配存储空间，它是由一系列节点（Link）对象组成的

实现

Link.java

LinkedList.java

时间开销

🤷‍♂️AList对比LList

1. 空间效率：n为当前元素数，P为指针内存大小，E为数据大小，D为数组最大容量，则n满足如下条件时

2. 选择：调用next/prev多时选择AList；插入元素多，选择LList

双链表

为了弥补单链表对无法快速访问前结点的问题，我们重新构造Link，使其保存两个指针，分别指向前一个和后一个节点

实现

DLink.java

DoubleLinkedList.java

时间开销

2. 栈 Stack

栈是限定仅在一端进行插入或删除的线性表，元素一般都按照LIFO（后进先出）顺序

顺序栈

本质就是顺序表(数组)的简化，建立栈时说明固定长度size，top表示栈顶，也是当前栈中元素数目

实现

AStack.java

时间开销

链式栈

本质是对链表的简化，无需head结点，唯一需要top指针指向栈顶

实现

LStack.java

时间开销

3. 队列 Queue

队列也是一类受限制线性表，元素只能从队尾插入(入队，enqueue)，从队首删除(出队，dequeue)，遵循FIFO先进先出原则.

顺序队列

基于顺序表(数组)，使用front和rear标记队首队尾，enqueue时插入元素rear右移dequeue时删除元素front右移.但是会产生"伪满"问题，即rear=size-1时无法插入新元素到数组中，但front由于dequeue实际上右移多位，即数组左侧实际依旧是空的.

时间开销

循环队列

循环队列也是顺序队列，但假设顺序表为循环的，为此需使得一个元素始终为空，根据rear是否标记数组空元素分为两种实现：

(1)rear不指空

实现

AQueue.java

(2)rear不指空

实现略(基本一致)

链式队列

实现

LQueue.java

链式队列基于链表，为了简便使用一个头节点.初始使得front与rear同时指向空头节点，之后front总是指向空头节点，rear总是指向尾节点

Ch5 二叉树

原目录：数据结构

查看语雀原文

1. 概述

定义和性质

二叉树是n个有限元素(结点，nodes)的集合，该集合要么为空，要么由一个根元素(root)及两个不相交的左，右子树(同为二叉树)组成，是有序树.

• 高度&深度

每个二叉树有以下属性

• 满&完全

根据二叉树形态可以分为

• 结构性开销

有关定理

4. 二叉检索树(BST)

对任意一个结点，其左子树任意结点值都<k，右子树任意结点值≥k

实现

BST.java

方法详解

• findhelp

检索，对比当前结点key和检索值k，再深入左右子树

时间开销：Θ(log₂n)~Θ(n)，取决于平衡性(左右子树规模)

private E findhelp(BSTNode<Key, E> rt, Key k)
{
    if (rt == null)
        return null;
    if (rt.key().compareTo(k) > 0)
        return findhelp(rt.left(), k);
    else if (rt.key().compareTo(k) == 0)
        return rt.element();
    else
        return findhelp(rt.right(), k);
}

• inserthelp

插入新结点，类似检索过程，找到合适的位置后插入为新的叶结点

时间开销：Θ(log₂n)~Θ(n)，取决于平衡性

private BSTNode<Key, E> inserthelp(BSTNode<Key, E> rt, Key k, E e)
{
    if (rt == null)
        return new BSTNode<Key, E>(k, e);
    if (rt.key().compareTo(k) > 0)
        rt.setLeft(inserthelp(rt.left(), k, e));
    else
        rt.setRight(inserthelp(rt.right(), k, e));
    return rt;
}

• deletemin/getmin

删除/获取当前树中最小的key，即一路沿左侧枝杈找到末端叶结点

private BSTNode<Key, E> deletemin(BSTNode<Key, E> rt)
{
    if (rt.left() == null)
        return rt.right();
    rt.setLeft(deletemin(rt.left()));
    return rt;
}
private BSTNode<Key, E> getmin(BSTNode<Key, E> rt)
{
    if (rt.left() == null)
        return rt;
    return getmin(rt.left());
}

• removehelp

删除指定的X结点，分情况(见下图)：

1. X只有LC，则：X.LC变成X.parent的LC
2. X只有RC，则：X.RC变成X.parent的RC
3. X兼具LC，RC，则：X右子树最小值变成X.parent

private BSTNode<Key, E> removehelp(BSTNode<Key, E> rt, Key k)
{
    if (rt == null)
        return null;
    if (rt.key().compareTo(k) > 0)
        rt.setLeft(removehelp(rt.left(), k));
    else if (rt.key().compareTo(k) < 0)
        rt.setRight(removehelp(rt.right(), k));
    else
    { // Found it
        if (rt.left() == null)
            return rt.right();
        else if (rt.right() == null)
            return rt.left();
        else
        { // Two children
            BSTNode<Key, E> temp = getmin(rt.right());
            rt.setElement(temp.element());
            rt.setKey(temp.key());
            rt.setRight(deletemin(rt.right()));
        }
    }
    return rt;
}

• printhelp

实现前中后序遍历结果打印，以下为中序遍历结果打印，调整语句顺序可改变打印顺序(*BST中序遍历结果即从小到大排序)

时间开销：Θ(n)，需要遍历n个结点

private void printhelp(BSTNode<Key,E> rt) 
{
    if (rt == null) return;
    printhelp(rt.left());
    printVisit(rt.element());
    printhelp(rt.right());
}

5. 堆(heap)

堆是由数组实现的完全二叉树，同时必须是部分有序的(partially ordered)，并由此分为

• 最大堆max heap：任意结点的值都大于等于其子节点值
• 最小堆min heap：任意结点的值都小于等于其子节点值

实现

MaxHeap.java

方法详解

• buildheap

给定任意长度n的原始数组，从下到上建立最大堆：

从下到上建堆可以忽略最后一层的叶结点，\(\color\red{pos=\left \lfloor\frac{n}{2}-1\right \rfloor}\)可确定堆倒数第二层开始的下标，从右到左依次siftdown，下沉到合适位置，然后是倒数第三层...最终到顶层元素下沉，执行完毕可得到一个最大堆

时间开销：Θ(n)

public void buildheap() 
{
    for (int i = n / 2 - 1; i >= 0; i--)
        siftdown(i);
}

• siftdown

下沉Heap[pos]到堆合适的位置

给定pos，找出其两个子结点中较大的;对比Heap[pos]和Heap[j]，大的作为父结点

时间开销：Θ(log₂n)

/** Put element in its correct place */
private void siftdown(int pos)
{
    assert(pos >= 0) && (pos < n) : "Illegal heap position";
    while (!isLeaf(pos))
    {
        int j = leftchild(pos);
        if ((j < (n - 1)) && (Heap[j].compareTo(Heap[j + 1]) < 0))
            j++; // j is now index of child with greater value
        if (Heap[pos].compareTo(Heap[j]) >= 0)
            return;
        DSutil.swap(Heap, pos, j);
        pos = j; // Move down
    }
}

举例：建堆

• insert

插入新元素进堆

首先插入数组末端，然后与parent的值对比，上浮到合适位置

时间开销：Θ(log₂n)

/** Insert val into heap */
public void insert(E val)
{
    assert n < size : "Heap is full";
    int curr = n++;
    Heap[curr] = val; // Start at end of heap
    // Now sift up until curr’s parent’s key > curr’s key
    while ((curr != 0) &&
           (Heap[curr].compareTo(Heap[parent(curr)]) > 0))
    {
        DSutil.swap(Heap, curr, parent(curr));
        curr = parent(curr);
    }
}

• removemax

移除堆顶(最大值)

实现时只需要交换堆顶/首元素和数组末尾元素，同时--n，避免换到末尾的元素被访问，之后新堆顶重新下沉

时间开销：Θ(log₂n)

public E removemax()
{
    assert n > 0 : "Removing from empty heap";
    DSutil.swap(Heap, 0, --n); // Swap maximum with last value
    if (n != 0)                // Not on last element
        siftdown(0);           // Put new heap root val in correct place
    return Heap[n];
}
/** Remove and return element at specified position */

• remove

移除指定位置元素

实现时只需要交换Heap[pos]元素和数组末尾元素，同时--n，避免换到末尾的元素被访问，Heap[pos]处新元素先上浮，再下沉

时间开销：Θ(log₂n)

public E remove(int pos)
{
    assert(pos >= 0) && (pos < n) : "Illegal heap position";
    if (pos == (n - 1))
        n--; // Last element, no work to be done
    else
    {
        DSutil.swap(Heap, pos, --n); // Swap with last value
        // If we just swapped in a big value, push it up
        while ((pos > 0) &&
               (Heap[pos].compareTo(Heap[parent(pos)]) > 0))
        {
            DSutil.swap(Heap, pos, parent(pos));
            pos = parent(pos);
        }
        if (n != 0)
            siftdown(pos); // If it is little, push down
    }
    return Heap[n];
}

• 逻辑上建成的偏序Heap和数组元素的排序无直接关系，最大堆不代表数组从大到小排列
• 对最大堆不断执行remove()后返回的所有元素依次排列为数组元素从大到小顺序

6. 哈夫曼树(Huffman Tree)

给定文本，可以确定其中每个字母出现的频度，将频度作为权值，以这些"权值+字符"作为二叉树的叶子结点，构造一棵二叉树.每个叶子结点对应一个加权路径长度(WPL)：\(\color\red{WPL=权重*深度}\)，若该树的加权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)，由定义知权值较大的结点离根较近，权值低的结点离根远.

建树过程：不断执行建立最小堆过程，每次结束后执行两次removemin()，取出权重最小两树，合并，然后重新insert()入堆，再次取出权重最小两树...直到堆中只剩一个元素，即为哈夫曼树

应用：为哈夫曼树的枝杈标记01后即可把字符转换为二进制编码，则高频字符编码短，低频字符编码长，这样可以节省文本存储空间

例题：已知文本中字符和频度：，建立哈夫曼树并求所有字符的哈夫曼编码与每个字符预期存储长度

\[\begin{aligned} &编码:\ Z\ 111100\ ||\ K\ 111101\ ||\ M\ 11111\ ||\ C\ 1110\ ||\ L\ 110\ ||\ U\ 100\ ||\ D\ 101\ ||\ E\ 0\\ &2+7+24+...+120=269,(\frac{2}{269}*6+\frac{7}{269}*6+\frac{24}{269}*5+...+\frac{120}{269}*1)/269可得每个字符的期望存储长度 \end{aligned}\]

Ch6 (非二叉)树

原目录：数据结构

查看语雀原文

1. 概述

树状图是一种数据结构，它是由n(n≥0)个有限结点组成一个具有层次关系的集合.把它叫做"树"是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的.它具有以下的特点：

• 每个结点有零个或多个子结点;
• 没有父结点的结点称为根结点;
• 每一个非根结点有且只有一个父结点;
• 除了根结点外，每个子结点可以分为多个不相交的子树;

2. 遍历

由于一般树的子结点可有不止2个，此时无法定义中序遍历，以此对于非二叉树只有两种遍历：

3. 树的并查算法(UNION/FIND)

描述

• UNION：对于多个不相交集合(disjoint sets)，希望支持两个基本操作(1)判断两个对象是否在一个集合中，然后(2)合并两个对象所在集合
• FIND：如果给定两个结点，问它们是否属于同一颗树，可行的方法是上溯两个结点的最终根结点，如果根结点相同，一定属于同一棵树，FIND旨在找出最终根结点

应用

可能直接看到并查算法的描述一脸懵逼👶，看下应用：

"等价类"问题是并查算法的用途之一，这涉及离散数学中的等价关系(满足自反/对称/传递性)

\[\begin{aligned} &问:给定S=\left\{A,B,C,D\right\}已知等价关系(A,B),(A,C),判断(B,C)是否成立?\\ &用并查算法描述:初始时\left\{A\right\}\left\{B\right\}\left\{C\right\}\left\{D\right\}构成四个不相交集合:\\ &给出(A,B),先判断A,B不在一个集合,则UNION得到\left\{A,B\right\}\left\{C\right\}\left\{D\right\};\\ &给出(A,C),先判断A,C不在一个集合,则UNION得到\left\{A,B,C\right\}\left\{D\right\};\\ &问(B,C)是否为真,则FIND得到有公共根结点A,即(B,C)成立 \end{aligned}\]

实现

ParPtrTree.java

本书上使用"父指针树ParPtrTree"实现并查算法(也可以对比《算法》中的并查算法)

1. 初始时针对n个对象创建大小n的数组array，每个对象和每个元素下标建立唯一的对应关系，其中每个元素值暂时初始化为null，这个数组即存储当前对象的最终根结点
2. 输入等价关系(a，b)

1. 执行differ(a，b)，通过find(a)，find(b)在array[a]和array[b]找到二者的最终根结点root1和root2，若不等，则不属于一个树，进入下一步
2. 执行union(a，b)，同样root1和root2，使得array[root2]=root1，即使得两个原本独立的树拥有共同的根节点，二者被合并

\[\begin{aligned} &例题:给定S=\left\{A,B,C,D,E,F\right\}已知等价关系(A,B),(A,C),(C,E),(F,D),(F,A),则可得树为?\\ \end{aligned}\]

首先初始化，创建array[6]

(A，B)：root1=find(0)=0，root2=find(1)=1，array[root2]=root1=0

(A，C)：root1=find(0)=0，root2=find(2)=2，array[root2]=root1=0

(C，E)：root1=find(2)=0，root2=find(4)=4，array[root2]=root1=0

(F，D)：root1=find(5)=5，root2=find(3)=3，array[root2]=root1=5

(F，A)：root1=find(5)=5，root2=find(0)=0，array[root2]=root1=5

UNION()优化：加权合并

默认的"父指针树ParPtrTree"在union()时因为(a，b)顺序的固定会导致一棵结点个数多的树连接到一棵结点数少的树上，即"大树挂小树"，导致生成的树不平衡，我们应使得"小树挂大树"

具体的实现应该是额外维护一个数组用于存储各个根结点的结点数(权重)，在union()时先比较权重确定小树和大树

实现可参考1.5.3 加权quick-union算法

FIND()优化：路径压缩

在查找结点的根结点时，将当前结点直接连接到根结点上

实现可参考1.5.4 路径压缩的加权quick-union算法(最优算法)

4. 树与二叉树变换

树->二叉树

1. 同父结点的兄弟结点相连
2. 对树中非父亲结点的第一个孩子结点，只保留其第一步新加的连线
3. 整理为二叉树形式

二叉树->树

1. 某个结点(A)是其父结点(B)的左孩子时，把该结点的RC，RC.RC，...都与其父结点(A)连接
2. 删除原始二叉树中那些RC，RC.RC，...与各自父结点的连线
3. 整理为树的形式

Ch7 内排序

原目录：数据结构

查看语雀原文

0. 算法一览

内排序是指"所有排序操作都在内存中完成"，无需额外外部存储空间

• 快速排序的空间开销来自于递归栈

1. 插入排序（Insertion Sort）

• 从第一个元素开始，该元素可以认为已经被排序；
• 取出下一个元素，在已经排序的元素序列中从后向前扫描；
• 如果该元素（已排序）大于新元素，将该元素移到下一位置；
• 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
• 将新元素插入到该位置后；
• 重复步骤2~5。

var sortArray = function(nums) {
    const swap = function(arr, i, j){
        let temp = arr[j];
        arr[j] = arr[i];
        arr[i] = temp;
    }
const insertSort = function(arr){
    for(let i=1; i<arr.length; i++){
        for(let j=i-1; j>=0 && arr[j+1]<arr[j]; j--){
            swap(arr, j, j+1);
        }
    }
}

insertSort(nums);
return nums;
};

2. 冒泡排序（Bubble Sort）

• 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
• 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
• 针对所有的元素重复以上的步骤，除了最后一个；
• 重复步骤1~3，直到排序完成。

var sortArray = function(nums) {
    const swap = function(arr, i, j){
        let temp = arr[j];
        arr[j] = arr[i];
        arr[i] = temp;
    }
const bubbleSort = function(arr){
    for(let i=0; i < arr.length-1; i++){
        for(let j=0; j<arr.length-i-1; j++){
            if(arr[j]>arr[j+1]) swap(arr, j, j+1);
        }
    }
}

bubbleSort(nums);
return nums;
};

优化：有序标记

通常资料中都给出冒泡排序的最优时间复杂度为 O(n)，但使用上面的原始算法，即便有序情况下也需要比较 O(n²)，要真正达到 O(n)，需使用一个有序标记：第一次内循环中，如果全体有序，则标记为 true，说明有序，内循环遍历结束后，判断标记为 true，直接跳出外层循环

var sortArray = function(nums) {
    const swap = function(arr, i, j){
        let temp = arr[j];
        arr[j] = arr[i];
        arr[i] = temp;
    }
const bubbleSort = function(arr){
    let isSorted = true;
    for(let i=0; i<arr.length-1; i++){
        for(let j=0; j<arr.length-i-1; j++){
            if(arr[j]>arr[j+1]){
                swap(arr, j, j+1);
                isSorted = false;
            }
        }
        if(isSorted) return;
    }
}

bubbleSort(nums,0,nums.length-1);
return nums;
};

3. 选择排序（Selection Sort）

n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法描述如下：

• 初始状态：无序区为R[1。n]，有序区为空；
• 第i趟排序(i=1，2，3…n-1)开始时，当前有序区和无序区分别为R[1。i-1]和R(i。n）。该趟排序从当前无序区中-选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1。i]和R[i+1。n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；
• n-1趟结束，数组有序化了。

var sortArray = function(nums) {
    const swap = function(arr, i, j){
        let temp = arr[j];
        arr[j] = arr[i];
        arr[i] = temp;
    }
const selectSort = function(arr){
    for(let i=0; i<arr.length; i++){
        let min = i;
        for(let j=i+1; j<arr.length; j++){
            if(arr[j]<arr[min]) min=j;
        }
        if(min != i) swap(arr, min, i);
    }
}
selectSort(nums);
return nums;
};

4. 希尔排序（Shell Sort）

希尔排序是基于简单插入排序的算法：把记录按一定增量(希尔增量)分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一个有序序列。

先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：

• 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；[通常选择初始增量i=array。length/2，此后i=i/2]
• 按增量序列个数k，对序列进行k 趟排序；
• 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m的子序列，分别对各子表进行直接插入排序。仅增量因子为1时，整个序列作为一个表来处理，表长度即为整个序列的长度。

function shellSort(arr) {
    var len = arr.length;
    for (var gap = Math.floor(len / 2); gap > 0; gap = Math.floor(gap / 2)) {
        for (var i = gap; i < len; i++) {
            var j = i;
            var current = arr[i];
            while (j - gap >= 0 && current < arr[j - gap]) {
                 arr[j] = arr[j - gap];
                 j = j - gap;
            }
            arr[j] = current;
        }
    }
    return arr;
}

5. 归并排序（Merge Sort）

归并排序采用分治法（Divide and Conquer）思想，是一种稳定的排序方法。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。 ​

• 把长度为n的输入序列分成两个长度为n/2的子序列；
• 对这两个子序列分别采用归并排序；
• 将两个排序好的子序列合并成一个最终的排序序列。

var sortArray = function(nums) {
    const swap = function(arr, i, j){
        let temp = arr[j];
        arr[j] = arr[i];
        arr[i] = temp;
    }
    const mergeSort = function(temp, arr, l, r){
        if(l>=r) return;
        let mid = ((r-l)>>1)+l;
        mergeSort(temp, arr, l, mid);
        mergeSort(temp, arr, mid+1, r);
    for(let i=l; i<=r; i++){
        temp[i] = arr[i];
    }

    for(let curr=l, i1=l, i2=mid+1; curr<=r; curr++){
        if(i1 == mid+1 || temp[i2]<temp[i1]) arr[curr]=temp[i2++];
        else if(i2 == r+1 || temp[i1]<= temp[i2]) arr[curr]=temp[i1++];
    }
}

mergeSort([], nums, 0, nums.length-1);
return nums;
};

优化：针对小序列

标准归并排序中对于所有子序列我们都使用了归并排序，实际上可设置Threshold，当子序列长度小于Threshold时就是用插入排序，可节省在小序列排序中的开销

var sortArray = function(nums) {
    const swap = function(arr, i, j){
        let temp = arr[j];
        arr[j] = arr[i];
        arr[i] = temp;
    }
const insertSort = function(arr, l, r){
    // 注意是 i<=r
    for(let i=l+1; i<=r; i++){
        for(let j=i-1; j>=l && arr[j]>arr[j+1];j--){
            swap(arr, j, j+1);
        }
    }
}
const mergeSort = function(temp, arr, l, r){
    // 以4作为threshold
    if(r-l<=4){
        insertSort(arr, l, r);
        return;
    }
    let mid = ((r-l)>>1)+l;
    mergeSort(temp, arr, l, mid);
    mergeSort(temp, arr, mid+1, r);

    for(let i=l; i<=r; i++){
        temp[i] = arr[i];
    }

    for(let curr=l, i1=l, i2=mid+1; curr<=r; curr++){
        if(i1 == mid+1 || temp[i2]<temp[i1]) arr[curr]=temp[i2++];
        else if(i2 == r+1 || temp[i1]<= temp[i2]) arr[curr]=temp[i1++];
    }
}

mergeSort([], nums, 0, nums.length-1);
return nums;
};

6. 快速排序（Quick Sort）

快速排序是通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

快排使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：

• 从数列中挑出一个元素，称为 “基准/枢轴”（pivot）；
• 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
• 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

var sortArray = function(nums) {
    const swap = function(arr, i, j){
        let temp = arr[j];
        arr[j] = arr[i];
        arr[i] = temp;
    }
    const quickSort = function(arr, l, r){
        if(l>=r) return;
        let pivot = ((r-l)>>1)+l;
        swap(arr, pivot, r);
        pivot = partition(arr, l-1, r, arr[r]);
        swap(arr, pivot, r);
    quickSort(arr, l, pivot-1);
    quickSort(arr, pivot+1, r);
}
const partition = function(arr, l, r, pivotVal){
    while(l<r){
        while(arr[++l]<pivotVal);
        while(r>0 && arr[--r]>pivotVal);
        swap(arr,l,r);
    }
    swap(arr, l ,r);
    return l;
}

quickSort(nums,0,nums.length-1);
return nums;
};

优化：三项切分快排

原始快排的“左右指针”分别找“比 pivotVal 大的元素”和“比 pivotVal 小的元素”，任由“等于 pivotVal 的元素”原地不动，在下一级迭代排序中继续参与排序

// 原始快排左右指针移动
while(l<r){
  while(arr[++l]<pivotVal);
  while(arr[--r]>pivotVal);
  swap(arr,l,r);
}

当序列中存在大量重复数据时，如果能在当前排序中将“等于 pivotVal 的元素”收集在中间，在下一级迭代中只排序中间项“比 pivotVal 大的元素”和“比 pivotVal 小的元素”，就能显著减少每次待排序的元素数，因此产生了三项切分快排

var sortArray = function(nums) {
    const swap = function(arr, i, j){
        let temp = arr[j];
        arr[j] = arr[i];
        arr[i] = temp;
    }
    const quickSort = function(arr, l, r){
        if(l>=r) return;
        let lt = l, curr = l+1, gt = r;
        let pivot = arr[lt]; // 每次排序以arr[l]作为基准，[lt,gt]间保存与之相同的值
        while(curr<=gt){
            if(arr[curr]<pivot) swap(arr, lt++, curr++);
            else if(arr[curr]>pivot)swap(arr, curr, gt--);
            else curr++;
        }
        quickSort(arr, l, lt-1); // [l, lt-1]间元素都小于pivot
        quickSort(arr, gt+1, r); // [gt+1, r]间元素都大于pivot
    }
quickSort(nums,0,nums.length-1);
return nums;
};

7. 堆排序（Heap Sort）

堆排序是指利用堆这种数据结构所设计的一种排序算法 Ch5. 二叉树-堆(heap)

• 将初始待排序关键字序列(R1，R2 … Rn)构建成大顶堆，此堆为初始的无序区；
• 执行swap()，此时无序区最大元素移至序列末端构成有序区，无序区size-1，有序区size+1
• 不断执行第二步，直到无序区变空

var sortArray = function(nums) {
    const swap = function(arr, i, j){
        let temp = arr[j];
        arr[j] = arr[i];
        arr[i] = temp;
    }
    // 下沉操作
    const siftdown = function(arr,i,len){
        while(i*2+1<len){
            let j=i*2+1;
            if(j+1<len && arr[j]<arr[j+1]) j++;
            if(arr[i]>arr[j]) return;
            swap(arr, i, j);
            i = j;
        }
    }
    // 建堆
    const buildHeap = function(arr){
        for(let i=((arr.length>>1)-1); i>=0; i--){
            siftdown(arr, i, arr.length);
        }
    }
    // 排序
    const heapSort = function(arr){
        buildHeap(arr);
        for(let i=arr.length-1; i>=0; i--){
            swap(arr, 0, i);
            siftdown(arr, 0, i);
        }
    }
heapSort(nums);
return nums;
};

堆排序复杂度分析：

参考链接：堆排序的时间复杂度分析

堆排序流程：

1. 先构造大顶堆
2. 每次交换堆顶（当前最大元素）和无序区最后一个元素，有序区元素加一，无序区元素减一，堆顶重新下沉到合适位置，不断重复，直到无序区只有最后一个元素

复杂度

• 建堆：siftdown() 的复杂度取决于以 a[i] 为 root 的子树高度——O(logn)。从倒数第二层开始建堆（循环次数数 n//2 ），开始树高为1，不断向上，\(log1+log2+log3+ ... => O(n)\)
• 排序重建堆过程：n-1次循环，每次执行siftdown，但结点数也减一，近似为\(O(nlogn)\)
• 总时间复杂度为\(O(n)+O(nlogn)\sim O(nlogn)\)

8. 分配排序/桶排序（Bin Sort/Bucket Sort）

• 简单分配

直接把关键值放在对应下标数组元素(一个桶)中：若A[1]=3，则令B[A[1]]=A[1]=3

for (i=0; i<n; i++)
	B[A[i]] = A[i];	

局限：

1. 关键字不可重复(1个bin中一个元素)
2. 数组size=关键字最大值MaxKey+1
3. 关键字必须为非负整数

• 扩展分配

构建一个以链表为元素的数组B[]，A[]的重复键值可放入一个元素中，共有(MaxKey+1)个桶，最终从B[]的首元素开始遍历每个链表和链表中的元素，输出序列即为有序序列

function countingSort(arr, maxKey) {
    var bucket = new Array(maxKey + 1),
        sortedIndex = 0;
        arrLen = arr.length,
        bucketLen = maxKey + 1;
for (var i = 0; i < arrLen; i++) {
    if (!bucket[arr[i]]) {
        bucket[arr[i]] = 0;
    }
    bucket[arr[i]]++;
}

for (var j = 0; j < bucketLen; j++) {
    while(bucket[j] > 0) {
        arr[sortedIndex++] = j;
        bucket[j]--;
    }
}

return arr;
}

局限：

1. 数组size=关键字最大值MaxKey+1，当MaxKey很大时B的开销很大

复杂度：

9. 基数排序（Radix Sort）

基数排序也叫按位排序

• 确定关键值 maxDigit 和其位数k
• 从低位到高位进行k趟排序，第i趟根据第i对上一趟结果进行桶排序

var counter = [];
function radixSort(arr, maxDigit) {
    var mod = 10;
    var dev = 1;
    for (var i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
        for(var j = 0; j < arr.length; j++) {
            var bucket = parseInt((arr[j] % mod) / dev);
            if(counter[bucket]==null) {
                counter[bucket] = [];
            }
            counter[bucket].push(arr[j]);
        }
        var pos = 0;
        for(var j = 0; j < counter.length; j++) {
            var value = null;
            if(counter[j]!=null) {
                while ((value = counter[j].shift()) != null) {
                      arr[pos++] = value;
                }
          }
        }
    }
    return arr;
}

复杂度：

• d 为位数，r 为基数，n 为原数组个数。
• 在基数排序没有比较操作，所以最好的情况与最坏的情况在时间上是一致的

Ch8 文件管理与外排序

原目录：数据结构

查看语雀原文

1. I/O与磁盘

这部分知识在《操作系统》《系统级编程》中都有相关章节，这里不在赘述

• 《操作系统》Ch11 I/O管理与磁盘调度
• 《系统级编程》Ch11 存储与性能

2. 缓存区&缓存算法

当硬盘的一个扇区（sector）被读取，其中部分信息会被暂存在内存中，这就叫buffering和caching技术，利用了存储的时间局部性和空间局部性，缓存策略通常由：

• FIFO：先进先出队列
• LFU（Least Frequently Used ）：最近最少使用，为每个扇区维护一个频度，优先删去内存中频度小&时间久的
• LRU（Least Recently Used）：最近最久未使用，将新信息读取至缓冲区头，根据需要丢弃尾部信息或重新写至头部

*LRU和LFU有点类似，但LFU缓冲区中任意扇区被读取不会改变其位置；LRU中凡是要被读取的扇区一定先会被重置到头部才会被读取

例题：要读取的扇区序号为9 0 1 7 6 6 8 1，已知缓冲区大小为4个sectors，求访问磁盘而非缓冲区的次数

3. 外排序

外排序与内排序相对，主要针对内存外(磁盘中)的数据排序，因此我们的算法应该尽量减少磁盘访问

3.1 简单2路归并

(Simple External Mergesort)

首先明确顺串(run)，表示有序的子序列，让run length=1即为无序，run length=2表示所有元素成对有序：[5，6]，[1，2]，[3，7]，[0，6]，run length=4类似[1，2，5，6]，[0，3，6，7]

1. 把文件分成两个等大的顺串文件，此时run length=1
2. 从每个run file中读取blocks放入input buffers

1. 从每个input buffer逐个取出记录，按序写入对应output buffers
2. 当output buffer满后写入合适的output file，一般input files有两个，则output file也有两个，此时其中的run length=2

3. output files作为新的input files读取下一个block，重复2-3，每次排序后run length翻倍，最终每个output file中的记录整体有序，即run length=size
4. 归并两个output file，得到一个有序的run file

书上的例子，只给出了run file的变化，不够详细，我在下方给出其中input buffer和output buffer的情况

简单二路归并中总IO次数\(log_2N*\frac{2N}{M}\)，我们的目的是尽量减少磁盘访问，因此可以有两种思路

• 增大初始顺串长度，即想办法使得开始时有序子序列越长越好==>置换选择排序
• 每一趟同时归并多个顺串，即修改对数log的底数2==>多路归并

3.2 置换选择排序

(Replacement Selection)

1. 内存中有一个长M的数组+一个大小M的input buffer+一个output buffer
2. 假设数组已有来自input buffer的M个记录填满，用数组建立最小堆，令LAST=M-1
3. 重复以下步骤

1. removemin()，将最小记录输出到output buffer
2. 设R为input buffer下一记录，若R>刚输入的值，则R作为堆的根结点;否则swap(array，LAST，0)把LAST处记录作为根结点，再把R放到LAST后LAST--
3. 重整堆有序

4. 当LAST=0时，output buffer中所有记录构成一个run，而此时数组M个元素又可进行第二轮求run的操作

算法即不断找到当前堆中最小的记录，不断构建一个从大到小的run，极端好的情况下第一个run就可包含所有数据，极端坏时第一个run length=1，即所有input都小于第一次output

3.3 多路归并

(Multiway Merging)

Ch9 检索（Searching）

原目录：数据结构

查看语雀原文

1. 关于检索

检索(search)：在一组记录中找到某个具有关键码值的记录，或者找到关键码值符合某些条件的一些记录。

常见算法

常见的检索算法分为三类

1. 顺序表和线性表方法
2. 根据关键码值直接访问的方法（Hash）
3. 树索引

评价指标

对线性表检索算法常采用ASL（average searching length，平均检索长度）进行评价，它表示查找若干记录的平均关键字比较次数。

判断元素K是否在长为n的线性表L中：令pi为K在L中位置i的几率（下标为0~n-1的某处），对于任意位置i处值必须查看i+1条记录来访问；当K不在L中时，需要比较n次才能确认，设pn为K不在L的几率，则ASL可以表示为

\(ASL = np_n + \sum_{i=0}^{n-1}(i+1)p_i \\\)

假设除了pn外的每个pi相等

\(ASL = \frac{n+1+p_n(n-1)}{2} \\ 则ASL\in[\frac{n+1}{2},n]\)

2. 检索线性表

• 未排序线性表：根据👆推导，检索无序线性表开销为O（n）
• 顺序线性表：通常采取二分法检索，开销O（logn）

3. 自组织线性表

完全根据关键值排序的线性表开销较大，一般也可以按照请求频率组织线性表，在有限开销情况下提高检索效率。主要有以下三种规则进行组织

• count（计数法）：为每个记录添加一个访问计数，每次访问则计数+1，该记录前移，直到遇到另外一个计数更大的，最终所有记录根据访问计数顺序排列；
• move-to-front（移至最前端）：找到一条记录后，该记录移动到最前端，易使用链表实现，类似LRU算法
• transpose（转置）：找到一条记录后与其前一记录交换

举例：给定线性表ABCDEFG，访问FDFG，使用以上三种规则时的线性表变换图示如下：

① count

\(A\qquad B\qquad C\qquad D\qquad E\qquad F\qquad G \\ 0\qquad\; 0\qquad\; 0\qquad\; 0\qquad\; 0\qquad\; 0\qquad\; 0 \\ F\qquad A\qquad B\qquad C\qquad D\qquad E\qquad G \\ 1\qquad\; 0\qquad\; 0\qquad\; 0\qquad\; 0\qquad\; 0\qquad\; 0 \\ F\qquad D\qquad A\qquad B\qquad C\qquad E\qquad G \\ 1\qquad\; 1\qquad\; 0\qquad\; 0\qquad\; 0\qquad\; 0\qquad\; 0 \\ F\qquad D\qquad A\qquad B\qquad C\qquad E\qquad G \\ 2\qquad\; 1\qquad\; 0\qquad\; 0\qquad\; 0\qquad\; 0\qquad\; 0 \\ F\qquad D\qquad G\qquad A\qquad B\qquad C\qquad E\\ 2\qquad\; 1\qquad\; 1\qquad\; 0\qquad\; 0\qquad\; 0\qquad\; 0 \\ SL = 6+5+1+7=19

)

② move-to-front

(A\qquad B\qquad C\qquad D\qquad E\qquad F\qquad G \ F\qquad A\qquad B\qquad C\qquad D\qquad E\qquad G \ D\qquad F\qquad A\qquad B\qquad C\qquad E\qquad G \ F\qquad D\qquad A\qquad B\qquad C\qquad E\qquad G \ G\qquad F\qquad D\qquad A\qquad B\qquad C\qquad E\ SL = 6+5+2+7=20

)

③ transpose

(A\qquad B\qquad C\qquad D\qquad \underline{E\qquad F}\qquad G \ A\qquad B\qquad \underline{C\qquad D}\qquad F\qquad E\qquad G \ A\qquad B\qquad D\qquad \underline{C\qquad F}\qquad E\qquad G \ A\qquad B\qquad D\qquad F\qquad C\qquad
\underline{E\qquad G} \ A\qquad B\qquad D\qquad F\qquad C\qquad
G\qquad E \ SL = 6+4+5+7=22

)

4. 哈希表⭐

概述

通过一些计算，把关键值映射到数组中的位置来访问记录，这个过程称为散列（hashing）；

• 把关键值映射到位置的函数称为散列函数（hash function， h），向哈希表中插入\检索\删除记录都与之相关；
• 存放记录的数组叫做散列表（hash table， HT）；HT中一个位置叫做一个槽（slot），HT中slot总数为M，slot从0编号到M-1；

设计散列系统的意义是使得对任何关键码值K和某个散列函数h，i=h(K)是表中满足0<=h(K)<M的一个slot，且记录在HT[i]存储的关键码值等于K

哈希函数

根据上述要求，哈希函数的构造原则如下

1. MUST：返回一个值，不超过HT索引范围（0~M-1）
2. SHOULD：尽可能使得码值均匀分布至表中空位

常见哈希函数

1. 除留余数法：\(H(k)=k\%M\)

// 举例，此时M=16
int h(int x){
    return x % 16
}

2. 平方取中法：计算key²，取中间r位作为h(k)返回值，下图说明了结果中的哪些位收到操作数的影响更大，可以发现57是受所有位置操作数影响的，此时使用这两位可以使得key分布更均匀

    \( \begin{align} 4567\\ 4567\\ \hline 31967\\ 27402\ \ \\ 22835\quad\\ 18268\quad \ \ \\ \hline 20957489

\end{align})

3. 折叠法：把所有字符串字符ASCII码值累加对M取模，适合key是字符串且sum>>M

5. 哈希冲突与解决

当key1≠key2，但是h(key1)=h(key2)，此时插入记录时会产生表内冲突（collisions），常见解决思路

1. closed hashing：闭域法/开放地址法（冲突放入另一个slot）
2. open hashing：开域法/链地址法（冲突存入链表）

闭域法/开放地址法

所有记录存在一张表内，为每个记录求得一个探查序列（probe sequence）\(H_0,H_1...H_S,1≤S≤M-1\)，其中\(H_0=h(key)\)如果产生冲突则增加偏移重新取模\(Hi=（H_0+d_i)\%M，i=1,2,3...\)其中di的值取决于探查函数\(p(K,i)\)，常见有如下探查函数

1. 线性探查：\(d_i=i\)

上图图示了线性探查，该函数的缺点是容易导致记录聚集到一起，把这种倾向叫做基本聚集（primary clustering），它会产生很长的探查序列：理想情况下每个slot有相同几率接受记录，但实际上每插入一个记录，其余空槽被填充的几率都会改变，图示左侧slot2，slot9被填充几率实际上是3/10，当slot9被填充后，slot2被填充几率会变成6/10

2. 二次探查：\(d_i=1^2,-1^2,2^2,-2^2 ...\)

线性探查使得基本聚集产生了很长的探查序列，因为每次冲突后的Hi都是连续的，为此我们可以“跳着走”

例题：已知M=10，h(k)=k%11，采用二次探查，作用于关键值：19，1，23，14，55，68，11，82，36，并计算放入剩下slot的概率

\[\begin{aligned} 19:&H_0=19\%11=\underline8 \\ 1:&H_0=1\%11=\underline1 \\ 23:&H_0=23\%11=1,H_1 = (1+1)\%11=\underline2 \\ 14:&H_0=14\%11=\underline3 \\ 55:&H_0=55\%11=\underline0 \\ 68:&H_0=68\%11=2,H_1 = (2+1)\%11=3,H_2 = (3-1)\%11=2,H_3 = (2+4)\%11=\underline6\\ 11:&H_0=11\%11=0,H_1 = (0+1)\%11=1,H_2 = (1-1)\%11=0,H_3 = (0+4)\%11=\underline4\\ 82:&H_0=82\%11=\underline5\\ 36:&H_0=36\%11=3,H_1 = (3+1)\%11=4,H_2 = (4-1)\%11=3,H_3 = (3+4)\%11=\underline7\\ \end{align} \)

此时下个位置情况

\(\begin{align} &当H_0=0,H_1=1,H_2=(-1)\%11=10[注意负数取模不产生负数，可以加模取正，即(-1+11)mod11=10]\\ &当H_0=1,H_1=2,H_2=0,H_3=5,H_4=8,H_5=10\\ &当H_0=2,H_1=3,H_2=1,H_3=6,H_4=9\\ &当H_0=3,H_1=4,H_2=2,H_3=7,H_4=10\\ &...\\ &当H_0=5...H_i=9\\ &当H_0=6...H_i=10\\ &当H_0=7...H_i=9\\ &当H_0=8...H_i=9\\ \end{align} \therefore P_9=\frac{6}{11},P_{10}=\frac{5}{11}\)

3. 随机探查：(伪)随机取值

双哈希

需要注意的是，二次探查和随即探查虽然可以消除基本聚集，但还有另一个问题--“二次聚集”：把H0位置记作基槽，如果两个key被散列到一个基槽，其后的探查序列依旧会重复。这是因为此后\(Hi=（H_0+d_i)\%M，i=1,2,3...\)下一个slot与K无关只和H0有关，因此为了解决二次聚集，我们需要使用二次散列方法（双哈希），再采用额外的一个哈希函数h2

\(\begin{align} 使得&P(k,i)=d_i变成P(k,i)=d_i*h_2(k)\\ &则H_i=(H_0+P(k,i))\% M \\ &=(H_0+d_i*h_2(k))\% M \\ \end{aligned}\]