选择排序（Selection Sort）

1
2
3
4
5
6
7
8
9
for(i=0;i<n;++i){
    index_min = i
    for(j=i;j<n;++j){
        if(list[j]<list[index_min]){
            index_min = j
        }
    }
    swap(i,index_min)//交换数组里最小的数字和未排序数组的第一个数字
}

每一次在未排序的数组里选择最小元素，把这个最小元素和未排序数组的第一个数字交换，直到未排序数组的大小为0，程序结束

分治法求解最大子序列问题

求解一个给定序列的最大子序列和，利用分治法，我们将这个问题转化为求解左半边的最大子序列和，右半边的最大子序列和，以及包含两边的元素的序列和，第一种和第二种我们可以跟据递归直接理想化地得到，第三种我们需要定义一个函数进行计算

对于这个函数如下,我们要计算的子序列是包含中间元素的子序列，所以我们从中间开始计数，我们设置left_sum初始值为一个很大的负数，这是为了保证第一个中间元素一定能被包含进去的简化，如果不这样写，那么我们就会写成初始化subsum为中间元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int crossmaxsubsum(list,l,r,m){
    //传入参数，数组，数组左端位置，右端位置，中间位置
    subsum = 0;
    left_sum = -10000;
    for(i=m;i>=l;--i){
        subsum += list[i];
        if(subsum > left_sum)
            left_sum = subsum;
    }
    subsum = 0;
    right_sum = -10000;
    for(i=m+1;i<r;++i){
        subsum += list[j];
        if(subsum > right_sum)
            right_sum = subsum;
    }
    return max(left_sum + right_sum,left_sum,right_sum);
}

主函数

1
2
3
4
5
6
7
8
9
int maxsubsum(list,l,r){
    if(l<r)
        return erro;
    if(l==r)
        return list[l];
    m = (l+r)/2;
    maxsubstring = max(maxsubsum(list,l,m-1),maxsubsm(list,m,r),crossmaxsubsum(list,l,r,m));
    return maxsubstring
}

复杂度分析

我们将问题拆解，可以得到一个递归关系

其中求交叉和的时候，我们进行的是一次线性时间复杂的的运算

对上式进一步展开可得

我们令

那么可以得到

所以该算法的时间复杂度为

求最大子序列的线性复杂度算法

下面这个函数能在线性时间复杂度内完成这个问题，我们指定两个变量，一个储存动态的变化值(ThisSum)，一个储存静态的答案(MaxSum)。如果ThisSum大于MaxSum,那么说明我们得到的就是目前读入的数组部分的最大值，如果ThisSum小于0了，那么前面这一段序列我们都可以视为一个负数，负数加入任何一个序列都一定会使这个序列的值变小，所以我们直接舍去，使ThisSum=0。

1
2
3
4
5
6
7
8
9
10
int maxsum(int list,int l,int r){
    int ThisSum=MaxSum=0;
    for(i=l;i<r;++i){
        ThisSum += list[i];
        if(ThisSum >= MaxSum)
            MaxSum = ThisSum;
        else if(ThisSum < 0)
            ThisSum = 0;
    }
}

misc

由后缀或前缀表达式求值

由后缀表达式构建表达式树

中序遍历的循环实现

实际上一切的递归都可以通过循环加上栈来实现，CPU里对递归的运算就是这么实现的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void inordertravesal(Tree Root){
    Stack S;
    while(True){
        if(Root != NULL){
            push(Root,S);
            Root = Root->left;
        }
        else if(!Isempty(S)){
            Root = pop(S);
            visit(Root);
            Root = Root->right
        }
        else
            break;
    }
}

优先队列（堆）

堆的插入操作需要上浮插入到堆尾的元素，堆的删除堆顶元素的操作需要下沉操作。

我们以最小堆为例说明函数。堆的元素数组为heap->elements,其中heap->elements[0]作为空头，不储存实际的元素，第一个元素从1开始。

我们将一个元素插入到堆尾，然后对这个元素进行percolate up操作

1
2
3
4
5
6
7
8
9
10
void insert(Heap* heap,ElementType ele){
    if(IsFull(heap)){
        return Erro;
    }
    ++heap->size;
    for(i=heap->size;heap->elements[i/2]>ele;i/=2){
        heap->elements[i]=heap->elements[i/2];
    }
    heap->elements[i]=ele;
}

我们删除并返回堆顶元素，为了保持堆的完全二叉树的性质，我们将堆尾元素取代堆顶元素，并进行percolate down

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int DeleteMin(Heap* heap){
    int i,child;
    ElementType MinElement,LastElement;
    if(Isempty(heap)){
        printf("The heap is empty");
        return heap->elments[0];
    }
    MinElement = heap->elements[0];
    LastElement = heap->elements[size--];
    for(i=1;i<heap->size;i*=2){
        child = i*2;
        if(child<heap->size&&heap->elements[child]<heap->elements[child+1]){
            child++;
        }
        if(LastElement>heap->elements[child]){
            heap->elements[i]=heap->elements[child];
        }
        else
            break;
    }
    heap->elements[i]=LastElement;
    return MinElement;
}

建堆的方法

  1. 我们可以将建堆操作转化为连续的N个插入操作
  2. 也可以对堆的前[heap->size/2]个元素进行percolate down直接操作

并查集

我们用数组表示集合，数组的索引代表的是这个元素，数组索引里的数字代表的是这个元素的父节点的索引，根节点的父节点索引我们一般设置为0，但是在不同的合并集合的策略下，我们对根节点的索引设置不同，比如按照大小合并集合，我们一般设置根节点的父节点索引为集合大小的相反数，按照树的高度合并，根表示的是树的高度的相反数。

按大小合并集合

1
2
3
4
5
6
7
8
9
10
void SetUnion(ElementType* S,Root1,Root2){
    if(S[root1] < S[root2]){//以root1为根的集合更大
        S[root1] += S[root2];
        S[root2] = root1;
    }
    else{//以root2为根的集合大于等于以root1为根的集合
        S[root2] += S[root1];
        S[root1] = root2;
    }
}//按大小合并

按高度合并集合

1
2
3
void SetUnion(ElementType* S,Root1,Root2){//root表示的高度的相反数，我们将高度小的树合并到高度大的树
    
}

最短路径算法

迪杰斯特拉算法

从起点开始，将所有与起点相连接的边入堆，取出最短的边，再将与这条边的终点的顶点相连的最短的边入堆，再选出最短的边，重复该步骤，直到所有顶点都被遍历

EC

项目能完成的最短时间，我们将一个具有拓扑结构的项目进程抽象为一个有向无环图，每一个顶点代表某一个项目状态，每一条边表示不同项目状态的过渡需要花费的时间，EC就是求完成一个项目所需的最短时间，EC等于所有入边连接到该点的边所连接的另一个点中最大的EC加上这条边的权重。

LC

项目所能完成的最长的时间，我们由EC可计算LC，最后一个顶点的LC等于EC，每一个顶点的LC等于所有出边连接到的顶点中LC的最小值减去这条边的权重。

最大流算法

在原始图中找到一条增广路径，去掉这条增广路径，并添加反向边，得到新的图，再对新的图寻找增广路径，添加反向边，如此重复，直到最后不能找到增广路径为止。

我们通过定义一个$\Delta$为最接近最大边容量的一个2的幂次方，每一次找容量为$\Delta$的路径，并将$\Delta$除二，直到$\Delta$等于1，这样优化算法，时间复杂度如下

寻找一个图的割点

我们通过深度优先的方式遍历图得到一个生成树，其中num数组储存每一个节点先后被访问的次序，其中图中没有遍历到的边作为回边（back edge）添加到树当中，然后对每一个节点求low数组，low数组中数字相同的节点属于同一个双连通分量。

每一个顶点的low值由该顶点的num,所有该顶点孩子节点的low,与该顶点形成回边的顶点的num值得最小值得到。

如果一个顶点是割点，那么：

  1. 如果这个顶点是根节点，那么根节点的孩子数量一定大于等于2
  2. 如果这个顶点不是根节点，那么这个顶点至少有一个节点并且这个节点的所有孩子节点的low值大于该节点的num值

排序

排序算法的下界是$N\log{N}$

希尔排序

快速排序

桶排序

基数排序

许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。