算法总结

算法总结

算法

什么是算法

从字面上来说，**算法也就是用于计算的方法。是用来解决某些问题的方法。**通过这个方法，可以达到想要的计算结果。它就像我们小时候学些的一些数学公式和解题步骤。

算法特征

算法，一般有5个特征：

  • 有穷性： 算法的执行步骤、时间、都是有限的。不会无休止的一直执行下去。
  • 确切性： 算法的每一步都必须有明确的定义和描述。
  • 输入： 一个算法应该有相应的输入条件，就像我们小时候做的应用题，已知什么什么。来求某个结果，已知部分便是输入条件。
  • 输出： 算法必须有明确的结果输出。没有结果，那这个算法是没有任何意义的。
  • 可行性： 算法的步骤必须是可行的，无法执行的则没有意义，也解决不了任何问题

算法分类

按照算法的应用来分：算法可以分为基本算法、几何算法、加密/解密算法、查找算法、图表数据分析算法等。 按照算法的思路（思想）来分：算法可以分为递推算法、递归算法、穷举算法、分治算法等。

按算法的应用来划分

基本算法：常规的循环、迭代、递归

递归、循环、迭代、遍历的区别

程序的运行快慢一般与其中重复执行的代码息息相关，而“重复执行”的方式又分为以下4种：

  • 递归：一个函数反复调用自身的行为，特指函数本身；
  • 循环：满足一定条件下，重复执行某些行为，如while结构；
  • 迭代：按某种规则执行一个序列中的每一项，每次执行的结果又作为下次执行的初始值，直到满足某个精度或条件；
  • 递推：由前一项可以推出后一项，是从前面的已知结果推出未知结果。当前一项的结果作为后一项的初始值时，就成了迭代。（有时候和迭代混用）
  • 遍历：按某种规则访问图形结构中每一个节点，特指图形结构。

说明例子：

【递归】

你自己不太了解小孩子的需求，为了缩小范围，让你的儿子去给孙子挑选。儿子比你强点有限，但依然不太了解小孩子的需求。为了缩小范围，你又让你孙子去挑选。如此这般，直到找到合适的玩具。

【循环】

你去小卖铺买了一个玩具，拿回家后孩子不喜欢，你也没问他为什么不喜欢。然后你又去同一个小卖铺买了一个玩具，拿回家后孩子又不喜欢。。。如此往复 10 次，孩子才满意。

每次去买玩具的目标、行为都一样，这叫循环。

【迭代】

你去小卖铺买了个一个玩具，拿回家后孩子不喜欢。你耐心的询问后得知他喜欢乐高的玩具，于是你就去大超市给他买了乐高，回家后孩子还是不喜欢，耐心询问后得知他喜欢乐高玩具中最贵的那个玩具，于是你就去奢侈品商店给他买了乐高限量版玩具，拿回家后孩子很满意。

每次去买玩具都跟上一次不一样，或是有了新的目标，或是缩小了搜寻范围，这叫迭代。

来源：CyrusCao_知乎_https://www.zhihu.com/question/20278387/answer/109266159

递归、迭代、循环常常可以转换，且转换后程序的效率不一定相同。递归由于效率低的问题，经常要求转换成循环结构的非递归形式。

递归、分治策略、动态规划以及贪心算法之间的关系

最大公因数

辗转相减法是一种简便的求出两数最大公约数的方法。由其可推出辗转相除法。

辗转相除法求两正整数的迭代次数较少。

辗转相除,使余数消失的那个除数就是最大公因数

算法流程

gcb(m,n): m>n, r 是 m ÷ n 的余数， 若r不为0， 继续gcd(n,r); 若r为0，则n是最大公因数

递归法
int divisor(int m,int n)
{
    if (m % n == 0) {
        return n;
    }
    else {
        return divisor(n,m % n);
    }
}
迭代法
public static int gcd(int a,int b){
    //如果相等
    if(a==b){
        return a;
    }
    //保证大数除以小数
    int l,x=a,y=b;
    if(a>b){
        x=b;
        y=a;
    }
    //迭代出现余数为0
    while((l=(y%x))!=0){
        y=x;
        x=l;
    }
    return x;
}
迭代法2（更优雅）
private static int getMaxFactor(int a, int b) {
    while (true) {
        if ((a = a % b) == 0) {
            return b;
        }
        if ((b = b % a) == 0) {
            return a;
        }
    }
}
迭代法3（再优雅一点）
int GCD(int a, int b) {
	if(b) while((a %= b) && (b %= a));
	return a + b;
}

最小公倍数

设两个数是a,b最大公约数是p,最小公倍数是q 那么有这样的关系:ab=pq

所以可以先求最大公因数，再求最小公倍数

递归法
int GCD(int a, int b)
{
	return a % b == 0 ? b : GCD(b, a % b);
}
int LCM(int a, int b)
{
	return a * b / GCD(a, b);
}
迭代法
int GCD(int a, int b) {
	if(b) while((a %= b) && (b %= a));
	return a + b;
}
int LCM(int a, int b) {
	return a * b / GCD(a, b);
}

判定素数

循环法
private static boolean isPrime(int num) {
    if (num < 2) {
        return false;
    } else if (num == 2) {
        return true;
    } else if (num % 2 == 0) {
        return false;
    }
    for (int i = 3; i * i <= num; i += 2) {
        if (num % i == 0) {
            return false;
        }
    }
    return true;
}
循环法（以空间换时间）

此方法适合一次生成，多次使用

private static boolean[] findPrime(int n) {
    boolean[] numList = new boolean[n + 1];    //index is range from 0 to n
    numList[0] = true;    // avoid mistake
    numList[1] = true;
    for (int i = 2; i < numList.length; i++) {
        // delete the multiple of prime numList[i], pirme = false
        if (!numList[i]) {
            for (int j = 2 * i; j < numList.length; j += i) {
                numList[j] = true;
            }
        }
    }
    return numList;
}

卡拉兹猜想

考拉兹猜想（英语：Collatz conjecture），又称为奇偶归一猜想、3n+1猜想、冰雹猜想、角谷猜想、哈塞猜想、乌拉姆猜想或叙拉古猜想，是指对于每一个正整数，如果它是奇数，则对它乘3再加1，如果它是偶数，则对它除以2，如此循环，最终都能够得到1。

这是一种迭代

迭代法
void collatz(int n){
  while(n > 1){
    System.out.print(n + "\t->\t");
    n = n % 2 == 0 ? n / 2 : n * 3 + 1;
  }
  System.out.print(1);
}

图形结构的算法：遍历：树和图的遍历方法

深度优先、广度优先、层次遍历，适用于树和图的遍历。只不过，对于图而言，要多用一个数组标记每一个节点是否访问过，防止重复遍历。

DFS

img

深度优先遍历/搜索（DFS），其对节点的访问过程是：首先不断向前递推然后回溯的过程，符合递归的思想，可以很容易的写成递归函数。所以DFS有2种写法：递归形式、非递归形式。

DFS递归形式

深度优先搜索的递归写法，比非递归的更常用（如果是图的话，要添加visit标记是否已访问过，如果是树的话不需要）

visited = set()
def dfs(node, visited):
    visited.add(node)
    # process current node here.
    ...
    for next_node in node:
        if not next_node in visited:
            dfs(next_node, visited)
DFS非递归形式

深度优先搜索的非递归写法，一般用栈实现

def dfs(tree):
    if tree.root is None:
        return []
    visited, stack = [], [tree.root]
    while stack:
        node = stack.pop(-1)
        visited.add(node)

        process(node)
        nodes = generate_related_nodes(node)
        stack.append(nodes)

图的深度优先遍历（Deep First Search），递归形式

/**
 * 深度优先遍历
 * @param s 表示遍历的源点
 */
private void DFS(int s) {
    //访问源点s
    visited[s] = true;
    //循环访问邻接的顶点
    //arc是m*2的二维数组，表示无向图有m条边，每条边连接2个顶点
    for (int i = 0; i < arc.length; i++) {
        if (arc[i][0] == s && !visited[arc[i][1]]) {
            //先访问邻接点的邻接点，再回过头来下一次循环
            DFS(arc[i][1]);
        }
        if (arc[i][1] == s && !visited[arc[i][0]]) {
            DFS(arc[i][0]);
        }
    }
}

BFS

img

一般的广度优先遍历（Breadth First Search），广度优先遍历非递归，使用队列实现

def bfs(graph, start, end):
    queue, visited = [], set() #visited用来判重，树结构不需要，
                               # 因为访问过的结点以后不会被访问到
    queue.append([start])
    visited.add(start)

    while queue:
        node = queue.pop(0) # 取队列头元素
        visited.add(node)

        process(node)
        nodes = generate_related_nodes(node)
        queue.append(nodes) # push进队列

树的算法

二叉树的遍历

参考二叉树的非递归遍历

一个二叉树节点最少包含如下三个属性：节点内容，左子节点句柄，右子节点句柄

public class BinaryTree<T> {
    private T value;
    private BinaryTree left;
    private BinaryTree right;
    //...
}

按一定的顺序访问二叉树的所有节点，称为二叉树的遍历，按访问节点的顺序分为：前序遍历，中序遍历，后序遍历，层次遍历。按实现方式可分为：递归实现，非递归实现。

其实想一下，二叉树遍历(前序/中序/后序，除了层次遍历），都符合树深度优先遍历（DFS）。仔细看一下，二叉树前序遍历的代码就是DFS的代码（只不过二叉树固定两个子节点，就没有用for循环，而是写了两次递归调用）。对于非递归形式，也一致。

前序递归遍历

先访问当前节点，再访问左子树，然后访问右子树

public String preOrderTraversalRecursive() {
    return this.toString()
            + (left != null ? left.preOrderTraversalRecursive() : "")
            + (right != null ? right.preOrderTraversalRecursive() : "");
}
前序非递归遍历

借助循环和栈可以控制节点访问顺序，模仿递归代码的执行顺序，实现非递归代码。

实现：循环判断当前节点是否为空，栈是否为空

void preOrder2(BinTree *root)     //非递归前序遍历 
{
    stack<BinTree*> s;
    BinTree *p=root;
    while(p!=NULL||!s.empty())
    {
        while(p!=NULL)
        {
            cout<<p->data<<"";
            s.push(p);
            p=p->lchild;
        }
        if(!s.empty())
        {
            p=s.top();
            s.pop();
            p=p->rchild;
        }
    }
}
中序递归遍历

先访问左子树，再访问当前节点，然后访问右子树

void inOrder1(BinTree *root)      //递归中序遍历
{
    if(root!=NULL)
    {
        inOrder1(root->lchild);
        cout<<root->data<<"";
        inOrder1(root->rchild);
    }
}
中序非递归遍历

循环判断当前节点是否为空，以及栈是否为空来实现

void inOrder2(BinTree *root)      //非递归中序遍历
{
    stack<BinTree*> s;
    BinTree *p=root;
    while(p!=NULL||!s.empty())
    {
        while(p!=NULL)
        {
            s.push(p);
            p=p->lchild;
        }
        if(!s.empty())
        {
            p=s.top();
            cout<<p->data<<"";
            s.pop();
            p=p->rchild;
        }
    }    
}
后序递归遍历

先访问左子树和右子树，再访问当前节点

void postOrder1(BinTree *root)    //递归后序遍历
{
    if(root!=NULL)
    {
        postOrder1(root->lchild);
        postOrder1(root->rchild);
        cout<<root->data<<"";
    }    
}
后序非递归遍历

后序遍历的非递归实现是三种遍历方式中最难的一种。因为在后序遍历中，要保证左孩子和右孩子都已被访问并且左孩子在右孩子前访问才能访问根结点，这就为流程的控制带来了难题。下面介绍两种思路。

第一种思路：对于任一结点P，将其入栈，然后沿其左子树一直往下搜索，直到搜索到没有左孩子的结点，此时该结点出现在栈顶，但是此时不能将其出栈并访问，因此其右孩子还为被访问。所以接下来按照相同的规则对其右子树进行相同的处理，当访问完其右孩子时，该结点又出现在栈顶，此时可以将其出栈并访问。这样就保证了正确的访问顺序。可以看出，在这个过程中，每个结点都两次出现在栈顶，只有在第二次出现在栈顶时，才能访问它。因此需要多设置一个变量标识该结点是否是第一次出现在栈顶。

思路一code：节点第二次出现在栈顶时，才访问它
void postOrder2(BinTree *root)    //非递归后序遍历
{
    stack s;
    BinTree *p=root;
    BTNode *temp;
    while(p!=NULL||!s.empty())
    {
        while(p!=NULL)              //沿左子树一直往下搜索，直至出现没有左子树的结点 
        {
            BTNode *btn=(BTNode *)malloc(sizeof(BTNode));
            btn->btnode=p;
            btn->isFirst=true;
            s.push(btn);
            p=p->lchild;
        }
        if(!s.empty())
        {
            temp=s.top();
            s.pop();
            if(temp->isFirst==true)     //表示是第一次出现在栈顶 
             {
                temp->isFirst=false;
                s.push(temp);
                p=temp->btnode->rchild;    
            }
            else//第二次出现在栈顶 
             {
                cout<btnode->data<<"";
                p=NULL;
            }
        }
    }    
}

第二种思路：要保证根结点在左孩子和右孩子访问之后才能访问，因此对于任一结点P，先将其入栈。如果P不存在左孩子和右孩子，则可以直接访问它；或者P存在左孩子或者右孩子，但是其左孩子和右孩子都已被访问过了，则同样可以直接访问该结点。若非上述两种情况，则将P的右孩子和左孩子依次入栈，这样就保证了每次取栈顶元素的时候，左孩子在右孩子前面被访问，左孩子和右孩子都在根结点前面被访问。

思路二code：入栈时保证右孩子先入栈，左孩子后入栈
void postOrder3(BinTree *root)     //非递归后序遍历
{
    stack s;
    BinTree *cur;                      //当前结点 
    BinTree *pre=NULL;                 //前一次访问的结点 
    s.push(root);
    while(!s.empty())
    {
        cur=s.top();
        if((cur->lchild==NULL&&cur->rchild==NULL)||
           (pre!=NULL&&(pre==cur->lchild||pre==cur->rchild)))
        {
            cout<data<<"";  //如果当前结点没有孩子结点或者孩子节点都已被访问过 
              s.pop();
            pre=cur; 
        }
        else
        {
            if(cur->rchild!=NULL)
                s.push(cur->rchild);
            if(cur->lchild!=NULL)    
                s.push(cur->lchild);
        }
    }    
}
层次遍历/BFS

参考：BFS、DFS和剪枝 1

二叉树的层次遍历属于BFS（层次遍历）的一种，参考BFS代码即可。

由遍历结果重建二叉树

由前序和中序遍历序列重建二叉树

参考：https://zhuanlan.zhihu.com/p/37265145

**问题描述：**输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建出如下图所示的二叉树并输出它的头结点。

解题思路：

在二叉树的前序遍历序列中，第一个数字总是树的根结点的值。但在中序遍历序列中，根结点的值在序列的中间，左子树的结点的值位于根结点的值的左边，而右子树的结点的值位于根结点的值的右边。因此我们需要扫描中序遍历序列，才能找到根结点的值。

　　前序遍历序列的第一个数字1就是根结点的值。扫描中序遍历序列，就能确定根结点的值的位置。根据中序遍历特点，在根结点的值1前面的3个数字都是左子树结点的值，位于1后面的数字都是右子树结点的值。

综上，我们可以分别找到根、左、右子树的前序遍历序列和中序遍历序列。 我们也可以用同样的方法分别去构建左右子树。换句话说，这是一个递归的过程。

int pre_order_arry[n];
int in_order_arry[n];
/* n为前序遍历和中序遍历子序列长度，pos1为前序数组下标，pos2为后序下标 */
void PrintPostOrder(int pos1, int pos2, int n)
{
    if (n == 1)
    {
        cout << pre_order_arry[pos1];
        return;
    }
    if (n == 0) return;
    int i = 0;
    for (; pre_order_arry[pos1] != in_order_arry[pos2 + i]; i++);
    PrintPostOrder(pos1 + 1, pos2, i);
    PrintPostOrder(pos1 + i + 1, pos2 + i + 1, n - i - 1);
    cout << pre_order_arry[pos1];
}

当然我们也可以根据前序和中序构造出二叉树，进而求出后序。

/* 该函数返回二叉树的根节点 */
Node * Create(int pos1, int pos2, int n)
{
    Node * p = nullptr;
    for (int i = 0; i < n; i++)
    {
        if (pre_order_arry[pos1] == in_order_arry[pos2+i])
        {
            p = new Node(pre_order_arry[pos1]);
            p->left = Create(pos1 + 1, pos2, i);
            p->right = Create(pos1 + i + 1, pos2 + i + 1, n - i - 1);
            return p;
        }
    }
    return p;
}
判断某序列是否为二叉搜索树的前序遍历

问题描述：给一个序列，它可能是一个正二叉搜索树的前序遍历，也可能是一个逆二叉搜索树的前序遍历，也可能什么都不是。题目要求给出判断结果，如果是前序的话，还要求给出后序遍历的结果。

题目链接

方法1 根据二叉搜索树前序遍历序列的特点来重建树/构造后序

正二叉搜索树有这样的特点：左子树上的值都比当前节点的值小，右子树上的值都大于等于（这道题包括等于的情况）当前节点 来 重建树/构造后序。 正二叉搜索树前序遍历的特点：第一个值是根节点；其后几个比第一个值小的都在左子树上；随后剩下的值比第一个值都大，都在右子树上。如果以上情况不成立，则给定的序列不是正二叉搜素树的前序遍历。对于左子树和右子树，同样递归判断。 逆二叉搜索树的情况与正二叉搜索树的情况类似。

方法1代码：根据二叉搜索树前序遍历序列的特点来重建树/构造后序
//不重建树，递归判断，同时构造后序
//牛客网牛友的提交 https://www.nowcoder.com/profile/986803/codeBookDetail?submissionId=5237150
#include 
using namespace std;
int pre[1001];
int post[1001];
int n;
bool bst(int begin,int end,int postBegin){
    int length=end-begin;
    if(length==1){
        post[postBegin]=pre[begin];
        return true;
    }
    if(length==0){
        return true;
    }
    int mid=begin+1;
    while(pre[mid]=pre[begin]&&mid=pre[begin]){
            return false;
        }
        else{
            last++;
        }
    }
    post[postBegin+length-1]=pre[begin];
    return mbst(begin+1,mid,postBegin)&&mbst(mid,end,postBegin+(mid-begin)-1);
}
int main(){
    //freopen("test.txt","r",stdin);
    cin>>n;
    for(int i=0;i
方法2 根据前序+中序遍历对应的二叉树的唯一性来做

假设给定的序列是二叉搜索树的前序序列，那么排序一下同时也得到了二叉搜索树的中序序列。 我们知道，已知前序+中序，对应的二叉树是唯一的。那么原问题就可以转化为：由前序+中序遍历重建二叉树/输出后序的问题

方法2代码：根据前序+中序遍历对应的二叉树的唯一性来做 
//已知前序+中序（隐含），对应的二叉树是唯一的。那么我们可以按前序序列的插入顺序重建二叉搜索树
//牛客网讨论区：https://www.nowcoder.com/questionTerminal/8bcd661314744321b55dce1c1bfa8c54
//下面是牛客网讨论区，RicardoZi的讨论代码：
#include 
#include 
using namespace std;
struct Node{
    int value;
    Node *left, *right;
};
void Insert(Node* &root, int data){
    if(root == NULL){
        root = new Node;
        root -> value = data;
        root -> left = NULL;
        root -> right = NULL;
        return;
    }
    if(data < root->value) Insert(root->left, data);
    else Insert(root->right, data);
}
void PreOrder(Node* root, vector& v){
    if(root == NULL) return;
    v.push_back(root->value);
    PreOrder(root->left, v);
    PreOrder(root->right, v);
}
void PreMirrorOrder(Node* root, vector& v){
    if(root == NULL) return;
    v.push_back(root->value);
    PreMirrorOrder(root->right, v);
    PreMirrorOrder(root->left, v);
}
void PostOrder(Node* root, vector& v){
    if(root == NULL) return;
    PostOrder(root->left, v);
    PostOrder(root->right, v);
    v.push_back(root->value);
}
void PostMirrorOrder(Node* root, vector& v){
    if(root == NULL) return;
    PostMirrorOrder(root->right, v);
    PostMirrorOrder(root->left, v);
    v.push_back(root->value);
}
int main(){
    int n;
    Node* s = NULL;
    scanf("%d", &n);
    vector num, pre, preM, post, postM;
    for(int i=0; i
根据中序遍历的栈操作顺序重建二叉树

问题描述：An inorder binary tree traversal can be implemented in a non-recursive way with a stack. For example, suppose that when a 6-node binary tree (with the keys numbered from 1 to 6) is traversed, the stack operations are: push(1); push(2); push(3); pop(); pop(); push(4); pop(); pop(); push(5); push(6); pop(); pop(). Then a unique binary tree (shown in Figure 1) can be generated from this sequence of operations. Your task is to give the postorder traversal sequence of this tree.

注意二叉树中序遍历时节点入栈顺序与二叉树前序遍历节点访问顺序一致（即，所有 Push 的节点组成的序列就是这棵树的先序遍历序列）。 中序遍历序列可以模拟栈操作获得，前序序列可以根据节点入栈顺序获得，于是问题转为从一棵树的先序遍历序列和中序遍历序列生成这棵树。

图的算法

连通子图

求解无向图的连通子图，一般有两种方法，一种是BFS或DFS遍历，另一种是并查集

连通子图个数（DFS方式）
/**
* 求连通子图个数
*/
public int countConnectedSubGraph() {
    int result = 0;
    //new数组默认都是false
    visited = new boolean[nodeNum + 1];
    for (int i = 1; i <= nodeNum; i++) {
        if (!visited[i]) {
            result++;
            DFS(i);
        }
    }
    return result;
}
/**
* 深度优先遍历
* @param s 表示遍历的源点
*/
private void DFS(int s) {
    visited[s] = true;
    for (int i = 0; i < arc.length; i++) {
        if (arc[i][0] == s && !visited[arc[i][1]]) {
            DFS(arc[i][1]);
        }
        if (arc[i][1] == s && !visited[arc[i][0]]) {
            DFS(arc[i][0]);
        }
    }
}
图中两顶点是否连通(并查集方式)

举例说明如下，假如一个图有9个顶点，7条边：(2,4),(5,7),(1,3),(8,9),(1,2),(5,6),(2,3)。

我们可以给每个顶点建立一个集合，表示最开始时他不知道任何顶点与它连通 。以后每次给出一条边(a, b)，则a所在的子图与b所在的子图就连通了，将a所在集合与b所在集合合并。对于样例数据的操作全过程如下：

初始状态：{1} {2} {3} {4} {5} {6} {7} {8} {9}

输入关系 分离集合

(2,4) {2,4}{1} {3} {5} {6} {7} {8} {9}

(5,7) {2,4} {5,7} {1} {3} {6} {8} {9}

(1,3) {1,3} {2,4} {5,7}{6} {8} {9}

(8,9) {1,3} {2,4} {5,7} {8,9}{6}

(1,2) {1,2,3,4} {5,7} {8,9}{6}

(5,6) {1,2,3,4} {5,6,7} {8,9}

(2,3) {1,2,3,4} {5,6,7} {8,9}

算法需要以下几个子过程：

(1) 开始时，为每个顶点建立一个集合；

(2) 得到一个关系a b，合并相应集合；

(3) 此外我们还需要判断两个顶点是否在同一个集合中，这就涉及到如何标识集合的问题。我们可以在每个集合中选一个代表标识集合（这里选集合中最小的顶点号作为集合/子图号）。

    /**
     * 存放每个顶点的组号，用于并查集判断两顶点是否连通
     */
    int[] father;

	public void setArc(int[][] arc) {
        this.arc = arc;
        //更新图连通状态
        for (int i = 0; i < arc.length; i++) {
            //存在一条边（a，b），则a，b顶点在同一个连通子图中，子图号默认使用其中最小的顶点号
            union(arc[i][0], arc[i][1]);
        }
    }

	/**
     * 存在一条边（a，b），则a，b顶点在同一个连通子图中，子图号默认使用其中最小的顶点号
     */
    private void union(int a, int b) {
        int x = findFather(a);
        int y = findFather(b);
        if (x < y) {
            father[y] = x;
        } else {
            father[x] = y;
        }
    }

    /**
     * 寻找顶点a所在的连通子图号（默认以子图中最小的顶点号指代）
     */
    public int findFather(int a) {
        while (a != father[a]) {
            a = father[a];
        }
        return a;
    }

递归实现

int findroot(int num,int JH[])
{
    if(JH[num]==-1) return num;
    else
    {
        int temp=findroot(JH[num],JH);
        JH[num]=temp;
        return temp;
    }
}

最短路径

最短路径问题是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。算法具体的形式包括：

  • 确定起点的最短路径问题 - 即已知起始结点，求最短路径的问题。适合使用Dijkstra算法。
  • 确定终点的最短路径问题 - 与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题。在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径方向反转的确定起点的问题。
  • 确定起点终点的最短路径问题 - 即已知起点和终点，求两结点之间的最短路径。
  • 全局最短路径问题 - 求图中所有的最短路径。适合使用Floyd-Warshall算法。

用于解决最短路径问题的算法被称做“最短路径算法”，有时被简称作“路径算法”。最常用的路径算法有：

Dijkstra算法

  1. 所有顶点集为V。 引入一个辅助数组(vector)D，每个元素D[i] 表示源点v到其它每个顶点$v_i$的长度。

    例如，D[3] = 2表示从起始点到顶点3的路径相对最小长度为2。这里强调相对就是说在算法执行过程中D的值是在不断逼近最终结果但在过程中不一定就等于最终长度。

    引入一个辅助集合S：表示已找到最短距离的顶点集。（一般也用数组实现）

  2. D的初始状态为： 若从源点v到$v_i$ 有弧（即从 v到 $v_i$存在连接边），则D[i]为弧上的权值（即为从v 到img 的边的权值）； 若从源点v 到img没有弧, 则置D[i] 为∞。 S的初始状态为$\varnothing$ 置源点到源点的距离为0: D[v] = 0

  3. 找最短的路径（长度）：D[j] = Min{ D[i] |$v_i$ ∈V-S } ，此路径为$(v,v_j)$, 即到顶点j 距离最短。

  4. 将对应的顶点j加入到S集，表示源点v到顶点j已是最短路径

  5. 更新V-S集顶点k的D值：对于${v_k|v_k \subset V-S}$,源点v到终点$v_k$, 最短路径要么是$(v,v_k)$, 要么是$(v,v_j,v_k)$。 即要么不经过顶点j，要么经过顶点j。那么当$D[j] + arc[v][j] < D[k]$时, 更新$D[k] =D[j] + arc[v][j]$ 。

  6. 若V-S集不为空，回到第三步，从非S集中继续寻找最短路径D[j]; 否则结束。

算法简化描述如下：

1）令arcs表示弧上的权值。若弧不存在，则置arcs为∞（在本程序中为MAXCOST）。S为已找到的从v 出发的的终点的集合，初始状态为空集。那么，从v 出发到图上其余各顶点img 可能达到的长度的初值为D=arcs[Locate Vex(G,img )]，img ∈V；

2）选择img ，使得Dimg =Min{ D |img ∈V-S } ；

3）修改从v 出发的到集合V-S中任一顶点img 的最短路径长度。

start=>start: Start:>http://www.google.com[blank]
end=>end: End
inputSource=>inputoutput: 输入源点
setupDS=>operation: 初始化当前各顶点到源点的最短距离D={∞,...}，标记各顶点到源点还不是最短visited={false,...}
input=>inputoutput: 输入各顶点的权值v[],顶点间距离c[][],源点
findMinDist=>subroutine: 从没有visited的顶点中，寻找到源点距离最短的顶点k
visitK=>operation: 标记顶点k已找到源点的最短距离：visited[k]=true
updateUnVisited=>subroutine: 更新未visited的顶点到源点的当前最短距离D[]
haveUnVisitedOrNot=>condition: 还有未visited的顶点吗？

start->inputSource->setupDS->input->findMinDist
findMinDist->visitK->updateUnVisited->haveUnVisitedOrNot
haveUnVisitedOrNot(yes)->findMinDist
haveUnVisitedOrNot(no)->end

举个例子：

对于无向图图g有4个顶点，5条边，顶点号为：0，1，2，3，边集{(start,end, distance,cost)} = {(0,1,1,20), (0,2,2,20), (0,3,4,10),(1,3,3,30), (2,3,1,20)}

假设要找从顶点0到顶点3的最短距离，花销，以及具体路径。下面是单源点最短路径Dijkstra算法的过程：

各顶点是否找到最但距离：visited[]源点（顶点0）到各顶点的距离： D[]源点（顶点0）到各顶点的花销： C[]各顶点的前一个顶点： P[]
初始化false, false, false, false$\infty$,$\infty$,$\infty$,$\infty$$\infty$,$\infty$,$\infty$,$\infty$-1, - 1, -1, -1
源点（顶点0）默认已找到最短距离,
加入到visited[],
同时更新D,C,P		true，false, false, false0,1,2,4
顶点0到顶点0距离为0，
顶点0到其他顶点有直接的边，边上的距离值设为顶点0到其他顶点的距离		0,20,20,10
顶点0到顶点0花销为0，
顶点0到其他顶点有直接的边，边上的花销值设为顶点0到其他顶点的花销		-1, 0, 0, 0
顶点0到其他顶点有直接的边，其他顶点都是从源点直接到达的，它们的前一个顶点都是源点0
选!visited[]且D,C最小值对应的顶点（顶点1），
加入到visited[],
同时更新D,C,P		true,true,false,false0,1,2,3
从源点0出发通过顶点1，再到达顶点3，比原来D[3]值更小		0,20,20,50
D值变化，根据路径变化同步修改C值		-1, 0, 0, 1
前面从源点0到顶点3的距离和花销发生变化的原因是路径发生了改变：从源点0出发通过顶点1，再到达顶点3，即顶点3的前一个顶点是1
选!visited[]且D,C最小值对应的顶点（顶点2），
加入到visited[],
同时更新D,C,P		true,true,true,false0,1,2,30,20,20,40
从源点0出发通过顶点2，再到达顶点3，和原来D[3]值一样大，但经过顶点2后C[3]更小		-1, 0, 0, 2
路径发生了改变：从源点0出发通过顶点2，再到达顶点3，即顶点3的前一个顶点是1
选!visited[]且D,C最小值对应的顶点（顶点3），
加入到visited[],
同时更新D,C,P		true,true,true,true0,1,2,30,20,20,40-1, 0, 0, 2
没有顶点!visited[]

则从源点0到顶点3的最短距离为D[3] = 3, 同时最小花销为C[3] = 40.

从各顶点的前一个顶点： P[] = {-1, 0, 0, 2},我们可以看出，顶点3的前一个顶点P[3] = 2, 顶点2的前一个顶点P[2] = 0, 顶点0的前一个顶点P[0] = -1, -1表示没有前一个顶点，即3<-2<-0,即从源点0到顶点3的最短路径为0->2->3.

#include<stdio.h>
#include<stdlib.h>
#define max1 10000000  //原词条这里的值太大，导致溢出，后面比较大小时会出错
int a[1000][1000];
int d[1000];//d表示源节点到该节点的最小距离
int p[1000];//p标记访问过的节点
int i, j, k;
int m;//m代表边数
int n;//n代表点数
int main()
{
    scanf("%d%d",&n,&m);
    int    min1;
    int    x,y,z;
    for(i=1;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&z);
        a[x][y]=z;
        a[y][x]=z;
    }
    for( i=1; i<=n; i++)
        d[i]=max1;
    d[1]=0;
    for(i=1;i<=n;i++)
    {
        min1 = max1;
        //下面这个for循环的功能类似冒泡排序，目的是找到未访问节点中d[j]值最小的那个节点，
        //作为下一个访问节点，用k标记
        for(j=1;j<=n;j++)
            if(!p[j]&&d[j]<min1)
            {
                min1=d[j];
                k=j;
            }
        //p[k]=d[k]; // 这是原来的代码，用下一 条代码替代。初始时，执行到这里k=1，而d[1]=0
       //从而p[1]等于0，这样的话，上面的循环在之后的每次执行之后，k还是等于1。
        p[k] = 1; //置1表示第k个节点已经访问过了
        for(j=1;j<=n;j++)
            if(a[k][j]!=0&&!p[j]&&d[j]>d[k]+a[k][j])
                d[j]=d[k]+a[k][j];
    }
    //最终输出从源节点到其他每个节点的最小距离
    for(i=1;i<n;i++)
        printf("%d->",d[i]);
    printf("%d\n",d[n]); 
    return 0;
}

相似的实现大学经典教材«数据结构»(C语言版 严蔚敏 吴为民 编著) 中该算法的实现

/*
测试数据 教科书 P189 G6 的邻接矩阵 其中 数字 1000000 代表无穷大
6
1000000 1000000 10 100000 30 100
1000000 1000000 5 1000000 1000000 1000000
1000000 1000000 1000000 50 1000000 1000000
1000000 1000000 1000000 1000000 1000000 10
1000000 1000000 1000000 20 1000000 60
1000000 1000000 1000000 1000000 1000000 1000000
结果：
D[0]   D[1]   D[2]   D[3]   D[4]   D[5]
 0   1000000   10     50     30     60
*/
#include <iostream>
#include <cstdio>
#define MAX 1000000
using namespace std;
int arcs[10][10];//邻接矩阵
int D[10];//保存最短路径长度
int p[10][10];//路径
int final[10];//若final[i] = 1则说明 顶点vi已在集合S中
int n = 0;//顶点个数
int v0 = 0;//源点
int v,w;
void ShortestPath_DIJ()
{
     for (v = 0; v < n; v++) //循环 初始化
     {
          final[v] = 0; D[v] = arcs[v0][v];
          for (w = 0; w < n; w++) p[v][w] = 0;//设空路径
          if (D[v] < MAX) {p[v][v0] = 1; p[v][v] = 1;}
     }
     D[v0] = 0; final[v0]=1; //初始化 v0顶点属于集合S
     //开始主循环 每次求得v0到某个顶点v的最短路径 并加v到集合S中
     for (int i = 1; i < n; i++)
     {
          int min = MAX;
          for (w = 0; w < n; w++)
          {
               //我认为的核心过程--选点
               if (!final[w]) //如果w顶点在V-S中
               {
                    //这个过程最终选出的点 应该是选出当前V-S中与S有关联边
                    //且权值最小的顶点 书上描述为 当前离V0最近的点
                    if (D[w] < min) {v = w; min = D[w];}
               }
          }
          final[v] = 1; //选出该点后加入到合集S中
          for (w = 0; w < n; w++)//更新当前最短路径和距离
          {
               /*在此循环中 v为当前刚选入集合S中的点
               则以点V为中间点 考察 d0v+dvw 是否小于 D[w] 如果小于 则更新
               比如加进点 3 则若要考察 D[5] 是否要更新 就 判断 d(v0-v3) + d(v3-v5) 的和是否小于D[5]
               */
               if (!final[w] && (min+arcs[v][w]<D[w]))
               {
                    D[w] = min + arcs[v][w];
                   // p[w] = p[v];
                    p[w][w] = 1; //p[w] = p[v] +　[w]
               }
          }
     }
}
 
 
int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
    {
         for (int j = 0; j < n; j++)
         {
              cin >> arcs[i][j];
         }
    }
    ShortestPath_DIJ();
    for (int i = 0; i < n; i++) printf("D[%d] = %d\n",i,D[i]);
    return 0;
}
A*算法

A* 算法使用了启发式信息：到目标的距离

Dijkstra 算法和它的升级版 A* 算法得到的结果是一样的，即所有节点的值在更新后是相同的。

香侬告诉我们，信息可以消除不确定性。其实，信息还可以提高算法的效率。因为我们都有这样的经验：信息越充分，决策越容易成功。A 算法仅仅将非常简单的启发式信息引入了Dijkstra 算法，就能大幅降低待处理节点的数量，从而极大的提高了效率。*

A 算法详解*1译文摘录：

概述

虽然掌握了 A* 算法的人认为它容易，但是对于初学者来说， A* 算法还是很复杂的。

搜索区域(The Search Area)

我们假设某人要从 A 点移动到 B 点，但是这两点之间被一堵墙隔开。如图 1 ，绿色是 A ，红色是 B ，中间蓝色是墙。

image001.jpg

图 1

你应该注意到了，我们把要搜寻的区域划分成了正方形的格子。这是寻路的第一步，简化搜索区域，就像我们这里做的一样。这个特殊的方法把我们的搜索区域简化为了 2 维数组。数组的每一项代表一个格子，它的状态就是可走 (walkalbe) 和不可走 (unwalkable) 。通过计算出从 A 到 B需要走过哪些方格，就找到了路径。一旦路径找到了，人物便从一个方格的中心移动到另一个方格的中心，直至到达目的地。

方格的中心点我们成为“节点 (nodes) ”。如果你读过其他关于 A* 寻路算法的文章，你会发现人们常常都在讨论节点。为什么不直接描述为方格呢？因为我们有可能把搜索区域划为为其他多变形而不是正方形，例如可以是六边形，矩形，甚至可以是任意多变形。而节点可以放在任意多边形里面，可以放在多变形的中心，也可以放在多边形的边上。我们使用这个系统，因为它最简单。

一旦我们把搜寻区域简化为一组可以量化的节点后，就像上面做的一样，我们下一步要做的便是查找最短路径。在 A* 中，我们从起点开始，检查其相邻的方格，然后向四周扩展，直至找到目标。

我们这样开始我们的寻路旅途：

  1. 从起点 A 开始，并把它就加入到一个由方格组成的 open list( 开放列表 ) 中。这个 open list 有点像是一个购物单。当然现在 open list 里只有一项，它就是起点 A ，后面会慢慢加入更多的项。 Open list 里的格子是路径可能会是沿途经过的，也有可能不经过。基本上 open list 是一个待检查的方格列表。

  2. 查看与起点 A 相邻的方格 ( 忽略其中墙壁所占领的方格，河流所占领的方格及其他非法地形占领的方格 ) ，把其中可走的 (walkable) 或可到达的 (reachable) 方格也加入到 open list 中。把起点 A 设置为这些方格的父亲 (parent node 或 parent square) 。当我们在追踪路径时，这些父节点的内容是很重要的。稍后解释。

  3. 把 A 从 open list 中移除，加入到 close list( 封闭列表 ) 中， close list 中的每个方格都是现在不需要再关注的。

如下图所示，深绿色的方格为起点，它的外框是亮蓝色，表示该方格被加入到了 close list 。与它相邻的黑色方格是需要被检查的，他们的外框是亮绿色。每个黑方格都有一个灰色的指针指向他们的父节点，这里是起点 A 。

image002.jpg

图 2 。

下一步，我们需要从 open list 中选一个与起点 A 相邻的方格，按下面描述的一样或多或少的重复前面的步骤。但是到底选择哪个方格好呢？具有最小 F 值的那个。

路径排序(Path Sorting)

计算出组成路径的方格的关键是下面这个等式：

F = G + H

这里，

G = 从起点 A 移动到指定方格的移动代价，沿着到达该方格而生成的路径。

H = 从指定的方格移动到终点 B 的估算成本。这个通常被称为试探法，有点让人混淆。为什么这么叫呢，因为这是个猜测。直到我们找到了路径我们才会知道真正的距离，因为途中有各种各样的东西 ( 比如墙壁，水等 ) 。本教程将教你一种计算 H 的方法，你也可以在网上找到其他方法。

我们的路径是这么产生的：反复遍历 open list ，选择 F 值最小的方格。这个过程稍后详细描述。我们还是先看看怎么去计算上面的等式。

如上所述， G 是从起点Ａ移动到指定方格的移动代价。在本例中，横向和纵向的移动代价为 10 ，对角线的移动代价为 14 。之所以使用这些数据，是因为实际的对角移动距离是 2 的平方根，或者是近似的 1.414 倍的横向或纵向移动代价。使用 10 和 14 就是为了简单起见。比例是对的，我们避免了开放和小数的计算。这并不是我们没有这个能力或是不喜欢数学。使用这些数字也可以使计算机更快。稍后你便会发现，如果不使用这些技巧，寻路算法将很慢。

既然我们是沿着到达指定方格的路径来计算 G 值，那么计算出该方格的 G 值的方法就是找出其父亲的 G 值，然后按父亲是直线方向还是斜线方向加上 10 或 14 。随着我们离开起点而得到更多的方格，这个方法会变得更加明朗。

有很多方法可以估算 H 值。这里我们使用 Manhattan 方法，计算从当前方格横向或纵向移动到达目标所经过的方格数，忽略对角移动，然后把总数乘以 10 。之所以叫做 Manhattan 方法，是因为这很像统计从一个地点到另一个地点所穿过的街区数，而你不能斜向穿过街区。重要的是，计算 H 是，要忽略路径中的障碍物。这是对剩余距离的估算值，而不是实际值，因此才称为试探法。

把 G 和 H 相加便得到 F 。我们第一步的结果如下图所示。每个方格都标上了 F ， G ， H 的值，就像起点右边的方格那样，左上角是 F ，左下角是 G ，右下角是 H 。

image003.jpg

图 3

好，现在让我们看看其中的一些方格。在标有字母的方格， G = 10 。这是因为水平方向从起点到那里只有一个方格的距离。与起点直接相邻的上方，下方，左方的方格的 G 值都是 10 ，对角线的方格 G 值都是 14 。

H 值通过估算起点于终点 ( 红色方格 ) 的 Manhattan 距离得到，仅作横向和纵向移动，并且忽略沿途的墙壁。使用这种方式，起点右边的方格到终点有 3 个方格的距离，因此 H = 30 。这个方格上方的方格到终点有 4 个方格的距离 ( 注意只计算横向和纵向距离 ) ，因此 H = 40 。对于其他的方格，你可以用同样的方法知道 H 值是如何得来的。

每个方格的 F 值，再说一次，直接把 G 值和 H 值相加就可以了。

为了继续搜索，我们从 open list 中选择 F 值最小的 ( 方格 ) 节点，然后对所选择的方格作如下操作：

  1. 把它从 open list 里取出，放到 close list 中。

  2. 检查所有与它相邻的方格，忽略其中在 close list 中或是不可走 (unwalkable) 的方格 ( 比如墙，水，或是其他非法地形 ) ，如果方格不在open lsit 中，则把它们加入到 open list 中。

把我们选定的方格设置为这些新加入的方格的父亲。

  1. 如果某个相邻的方格已经在 open list 中，则检查这条路径是否更优，也就是说经由当前方格 ( 我们选中的方格 ) 到达那个方格是否具有更小的 G 值。如果没有，不做任何操作。

相反，如果 G 值更小，则把那个方格的父亲设为当前方格 ( 我们选中的方格 ) ，然后重新计算那个方格的 F 值和 G 值。如果你还是很混淆，请参考下图。

image004.jpg

图 4

Ok ，让我们看看它是怎么工作的。在我们最初的 9 个方格中，还有 8 个在 open list 中，起点被放入了 close list 中。在这些方格中，起点右边的格子的 F 值 40 最小，因此我们选择这个方格作为下一个要处理的方格。它的外框用蓝线打亮。

首先，我们把它从 open list 移到 close list 中 ( 这就是为什么用蓝线打亮的原因了 ) 。然后我们检查与它相邻的方格。它右边的方格是墙壁，我们忽略。它左边的方格是起点，在 close list 中，我们也忽略。其他 4 个相邻的方格均在 open list 中，我们需要检查经由这个方格到达那里的路径是否更好，使用 G 值来判定。让我们看看上面的方格。它现在的 G 值为 14 。如果我们经由当前方格到达那里， G 值将会为 20(其中 10 为到达当前方格的 G 值，此外还要加上从当前方格纵向移动到上面方格的 G 值 10) 。显然 20 比 14 大，因此这不是最优的路径。如果你看图你就会明白。直接从起点沿对角线移动到那个方格比先横向移动再纵向移动要好。

当把 4 个已经在 open list 中的相邻方格都检查后，没有发现经由当前方格的更好路径，因此我们不做任何改变。现在我们已经检查了当前方格的所有相邻的方格，并也对他们作了处理，是时候选择下一个待处理的方格了。

因此再次遍历我们的 open list ，现在它只有 7 个方格了，我们需要选择 F 值最小的那个。有趣的是，这次有两个方格的 F 值都 54 ，选哪个呢？没什么关系。从速度上考虑，选择最后加入 open list 的方格更快。这导致了在寻路过程中，当靠近目标时，优先使用新找到的方格的偏好。但是这并不重要。 ( 对相同数据的不同对待，导致两中版本的 A* 找到等长的不同路径 ) 。

我们选择起点右下方的方格，如下图所示。

image005.jpg

图 5

这次，当我们检查相邻的方格时，我们发现它右边的方格是墙，忽略之。上面的也一样。

我们把墙下面的一格也忽略掉。为什么？因为如果不穿越墙角的话，你不能直接从当前方格移动到那个方格。你需要先往下走，然后再移动到那个方格，这样来绕过墙角。 ( 注意：穿越墙角的规则是可选的，依赖于你的节点是怎么放置的 )

这样还剩下 5 个相邻的方格。当前方格下面的 2 个方格还没有加入 open list ，所以把它们加入，同时把当前方格设为他们的父亲。在剩下的3 个方格中，有 2 个已经在 close list 中 ( 一个是起点，一个是当前方格上面的方格，外框被加亮的 ) ，我们忽略它们。最后一个方格，也就是当前方格左边的方格，我们检查经由当前方格到达那里是否具有更小的 G 值。没有。因此我们准备从 open list 中选择下一个待处理的方格。

不断重复这个过程，直到把终点也加入到了 open list 中，此时如下图所示。

image006.jpg

图 6

注意，在起点下面 2 格的方格的父亲已经与前面不同了。之前它的 G 值是 28 并且指向它右上方的方格。现在它的 G 值为 20 ，并且指向它正上方的方格。这在寻路过程中的某处发生，使用新路径时 G 值经过检查并且变得更低，因此父节点被重新设置， G 和 F 值被重新计算。尽管这一变化在本例中并不重要，但是在很多场合中，这种变化会导致寻路结果的巨大变化。

那么我们怎么样去确定实际路径呢？很简单，从终点开始，按着箭头向父节点移动，这样你就被带回到了起点，这就是你的路径。如下图所示。从起点 A 移动到终点 B 就是简单从路径上的一个方格的中心移动到另一个方格的中心，直至目标。就是这么简单！

image007.jpg

图 7

A算法总结(Summary of the A Method)

Ok ，现在你已经看完了整个的介绍，现在我们把所有步骤放在一起：

  1. 把起点加入 open list 。

  2. 重复如下过程：

    a. 遍历 open list ，查找 F 值最小的节点，把它作为当前要处理的节点。

    b. 把这个节点移到 close list 。

    c. 对当前方格的 8 个相邻方格的每一个方格？

    ​ ◆ 如果它是不可抵达的或者它在 close list 中，忽略它。否则，做如下操作。

    ​ ◆ 如果它不在 open list 中，把它加入 open list ，并且把当前方格设置为它的父亲，记录该方格的 F ， G 和 H 值。

    ​ ◆ 如果它已经在 open list 中，检查这条路径 ( 即经由当前方格到达它那里 ) 是否更好，用 G 值作参考。更小的 G 值表示这是更好的路径。如果是这样，把它的父亲设置为当前方格，并重新计算它的 G 和 F 值。如果你的 open list 是按 F 值排序的话，改变后你可能需要重新排序。

    d. 停止，当你

    ​ ◆ 把终点加入到了 open list 中，此时路径已经找到了，或者

    ​ ◆ 查找终点失败，并且 open list 是空的，此时没有路径。

  3. 保存路径。从终点开始，每个方格沿着父节点移动直至起点，这就是你的路径。

Dijkstra算法和A*算法的比较

Dijkstra算法和A* 算法都是最短路径问题的常用算法，下面就对这两种算法的特点进行一下比较。 1.Dijkstra算法计算源点到其他所有点的最短路径长度，A* 关注点到点的最短路径(包括具体路径)。 2.Dijkstra算法建立在较为抽象的图论层面，A* 算法可以更轻松地用在诸如游戏地图寻路中。 3.Dijkstra算法的实质是广度优先搜索，是一种发散式的搜索，所以空间复杂度和时间复杂度都比较高。对路径上的当前点，A* 算法不但记录其到源点的代价，还计算当前点到目标点的期望代价，是一种启发式算法，也可以认为是一种深度优先的算法。 4.由第一点，当目标点很多时，A* 算法会带入大量重复数据和复杂的估价函数，所以如果不要求获得具体路径而只比较路径长度时，Dijkstra算法会成为更好的选择。

Floyd-Warshall算法

参考：https://www.cnblogs.com/wangyuliang/p/9216365.html

参考：https://houbb.github.io/2020/01/23/data-struct-learn-03-graph-floyd#:~:text=Floyd%2DWarshall%E7%AE%97%E6%B3%95%EF%BC%88Floyd%2D,O(N%5E2)%E3%80%82

Floyd算法是求多源最短路径的算法。一次获取所有的两点之间最短距离。

过程

现在需要一个数据结构来存储图的信息，我们仍然可以用一个4*4的矩阵（二维数组e）来存储。比如1号城市到2号城市的路程为2，则设e[1][2]的值为2。2号城市无法到达4号城市，则设置e[2][4]的值为∞。另外此处约定一个城市自己是到自己的也是0，例如e[1][1]为0，具体如下。

img

当任意两点之间不允许经过第三个点时，这些城市之间最短路程就是初始路程，如下。

img

​

假如现在只允许经过1号顶点，求任意两点之间的最短路程，应该如何求呢？只需判断e[i][1]+e[1][j]是否比e[i][j]要小即可。e[i][j]表示的是从i号顶点到j号顶点之间的路程。e[i][1]+e[1][j]表示的是从i号顶点先到1号顶点，再从1号顶点到j号顶点的路程之和。其中i是1~n循环，j也是1~n循环，代码实现如下。

for (i = 1; i <= n; i++)
{
    for (j = 1; j <= n; j++)
    {
        if (e[i][j] > e[i][1] + e[1][j])
            e[i][j] = e[i][1] + e[1][j];
    }
}

在只允许经过1号顶点的情况下，任意两点之间的最短路程更新为：

img

​ 通过上图我们发现：在只通过1号顶点中转的情况下，3号顶点到2号顶点（e[3][2]）、4号顶点到2号顶点（e[4][2]）以及4号顶点到3号顶点（e[4][3]）的路程都变短了。

​ 接下来继续求在只允许经过1和2号两个顶点的情况下任意两点之间的最短路程。如何做呢？我们需要在只允许经过1号顶点时任意两点的最短路程的结果下，再判断如果经过2号顶点是否可以使得i号顶点到j号顶点之间的路程变得更短。即判断e[i][2]+e[2][j]是否比e[i][j]要小，代码实现为如下。

//经过1号顶点
for(i=1;i<=n;i++)  
    for(j=1;j<=n;j++)  
        if (e[i][j] > e[i][1]+e[1][j])  e[i][j]=e[i][1]+e[1][j];  
//经过2号顶点
for(i=1;i<=n;i++)  
    for(j=1;j<=n;j++)  
        if (e[i][j] > e[i][2]+e[2][j])  e[i][j]=e[i][2]+e[2][j];

在只允许经过1和2号顶点的情况下，任意两点之间的最短路程更新为：

img

​ 通过上图得知，在相比只允许通过1号顶点进行中转的情况下，这里允许通过1和2号顶点进行中转，使得e[1][3]和e[4][3]的路程变得更短了。

​ 同理，继续在只允许经过1、2和3号顶点进行中转的情况下，求任意两点之间的最短路程。任意两点之间的最短路程更新为：

img

​ 最后允许通过所有顶点作为中转，任意两点之间最终的最短路程为：

img

​ 整个算法过程虽然说起来很麻烦，但是代码实现却非常简单，核心代码只有五行：

for(k=1;k<=n;k++)  
    for(i=1;i<=n;i++)  
        for(j=1;j<=n;j++)  
            if(e[i][j]>e[i][k]+e[k][j])  
                e[i][j]=e[i][k]+e[k][j];

这段代码的基本思想就是：最开始只允许经过1号顶点进行中转，接下来只允许经过1和2号顶点进行中转……允许经过1~n号所有顶点进行中转，求任意两点之间的最短路程。用一句话概括就是：从i号顶点到j号顶点只经过前k号点的最短路程。

#include
int main()
{
    int e[10][10],k,i,j,n,m,t1,t2,t3;
    int inf=99999999; //用inf(infinity的缩写)存储一个我们认为的正无穷值
    //读入n和m，n表示顶点个数，m表示边的条数
    scanf("%d %d",&n,&m);
    //初始化
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            if(i==j) e[i][j]=0;
    else e[i][j]=inf;
    //读入边
    for(i=1;i<=m;i++)
    {
        scanf("%d %d %d",&t1,&t2,&t3);
        e[t1][t2]=t3;
    }
    //Floyd-Warshall算法核心语句
    for(k=1;k<=n;k++)
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
                if(e[i][j]>e[i][k]+e[k][j] )
                    e[i][j]=e[i][k]+e[k][j];
    //输出最终的结果
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
        {
            printf("%10d",e[i][j]);
        }
        printf("\n");
    }
    return 0;
}

最长路径

图的最长路径 –BFS,树,图

我们先把图的遍历过程看作是一个遍历树，起点随机：

img

这里强调：遍历树的根节点肯定在最高遍历树上（废话），而且该节点遍历的最深的叶子节点肯定是最高遍历树的根节点（可能有多个） 可以看成，随机选取的节点就是从最高遍历树中的某个节点开始进行搜索的

img

以上图为例，随机选取一个节点，广度优先遍历（这样可以知道哪些节点层数最深），找到深度最深（最后遍历）的节点，多个的话可以随机选一个，然后基于这个最后的节点为起始节点，重新进行遍历，记录层数，就是图的直径（最长路径）了。

牛客网JacobGo！的讨论

从任意一个节点开始进行深度优先遍历，找到离他最远的节点（可能不止一个，记为集合A）；第二步：再从A中任意选一个节点出发进行深度优先遍历，找到离他最远的节点（记为集合B），最后最深根就是这两个集合的并集。

按算法的思路来划分（算法思想）

参考：常用算法指南(一)基本算法思想

参考：八大算法思想

参考：12种常见算法思想汇总

  • 穷举算法思想;
  • 递推算法思想;
  • 递归算法思想;
  • 分治算法思想;
  • 概率算法思想;

递归的思想

递归的思想

简单说，递归就是一个函数反复的“自己调用自己”。

img

递归的要求

把问题分解成规模更小，但和原问题有着相同解法的问题。 存在一个能让递归调用退出的简单出口。

注意：分治的思想是把问题分解成规模更小的问题（不一定是相同解法/类型的问题）

递归的过程

1)递推:把复杂的问题的求解推到比原问题简单一些的问题的求解; 2)回归:当获得最简单的情况后, 逐步返回, 依次得到复杂的解

递归的优点

递归代码一般比较精炼，便于阅读。

递归的缺点

需要系统堆栈，且压入栈的内容得不到释放，所以空间消耗要比非递归代码要大很多。 而且，如果递归深度太大，可能会造成栈溢出

递归的实现机制

递归导致一个函数反复调用自己，我们知道函数调用是通过一个栈来实现的。（局部变量或其引用也保存在栈上） 在大多数机器上，每次调用函数时大致要做三个工作：调用前先保存寄存器，并在返回时恢复；复制实参；程序必须转向一个新位置执行。 所以函数调用的压栈操作：保存局部变量、寄存器值、返回地址、实参。 函数嵌套或递归调用，则压入栈中的数据会很多；栈中较底部的变量/引用的对象都没被释放，开销大且可能栈溢出。

img

为了防止无穷递归现象，有些语言是规定栈的长度的，比如python语言规定堆栈的长度不能超过1000。 还有就是当规 模很大的时候，尽量不使用递归，而改为非递归的形式。 或者优化成尾递归的形式。

注：这里的实现机制是c语言、java等的机制；Lisp等提倡递归使用的语言并不适用

递归的效率

从上面递归的实现机制来看，递归函数反复调用自己，现场的保存与恢复非常消耗栈内存以及时间。 递归把问题分解成规模更小，但和原问题有着相同解法的问题的过程中，遇到同样的子问题会重复计算浪费时间。（这一点可以通过边递归边保存结果来优化）

递归的复杂度分析

算法导论——递归算法的时间复杂度求解

递归算法的时间复杂度终结篇

递归与非递归的转换

参考：漫谈递归转非递归

参考：https://blog.csdn.net/Shunrei/article/details/5680579

参考：https://www.cnblogs.com/TECHNOLOGYer/p/4776496.html

简单递归，不借助栈，用直接转换法，或消除尾递归的方式转换为非递归。

复杂递归，借助栈，转换为非递归。

简单递归转非递归：直接转换法/不借助栈法

简单递归转换为非递归：如果是尾递归，直接转换；其他简单递归，可以直接转换，也可以先转尾递归再转换为非递归。

简单递归概念

单向递归/线性递归/简单递归：指递归调用的过程总是朝着一个方向进行（如果函数１调用了函数２,而函数２又调用了函数１,则这种情况不属于单向递归。斐波那契数列的递归求解可转用一个迭代法实现）。 这类递归一般可以找到递推公式（这也就引申出分治思想和动态规划），可以使用直接转换法转换为非递归，并不需要借助栈，所以又叫简单递归。

尾递归概念

尾递归函数是以递归调用结尾的函数，函数的调用返回都集中在尾部（最后一步操作是递归），是单向递归的特例。

直接转换法

直接转换法将简单递归(包括尾递归）转换为循环，并使用一些变量保存中间结果。（不借助栈）

尾递归的直接转换

尾递归在尾部调用，其实是具有迭代特性的递归，时间复杂度为O(n).那么一定要有迭代的统计步数。我们记录当统计步数到达临界条件时，就退出.

尾递归可以直接地改成迭代的形式。很多编译器都能够将尾递归的形式优化成循环的形式。

非尾递归的直接转换法

一般是根据递推关系来转换

比如斐波那契数列：fib(n) = fib(n-1) + fib(n-2)

递归形式：

int fib(int n) {
    if(n==1||n==2) {
        //简单情形，递归出口
        return n;
    }else {
        //递归调用：最后一个动作时是加法（不是尾递归）
        return fib(n-1)+fib(n-2);
    }
}

根据递推关系，直接转换为非递归

int fib(int n) {
    if(n <= 1) return n;
    int twoBack = 0;
    int oneBack = 1;
    int cur;
    for(int i = 2;i < = n; i++) {
        cur = twoBack + oneBack;
        twoBack = oneBack;
        oneBack = cur;
    }
    return cur;
}
直接转换补充思路：先转尾递归，再转非递归

简单递归问题，如阶乘问题和斐波那契数列数列问题。这些问题，一般都可以优化成尾递归的形式，再转换成迭代形式（循环结构）。

比如斐波那契数列：fib(n) = fib(n-1) + fib(n-2)

递归形式：

int fib(int n) {
    if(n==1||n==2) {
        //简单情形，递归出口
        return n;
    }else {
        //递归调用：最后一个动作时是加法（不是尾递归）
        return fib(n-1)+fib(n-2);
    }
}

尾递归：统计步数从简单情境递增到n

int fact(int n, int i, int ret)
{
    if (n < 1)
        return -1;
    if (n == 1)
        return n;
    else if (i == n)
        return i*ret;
    else return fact(n, i + 1, ret*i);
}
//调用过程
//fact(5, 1, 1)
//fact(5, 2, 1)
//fact(5, 3, 2)
//fact(5, 4, 6)
//fact(5, 5, 24)

尾递归：统计步数从n递减到简单情境

int fact1(int n, int i, int ret) 
{
    if (n == 0)
        return ret;
    else return fact1(n-1, i + 1, ret * i);
}
//调用过程
//fact1(5, 1, 1)
//fact1(4, 2, 1)
//fact1(3, 3, 2)
//fact1(2, 4, 6)
//fact1(1, 5, 24)
//fact1(0, 6, 120)

尾递归效率已经和迭代差不多了。

进一步，使用尾递归直接转换为迭代。略

复杂递归转非递归：间接转换法/借助栈法

参考：https://www.cnblogs.com/zhaoshuai1215/p/3164698.html

参考：https://www.cnblogs.com/zhaoshuai1215/p/3165699.html

复杂递归/树形递归：一般是同一类递归，这类递归转非递归必须要借助栈。可以将递归问题看作一棵树，例如快速排序，整个排序问题分割成左右两部分，每一部分又分割成两部分，类似于二叉树。递归问题的求解可以是由树根到叶子的自顶向下方式求解，如快排，也可以是由叶子节点到根节点的自底向上方式求解。再进一步，可以把递归问题的求解方式按照树的遍历方式分成三种，分别是前序遍历、中序遍历和后序遍历。

实际上，借助栈，将可以将所有递归转化为非递归。（PS：简单递归的情况严格意义上来说不能看做是一种情况）。

借助栈为非递归有两种转化方法：

  • 借助堆栈模拟递归的执行过程。这种方法几乎是通用的方法，因为递归本身就是通过栈实现的，用栈模拟函数调用是一种很自然的方法。
  • 借助堆栈的循环结构算法/类二叉树非递归遍历算法。这种方法常常适用于某些局部变量有依赖关系，且需要重复执行的场景，例如二叉树的遍历算法。递归函数可以写出递归调用树，再根据访问各节点的次序，类比二叉树的前序、中序、后序非递归遍历，写出相应的代码。
借助堆栈模拟递归的执行过程

参考：https://www.cnblogs.com/bakari/p/5349383.html

递归的过程其实是编译器帮我们处理了压栈和出栈的操作，转换为非递归函数就需要另外建栈，手动地处理压栈和出栈。

因此，我们可以很自然的想到：借助堆栈模拟递归的执行过程。这种方法几乎是通用的方法，因为递归本身就是通过堆栈实现的，我们只要把递归函数调用的局部变量和相应的状态放入到一个栈结构中，在函数调用和返回时做好push和pop操作，就可以了（后面是一个模拟快排的例子）。

快排的模拟递归示例
void qsort(int a[],int l,int r){
    //boundary case
    if(l>=r)       
        return;
    //state 0
    int mid=partition(a,l,r); 
    qsort(a,l,mid-1);
    //state 1
    qsort(a,mid+1,r);         
    //state 2
}

模拟递归调用过程。因为递归本身就是通过堆栈实现的，我们只要把递归函数调用的局部变量和相应的状态放入到一个栈结构中，在函数调用和返回时做好push和pop操作，就可以了

快排的非递归实现（根据递归结构设置了几个状态）

struct recorc{
    int l,r,mid; //local virables.
    int state;
}stack[100000];
void nun_recursive_qsort(int a[],int l,int r){
    int state=0,top=0;
    int mid;
    while(1){
        if(l>=r){ //boundary case, return previous level
            if(top == 0)
                break;//end of recursion
            top--;
            l=stack[top].l;//end of function, update to previous state
            r=stack[top].r;
            mid=stack[top].mid;
            state=stack[top].state;
        }
        else if(state == 0){
            mid=partition(a,l,r);
            stack[top].l=l;    //recutsive call, push current state into stack
            stack[top].r=r;
            stack[top].mid=mid;
            stack[top].state=1;
            top++;
            r=mid-1;
            state=0; //don't forget to update state value
        }
        else if(state == 1){
            stack[top].l=l;        
            stack[top].r=r;     //recursive call, push current state into stack
            stack[top].mid=mid;
            stack[top].state=2;
            top++;
            l=mid+1;
            state=0;
        }
        else if(state == 2){
            if(top == 0)
                break;  //end of recursion
            top--;
            l=stack[top].l;
            r=stack[top].r;
            mid=stack[top].mid;
            state=stack[top].state;
        }
    }
}
//借助堆栈人工模拟快排
模拟递归函数执行的模板

比如递归函数的形式：

int recursive(int x) {
    //前导代码
    //。。。
    
    if(hhh) {
        //递归结束条件
        //...
    }
    else if(xxx) {
        //其他情况
        //。。。
    }else {
        //递归,并做一些操作
        operation(recursive(x+offset));
    }
    
    //收尾代码
    //。。。
}

递推的过程，其实是：递推+回溯

使用循环模拟执行过程：

int nonRecursive(int x) {
    Stack<States> stack = new Stack<>();
    states = 。。。
    stack.push(states);
    //回溯
    while(!stack.isEmpty()) {
    	states = stack.pop();
        
        //向下递推的情况
        while(!{递归结束条件}) {
            //前导代码
            //。。。
            
            //当前状态入栈
            stack.push(states);
        }
        
        //递归结束条件
        if(hhh){
            //。。。
        }
        //其他情况
        else if(xxx){
            //。。。
        }
        
        //收尾代码
        //。。。
    }
}
借助堆栈的循环结构算法/树的非递归遍历算法

还是以快排算法为例，根据快排算法的递归示例，它的递归调用树是二叉树前序遍历的形式。

那么我们只需要把二叉树的前序遍历代码搬过来，partition()过程替换visit()过程即可。

动态规划的思想

参考：算法笔记-胡凡：提高篇（5）——动态规划专题

动态规划的递归写法和递推写法

动态规划是一种精妙的思想，它没有固定的写法，使用非常灵活，常常需要具体问题具体分析。直接讨论动态规划的概念不是很好的学习方式，先接触一些经典模型，穿插动态规划概念的理解，会有更好的效果。

动态规划的概念

动态规划（Dynamic Programming, DP)是一种用来解决**最优化问题**的算法思想。

最优化问题的形式

max/min 目标函数F() st. 限制条件（等式、不等式、变量范围限制）

简单来说，动态规划将一个复杂问题分解成若干个子问题，通过综合子问题的最优解来得到原问题的最优解。（区别分治法：分治法也要综合其子问题的解，但不要求选择其中的最优解） 需要注意的是，动态规划会将每个求解的子问题的解记录下来，这样下次碰到同样的子问题时，就可以直接使用之前记录的结果，不必重复计算。虽然动态规划采用这种方式来提高计算效率，但不能说这种做法时动态规划的核心。

动态规划可以使用递归和递推的方式实现，其中递归写法又称作记忆化搜索。

动态规划的递归写法/记忆化搜索

重叠子问题TODO

动态规划的递推写法

最优子结构TODO

青蛙跳台阶2

普通跳台阶

一只青蛙可以一次跳 1 级台阶或者一次跳 2 级台阶，$例如$：

跳上第 1 级台阶只有一种跳法：直接跳 1 级即可。 跳上第 2 级台阶有两种跳法：每次跳 1 级，跳两次；或者一次跳 2 级。 问要跳上第 n 级台阶有多少种跳法？

很多人喜欢正向思考，使用暴力求解，但往往这是一个很复杂的问题。我们可以反过来思考：

如果我们要跳上第 n 级台阶，该怎么跳？此时问题就简单多了，答案是，要么从第 n−1 级台阶跳一级上来，要么从第 n−2 级台阶跳两级上来，除此，青蛙再也没有其他的方法可以跳上第 n 级台阶。

我们令 f(n)f(n) 表示从第一级台阶跳上第 nn 级台阶有几种跳法。则有如下递推公式：

f(n)=f(n−1)+f(n−2)

是不是很熟悉，它不就是斐波那契数列吗，（C语言）代码就很简单啦：

int jumpFloor(int number) {
    int g = 1, f = 2;
    while (number-- > 1) {
        f += g;
        g = f - g;
    }
    return g;
}
变态跳台阶

变态跳台阶问题是这样的：如果青蛙可以一次跳 1 级，也可以一次跳 2 级，一次跳 3 级，…，一次跳 n 级。问要跳上第 nn 级台阶有多少种跳法？

同样的，我们采用逆向思维，将问题改为：跳上第 n 级台阶该怎么跳？答案如下：

要跳上第 n级台阶，可以从第 n−1级台阶一次跳上来，也可以可以从第 n−2 级台阶一次跳上来，也可以可以从第 n−3级台阶一次跳上来，…，也可以可以从第 1级台阶一次跳上来。那么问题就很简单啦，同样的，令 f(n) 表示从第一级台阶跳上第 n级台阶有几种跳法。则有如下递推公式： f(n)=f(n−1)+f(n−2)+…+f(1)

同时，f(n−1)也可以表示如下： f(n−1)=f(n−2)+f(n−3)+…+f(1)

所以，由上面两个公式可知： f(n)=2f(n−1)=4f(n−2)=8f(n−3)=…

即： f(n)=2f(n−1)=2^2 f(n−2)=2^3 f(n−3)=…=2^(n−1) f(n−(n−1))=2^(n−1) f(1)

因为 f(1)=1f(1)=1，所以 f(n)=2^(n−1) f(n)=2^(n−1)。 C语言代码如下：

int square(int a) { return a * a; }
int power2(int n) { // 计算2的n次方
    if (0 == n) return 1;
    return n % 2 ? square(power2(n>>1))<<1 : square(power2(n>>1));
}

int jumpFloorII(int number) {
    return power2(number - 1);
}

装错信封问题（错排问题）

错排问题最早被尼古拉·伯努利和欧拉研究，因此历史上也称为伯努利-欧拉的装错信封的问题。这个问题有许多具体的版本，如在写信时将n封信装到n个不同的信封里，有多少种全部装错信封的情况？又比如四人各写一张贺年卡互相赠送，有多少种赠送方法？自己写的贺年卡不能送给自己，所以也是典型的错排问题。

错排问题，是组合数学中的问题之一。考虑一个有n个元素的排列，若一个排列中所有的元素都不在自己原来的位置上，那么这样的排列就称为原排列的一个错排。 n个元素的错排数记为D(n)。 研究一个排列错排个数的问题，叫做错排问题或称为更列问题。

当n个编号元素放在n个编号位置，元素编号与位置编号各不对应的方法数用D(n)表示，那么D(n-1)就表示n-1个编号元素放在n-1个编号位置，各不对应的方法数，其它类推.

第一步，把第n个元素放在一个位置，比如位置k，一共有n-1种方法；

第二步，放编号为k的元素，这时有两种情况：⑴把它放到位置n，那么，对于剩下的n-1个元素，由于第k个元素放到了位置n，剩下n-2个元素就有D(n-2)种方法；⑵第k个元素不把它放到位置n，这时，对于这n-1个元素，有D(n-1)种方法；

综上得到递推公式：

D(n) = (n-1) [D(n-2) + D(n-1)]

特殊地，D(1) = 0, D(2) = 1.

可推导其通项公式为D(n) = n! [(-1)^2/2! + … + (-1)^(n-1)/(n-1)! + (-1)^n/n!].此即错排公式

约瑟夫问题/选大王问题

约瑟夫问题

据说著名历史学家 Josephus有过以下的故事:在罗马人占领乔塔帕特后，39 个人与Josephus及他的朋友躲到一个洞中，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人，该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。

首先从一个人开始，越过k-2个人(因为第一个人已经被越过)，并杀掉第k个人。接着，再越过k-1个人，并杀掉第k个人。这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。

然而Josephus 和他的朋友并不想遵从。问题是，给定了人数总和，一开始要站在什么地方才能避免被处决?Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，成了最后剩下的2个人，于是逃过了这场死亡游戏。

选大王问题

链接：https://www.nowcoder.com/questionTerminal/84789c61e87f4290a544d5eb60226f05 来源：牛客网

  • 问题描述： 有n只猴子，按顺时针方向围成一圈选大王(编号从1到n)，从第1号开始报数，一直数到m，数到m的猴子退出圈外，剩下的猴子再接着从 1 开始报数。就这样，直到圈内只剩下一只猴子时，这个猴子就是猴王。现在告诉你 n 和 m，请帮忙求出哪一只猴子能当大王。
  • 输入描述: 输入包含多组数据。每组数据包含两个正整数 n 和m（1≤ m < n ≤ 10000）。
  • 输出描述: 对应每一组输入，输出猴王的编号 i（1≤i≤n）。
常规解法

构建一个列表，按照报数顺序依次 删除元素，直到只剩下一个元素

/**
 * 常规算法
 * 序列为 1,2，... ，n
 */
static int Josephus(int n,int m){
 
    List<Integer> monkeys=new ArrayList<>();
 
    for(int i=1;i<=n;i++){
        monkeys.add(i);
    }
 
    int pos=0;
 
    while(n>1){
        pos+=m-1;
        pos%=n;
        monkeys.remove(pos);
        n--;
    }
 
    return monkeys.get(0);
}
递归解法

假设 对于n,m 已知 k 是当前需要的人，当前序列为 0，1，… ，k-1, k , k+1, … , n-1 那么剩下的人分别为 0，1，… ，k-1, k+1, … , n-1 接下来需要从 k+1 处开始报数，不妨对 k 以前的数 +n, 即： n, n+1, … , n+k-1, k+1, … , n-1 按照报数顺序排列： k+1, … , n，n+1, … , n+k-1 这个序列可看出，仅比正常序列 0，1，… , n-2 多了 k+1

所以有： 假设 josephus(n,m)是序列 0，1，… , n-1循环报数最终剩下的人， 则 josephus(n-1,m)为序列 0，1，… , n-2循环报数最终剩下的人 josephus(n,m)= josephus(n-1,m)+k+1 考虑到运用上述公式时，是对 n,m序列 对k之前的数+n得到的， 因此应当修正为

josephus(n,m)=（ josephus(n-1,m)+k+1）%n

如此即可还原到原始序列。

又因为对于任意 n,m ,初始k值我们是可以求解得到的

k=(m%n)-1

所以

josephus(n,m)=（ josephus(n-1,m)+(m%n)）%n
josephus(n,m)=（ josephus(n-1,m)+m）%n

至此已形成递归 递归截至条件也显而易见

josephus(1,m)=0

注意 此解法针对的是 0, 1, 2, … , n-1的序列， 但约瑟夫环一般是从1 开始的，即 1, 2， … , n 所以我们利用 josephus(n,m)求出的结果要 +1才是最终结果。

public class Main {
    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
 
        while (scanner.hasNext()){
            //递归算法
            System.out.println( JosephusRecursive( scanner.nextInt(), scanner.nextInt() )+1 );
            //常规算法
            // System.out.println( Josephus( scanner.nextInt(), scanner.nextInt() ));
        }
    }
 
    /**
    * 递归算法
    * 序列为 0,1,2，... ，n-1
    */
    static int JosephusRecursive(int n,int m){
 
        if(n==1){
            return 0;
        }
        return (JosephusRecursive(n-1,m)+m)%n;
    }
 
}
递归衍生循环

由 递归法 可知

josephus(n,m)=（ josephus(n-1,m)+m）%n
josephus(1,m)=0

因此有

josephus(n+1,m)=（ josephus(n,m)+m）%（n+1）

将 josephus( ) 简记为 J( )

J ( n+1, m ) = ( J ( n, m ) + m ) % ( n+1)

由此可以将递归改成循环

 /**
 * 递归衍生循环
 */
static int JosephusCycle(int n,int m){
    int r=0;
    for(int i=2;i<=n;i++){
        r = (r+m)%i;
    }
    //由于该方法为递归思想推算过来的，上述算法执行完后的结果仍然为 针对序列 0， 1， ... , n-1推算的结果，
    // 因此最终结果需要 +1
    return r+1;
}

该方法虽然是从递推的结果进一步通过数算得来的，但是结论反而可以当作一个公式用，只是逻辑上讲没什么道理。

最长不下降子序列

参考：算法笔记-胡凡曾磊-提高篇（5）动态规划专题

最长不下降子序列（longest increasing sequence, LIS)问题：

在一个序列中，找到一个最长的子序列（可以不连续），使得这个子序列是不下降（非递减）的。

例如，给一个序列A = {1,2,3,-1,-2,7,9}, 它的最长不下降子序列是{1,2,3,7,9}，长度为5。当然它还有其他一些非降子序列，比如{1,2,3}, {-2,7,9}等，但都不是最长的。

枚举法：我们可以用最原始的方法来枚举每种情况。即每个元素有取和不取两种方式。然后判断是否为不下降子序列。 如果是不下降子序列，则更新最大长度。直达枚举完所有情况，得到最长不下降子序列长度。 对于n个元素，每个元素取/不取，有$2^n$种情况，算法复杂度为$O(2^n)$. 这显然是不能承受的。

实际上以上枚举包含了大量重复计算。下面先看动态规划解法。

动态规划法：令dp[i] 表示以A[i]结尾的最长不下降子序列长度。还是和枚举法一样，考虑每个元素取/不取。对A[i] 来说，就会有两种情况： 取A[i]: 如果A[i]大于等于之前的某个元素A[j], 且dp[i]<dp[j]+1,则需要更新dp[i] = dp[j]+1, 即将A[i]纳入当前最长子序列。($\forall j<i, dp[i] = max{dp[j]+1}$) 不取A[i]:如果A[i]小于之前的所有元素A[j]，或者dp[i]<dp[j]+1时，不更新dp[i],即不将A[i]纳入当前最长子序列。

得到动态规划的状态转移方程： $dp[i] = max{dp[j]+1, dp[i] }, \forall j<i $ 边界条件： $dp[i] = 1, \forall i$

举例： A[1:4] = {1,5,-1,3},假设已知道以A[1],A[2],A[3]的最长不下降子序列为{1},{1,5}, {-1},长度分别为1，2，1. 为求A[4]结尾的最长不下降子序列，考虑将A[4]接到A[1],A[2],A[3]的最长不下降子序列的后面，看看最长子序列能否变得更长。 A[4] : 喂，A[1],我可以站你后面，形成更长的LIS吗 A[1]: 我看看，你比我高，当然可以。这样我们组成的最长子序列就是{1,3}了 A[4]: 喂，A[2]，我可以站你后面，形成更长的LIS吗 A[2]: 你那么矮，还是算了。我这里本来就有2了，你就算来了也不增加LIS长度。 A[4]: 喂，A[3]，我可以站你后面，形成更长的LIS吗 A[3]: 我看看，你比我高，当然可以。这样我们组成的最长子序列就是{-1,3}了 还有一种情况，比如A[1:4] = {1,2,3,-4},则A[1],A[2],A[3]都嫌A[4]矮，A[4]只能孤零零一人形成以A[4]结尾的最长子序列{-4}。

//dp[i]表示以a[i]结尾的最长不下降子序列长度
int[] dp = new int[count];
//边界条件：dp[i] = 1;
//状态转移方程： dp[i] = max(dp[j]+1,dp[i]) , j = 0,1,,i-1,  当[j] <= a[i],
//              dp[i] = dp[i],                       当所有a[j]都 > a[i]
for (int i = 0; i < count; i++) {
    dp[i] = 1;
}
int max = 0;
for (int i = 1; i < count; i++) {
    for (int j = 0; j < i; j++) {
        if (a[j] <= a[i] && dp[j] + 1 > dp[i]) {
            dp[i] = dp[j] + 1;
        }
    }
    max = dp[i] > max ? dp[i] : max;
}
System.out.println(max);
例1

题目链接

背包问题

参考1(入门和掌握）：算法笔记-胡凡：提高篇（5）——动态规划专题 参考2（进阶：背包九讲）：https://www.cnblogs.com/jbelial/articles/2116074.html 参考（参考2的转载）：https://zhuanlan.zhihu.com/p/139368825 参考（参考2的迁移）：https://www.kancloud.cn/kancloud/pack/70125

01背包问题

01背包问题是这样的：有n件物品，每件物品的重量w[i],价值c[i]。现有一个背包，容量为V，问如何选择物品装入背包，使装入背包物品的总价值最大？

背包的初始化条件

不同的初始化条件决定了dp数组的意义： 是装入的总价值的最大值（不一定恰好装满） 还是装入的总价值（但一定装满）

具体的讲，初始化的问题（可用数学归纳法证明状态的转移过程：见bilibili大雪菜背包九讲专题）：

对于滚动数组/一维数组，$dp[0:m]$都初始化为0，则$dp[m]$中表示的内容，就是背包里装入物品总价值的最大值（背包不一定装满） 对于滚动数组/一维数组，$dp[1:m]$都初始化为$-INF$，$dp[0] = 0$, 则$dp[m$]中表示的内容，就是（恰好装满背包容量m时）背包里物品的总价值 对于二维数组，$dp[0:n][0:m]$都初始化为0，则$dp[n][m]$中表示的内容，就是背包里装入物品总价值的最大值（背包不一定装满） 对于二维数组，$dp[0:n][1:m]$都初始化为$-INF$，$dp[1:n][0] = 0$, 则$dp[n][m]$中表示的内容，就是（恰好装满背包容量m时）背包里物品的总价值

例1 用零钱凑一定的金额

给n张零钱，面值分别为v[i]，问如何选择零钱，凑成给定的金额V。如果有多种方法，使用面值尽量小的，张数多的方法。

原题链接

这道题目属于：背包问题-01背包问题-01满背包问题

从最优化问题的角度考虑，

可以看作是如下的最优化问题（方法1）：

限制条件： 变量i 属于[1,n], 面值v[i] 属于{v[1]:v[n]} 选择的面值之和必须恰好为给定的金额V 目标函数： 使用的零钱张数（最多）

也可以看作是如下的最优化问题（方法2）：

限制条件： 变量i 属于[1,n], 面值v[i] 属于{v[1]:v[n]} 选择的零钱总额小于等于给定的金额V 目标函数： 使用的零钱总额（最大）

如上面所示，可以写成两种最优化问题，那么就有各自对应的状态转移方程和递推方法。具体解法见PAT习题.md#动态规划#背包问题#例1.

完全背包问题

//TODO

数位DP

参考：牛客网讨论区：https://www.nowcoder.com/questionTerminal/eb1e0fc83a25461e93b8bf2039e871b9 参考：wust_wenhao的csdn博客 : https://blog.csdn.net/wust_zzwh/article/details/52100392 参考：oi-wiki数位dp： https://oi-wiki.org/dp/number/

数位 DP 问题往往都是这样的题型，给定一个闭区间 $[l,r]$，让你求这个区间中满足 某种条件 的数的总数。

首先我们将问题转化成更加简单的形式。设$ans_i$ 表示在区间 $[1,i]$中满足条件的数的数量，那么所求的答案就是$ans_r - ans_{l-1}$ 。

数位dp的实质就是换一种暴力枚举的方式，使得新的枚举方式满足dp的性质，然后记忆化就可以了。

枚举方法：从高位开始递归计数 + 记忆化搜索

但是枚举的过程中要注意枚举上界的问题。

对于一个小于n 的数，它从高到低肯定出现某一位，这一位之前的所有位都和 n上的位相等。而这一位上的数值小于 n这一位上对应的数值。 那么从高位开始枚举。这一位之前和这一位，每一位的枚举都是受限的。而这一位之后，每一位都可以枚举0-9.

数[1,N]中出现1的个数
方法1 动态规划DP法

数1-N中出现1的个数，即给定一个闭区间 $[1,N]$，让你求这个区间中 所有数里的1 的总数。

首先，我们可以从高位开始递归枚举所有的情况。然后通过记忆化存储，转化为递归型动态规划。

package com.jingmin.advanced2;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * 数位dp的实质就是换一种暴力枚举的方式，使得新的枚举方式满足dp的性质，然后记忆化就可以了。
 * 其枚举方式：控制上界枚举，从最高位开始往下枚举
 * 枚举上界：例如N=213，从百位开始枚举：百位可能的情况有0,1,2.然后每一位枚举都不能让枚举的这个数超过上界213（下界就是0或者1，这个次要），
 * 当百位枚举了1，那么十位枚举就是从0到9，因为百位1已经比上界2小了，后面数位枚举什么都不可能超过上界。
 * 所以问题就在于：当高位枚举刚好达到上界时，那么紧接着的一位枚举就有上界限制了。
 * 具体的这里如果百位枚举了2，那么十位的枚举情况就是0到1，如果前两位枚举了21，最后一位之是0到3
 * (这一点正好对于代码模板里的一个变量limit 专门用来判断枚举范围)。
 */
public class Advanced1038_2 {
    static int[] bit = new int[12];
    static int[][] dp = new int[12][12];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        br.close();
        System.out.println(solve(n));
    }

    private static int solve(int n) {
        int i = 0;
        while (n != 0) {
            bit[i++] = n % 10;
            n /= 10;
        }
//        return dfs(--i, 0, true);
        for (int k = 0; k < 12; k++) {
            for (int j = 0; j < 12; j++) {
                dp[k][j] = -1;
            }
        }
        return dfs1(--i, 0, true);
    }

    /**
     * 从高位开始递归计数1的出现次数
     *
     * @param pos       当前位 pos=0表示个位，pos=1表示十位，pos=2表示百位，依次类推
     * @param highState 从最高位到当前位已经累计1的个数（不包括当前位）
     * @param limit     当前位是否有枚举上界的标记。 如果高位枚举达到了上界，那么当前位枚举时也有限制。
     * @return
     */
    private static int dfs(int pos, int highState, boolean limit) {
        if (pos == -1) {
            return highState;
        }
        int count = 0;
        //当前位枚举上界
        int up = limit ? bit[pos] : 9;
        //从高位向低位递推枚举所有可能的情况（状态），综合所有的情况回归
        for (int i = 0; i <= up; i++) {
            count += dfs(pos - 1, i == 1 ? highState + 1 : highState, limit && i == up);
        }
        return count;
    }

    /**
     * 从高位开始递归计数1的出现次数(递归函数进行记忆化存储,转化为动态规划)
     *
     * @param pos       当前位 pos=0表示个位，pos=1表示十位，pos=2表示百位，依次类推
     * @param highState 从最高位到当前位已经累计1的个数（不包括当前位）
     * @param limit     当前位是否有枚举上界的标记。 如果高位枚举达到了上界，那么当前位枚举时也有限制。
     *                  dp[pos][highState] 保存从最高位开始到当前位pos（不包含当前位），已有1的个数
     */
    private static int dfs1(int pos, int highState, boolean limit) {
        //递归结束条件
        if (pos == -1) {
            return highState;
        }
        //使用记忆的值，!limit防止发生状态冲突
        if (!limit && dp[pos][highState] != -1) {
            return dp[pos][highState];
        }
        int count = 0;
        //当前位枚举上界
        int up = limit ? bit[pos] : 9;
        //从高位向低位递推枚举所有可能的情况（状态），综合所有的情况回归
        for (int i = 0; i <= up; i++) {
            count += dfs1(pos - 1, i == 1 ? highState + 1 : highState, limit && i == up);
        }
        return count;
    }
}
方法2 排列组合法

参考（牛客网讨论区 琉璃の璀璨 的讨论）：https://www.nowcoder.com/questionTerminal/eb1e0fc83a25461e93b8bf2039e871b9

package com.jingmin.advanced2;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * @author : wangjm
 * @date : 2020/6/23 21:17
 * @discription : https://www.nowcoder.com/pat/5/problem/4088
 * 数1-N之间出现1的个数
 * <p>
 * 方法： 排列组合的方法（求每一位的1的个数/通项公式法）
 * 参考（牛客网讨论区 琉璃の璀璨 的讨论）：https://www.nowcoder.com/questionTerminal/eb1e0fc83a25461e93b8bf2039e871b9
 * <p>
 * 1的总个数为1在1~n所有数中
 * 个位数上有1的个数+十位数上有1的个数+...+亿位数上有1的个数+...
 * 自己动手亲自找一遍规律就能得出答案：
 * 首先，找规律：
 * 13
 * 个位数为1：1 11
 * 十位数为1：10 11 12 13
 * 1的总个数为： 2+4=6
 * <p>
 * 23
 * 个位数为1：1  11 21
 * 十位数为1：10 11 12 13 14 15 16 17 18 19
 * 1的总个数为：3+10=13
 * <p>
 * 345
 * 个位数为1：1 11 21 31 41 51 61 71 81 91 101 111 121 131 141   ...341
 * 十位数为1：10 11 12 13 14 15 16 17 18 19  ...311 312 ...319
 * 百位数为1：100  101...199
 * 1的总个数为：100+40+35=175
 * <p>
 * 进而可得通项：
 * 通项：求某一位的1的个数
 * 高n位 * 本位权（比如百位就乘100）+  0                             （本位小于1）
 * 高n位 * 本位权                  +  1 * 本位权                    （本位大于1）
 * 高n位 * 本位权                  +  低n位 + 1                     （本位等于1）
 * 也就是说，某位（各位，十位...）1的总个数可能与其高位，低位以及自己的
 * 值有关，具体对应情况如上
 * <p>
 * 例如算12345：
 * 个位1：1234*1+1（个位>=1加1）
 * 十位1：123*10+10
 * 百位1：12*100+100
 * 千位1：1*1000+1000
 * 万位1：2345+1
 * 1的总个数为：8121
 * <p>
 * 例如算23012：
 * 个位1：2301*1+1
 * 十位1：230*10+2+1  （十位=1加低位即2然后加1）
 * 百位1：23*100            （百位为0加0）
 * 千位1：2*1000+1000
 * 万位1：10000
 * 1的总个数为：19905
 * <p>
 * 通俗来说，某位（个位，十位..）上1的个数=
 * 基础数+当前位为>1，<1，=1时的情况，
 * 而基础数为当前位前面的高位*当前位
 * （例如：23012，当 当前位为百位时，基础数=23（前高位）*100+上面讨论的情况）
 */
public class Advanced1038 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        br.close();
        int count = 0;
        //从个位开始
        int bit = n % 10;
        int base = 1;
        int high = n / (10 * base);
        int low = n % base;
        while (bit != 0 || high != 0) {
            if (bit > 1) {
                count += (high + 1) * base;
            } else if (bit == 1) {
                count += high * base + low + 1;
            } else {
                count += high * base;
            }
            bit = high % 10;
            high = high / 10;
            base *= 10;
            low = n % base;
        }
        System.out.println(count);
    }
}

排序

参考：https://www.cnblogs.com/onepixel/p/7674659.html

排序概览

排序分类

十种常见排序算法可以分为两大类：

  • 比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此也称为非线性时间比较类排序。
  • 非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。

img

算法复杂度

img

相关概念
  • 稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
  • 不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。
  • 时间复杂度：对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。
  • **空间复杂度：**是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。

比较类排序

通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此也称为非线性时间比较类排序。

插入排序

插入排序（英语：Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

包括：直接插入排序，二分插入排序（又称折半插入排序），链表插入排序。

平均来说插入排序算法的时间复杂度为O(n^2）。

属于稳定排序的一种（通俗地讲，就是两个相等的数不会交换位置） 。

就地排序: 在原输入数组上进行后移赋值操作，所需开辟的辅助空间跟输入数组规模无关，所以空间复杂度为：O(1)

直接插入排序

一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：

  1. 从第一个元素开始，该元素可以认为已经被排序
  2. 取出下一个元素，在已经排序的元素序列中从后向前扫描
  3. 如果该元素（已排序）大于新元素，将该元素移到下一位置
  4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
  5. 将新元素插入到该位置后
  6. 重复步骤2~5
	/**
     * 直接插入排序
     */
    public static <T extends Comparable> void directInsertSort(ArrayList<T> list) {
        int n = list.size();
        for (int i = 1; i < n; i++) {
            T tmp = list.get(i);
            int j = i - 1;
            for (; j >= 0 && tmp.compareTo(list.get(j)) < 0; j--) {
                list.set(j + 1, list.get(j));
            }
            list.set(j + 1, tmp);
        }
    }

如果目标是把n个元素的序列升序排列，那么采用插入排序存在最好情况和最坏情况。 最好情况就是，序列已经是升序排列了，在这种情况下，需要进行的比较操作需（n-1）次即可。 最坏情况就是，序列是降序排列，那么此时需要进行的比较共有n(n-1)/2次。 插入排序的赋值操作是比较操作的次数加上 (n-1）次。 平均来说插入排序算法的时间复杂度为O(n^2）。 因而，插入排序不适合对于数据量比较大的排序应用。

如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。

二分插入排序

（1）计算 0 ~ i-1 的中间点，用 i 索引处的元素与中间值进行比较，如果 i 索引处的元素大，说明要插入的这个元素应该在中间值和刚加入i索引之间，反之，就是在刚开始的位置 到中间值的位置，这样很简单的完成了折半；

（2）在相应的半个范围里面找插入的位置时，不断的用（1）步骤缩小范围，不停的折半，范围依次缩小为 1/2 1/4 1/8 …….快速的确定出第 i 个元素要插在什么地方；

（3）确定位置之后，将整个序列后移，并将元素插入到相应位置。

/**
 * 二分搜索插入排序
 */
public static <T extends Comparable> void binarySearchInsertSort(ArrayList<T> list) {
    int n = list.size();
    for (int i = 1; i < n; i++) {
        T tmp = list.get(i);
        int low = 0;
        int high = i - 1;
        int mid = -1;
        while (low <= high) {
            mid = low + (high - low) / 2;
            if (tmp.compareTo(list.get(mid)) < 0) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        for (int j = i - 1; j >= low; j--) {
            list.set(j + 1, list.get(j));
        }
        list.set(low, tmp);
    }
}

二分法查找的插入排序的算法复杂度

  1. 时间复杂度：O(n^2)

    二分查找插入位置，因为不是查找相等值，而是基于比较查插入合适的位置，所以必须查到最后一个元素才知道插入位置。 二分查找最坏时间复杂度：当2^X>=n时，查询结束，所以查询的次数就为x，而x等于log2n（以2为底，n的对数）。即O(log2n)。所以，二分查找排序比较次数为：x=log2n

    二分查找插入排序耗时的操作有：比较 + 后移赋值。时间复杂度如下：

    1. 最好情况：查找的位置是有序区的最后一位后面一位，则无须进行后移赋值操作，其比较次数为：log2n 。即O(log2n)
    2. 最坏情况：查找的位置是有序区的第一个位置，则需要的比较次数为：log2n，需要的赋值操作次数为n(n-1)/2加上 (n-1) 次。即O(n^2)
    3. 渐进时间复杂度（平均时间复杂度）：O(n^2)

  2. 空间复杂度：O(1)

    从实现原理可知，二分查找插入排序是在原输入数组上进行后移赋值操作的（称“就地排序”），所需开辟的辅助空间跟输入数组规模无关，所以空间复杂度为：O(1)

链接插入排序
/**
 * 链接插入排序
 */
public static <T extends Comparable> void linkedInsertSort(LinkedList<T> list) {
    int n = list.size();
    for (int i = 1; i < n; i++) {
        T tmp = list.get(i);
        int j = i - 1;
        for (; j >= 0 && tmp.compareTo(list.get(j)) < 0; j--) {
        }
        list.add(j + 1, list.remove(i));
    }
}
希尔排序

思想：分治策略

希尔排序是一种分组直接插入排序方法，其原理是：先将整个序列分割成若干小的子序列，再分别对子序列进行直接插入排序，使得原来序列成为基本有序。这样通过对较小的序列进行插入排序，然后对基本有序的数列进行插入排序，能够提高插入排序算法的效率。

具体如下（实现为升序）：

  1. 先取一个小于n的整数d1作为第一个增量，将所有距离为d1的倍数的记录放在同一个组中，把无序数组分割为若干个子序列。

  2. 在各子序列内进行直接插入排序。

  3. 然后取第二个增量d2<d1，重复步骤1~2，直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。

/**
 * 希尔排序
 */
public static <T extends Comparable> void shellSort(ArrayList<T> list) {
    int n = list.size() / 2;
    while (n >= 1) {
        //以n为间隔，对子list进行直接插入排序
        for (int i = 0; i < n; i++) {
            directInsertSort(list, i, n);
        }
        n = n / 2;
    }
}

/**
 * 直接插入排序(指定开始位置，和间隔）
 * <p>
 * 若startPos = 1, interval = 3, 则对list的1,4,7,...号元素排序
 * 若startPos = 0, interval = 1, 则为全list的直接插入排序
 *
 * @param list     待排序列表（为了提高效率，这里指定为ArrayList）
 * @param startPos 开始位置
 * @param interval 以interval为间隔
 * @param <T>      待排序元素类型
 */
public static <T extends Comparable> void directInsertSort(ArrayList<T> list, int startPos, int interval) {
    int n = list.size();
    for (int i = startPos + interval; i < n; i += interval) {
        T tmp = list.get(i);
        int j = i - interval;
        for (; j >= 0 && tmp.compareTo(list.get(j)) < 0; j -= interval) {
            list.set(j + interval, list.get(j));
        }
        list.set(j + interval, tmp);
    }
}

希尔排序是按照不同步长对元素进行插入排序，当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，速度很快；当元素基本有序了，步长很小，插入排序对于有序的序列效率很高。所以，希尔排序的时间复杂度会比o(n^2)好一些。

  1. 时间复杂度: O(nlog2n)3

    希尔排序耗时的操作有：比较 + 后移赋值。时间复杂度如下：

    1. 最好情况：序列是升序排列，在这种情况下，需要进行的比较操作需（n-1）次。后移赋值操作为0次。即O(n)

    2. 最坏情况：O(nlog2n)。(维基百科上最坏是O(n^2))

    3. 渐进时间复杂度（平均时间复杂度）：O(nlog2n)

    ​ 增量选取：希尔排序的时间复杂度与增量的选取有关，但是现今仍然没有人能找出希尔排序的精确下界。一般的选择原则是：取上一个增量的一半作为此次序列的划分增量。首次选择序列长度的一半为增量。（因此也叫缩小增量排序）

    ​ 平均时间复杂度：O(nlog2n)，希尔排序在最坏的情况下和平均情况下执行效率相差不是很多，与此同时快速排序（O(log2n)）在最坏的情况下执行的效率会非常差。专家们提倡，几乎任何排序工作在开始时都可以用希尔排序，若在实际使用中证明它不够快，再改成快速排序这样更高级的排序算法.

  2. 空间复杂度：O(1)

    从实现原理可知，希尔排序是在原输入数组上进行后移赋值操作的（称“就地排序”），所需开辟的辅助空间跟输入数组规模无关，所以空间复杂度为：O(1)

稳定性：希尔排序是不稳定的。因为在进行分组时，相同元素可能分到不同组中，改变相同元素的相对顺序。

优化改进：根据实际运行情况，我们也可以将希尔排序中查找插入位置部分的代码替换为二分查找方式。

归并排序

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。归并排序是一种稳定的排序方法。

归并操作(merge)，也叫归并算法，指的是将两个顺序序列合并成一个顺序序列的方法。 如　设有数列{6，202，100，301，38，8，1} 初始状态：6,202,100,301,38,8,1 第一次归并后：{6,202},{100,301},{8,38},{1}，比较次数：3； 第二次归并后：{6,100,202,301}，{1,8,38}，比较次数：4； 第三次归并后：{1,6,8,38,100,202,301},比较次数：4； 总的比较次数为：3+4+4=11； 逆序数为14；

归并排序的过程如下： 第一步：申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列 第二步：设定两个指针，最初位置分别为两个已经排序序列的起始位置 第三步：比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置 重复步骤3直到某一指针超出序列尾 将另一序列剩下的所有元素直接复制到合并序列尾

递归代码：

public static int[] mergeSort(int[] nums, int l, int h) {
    if (l == h)
      return new int[] { nums[l] };
    
    int mid = l + (h - l) / 2;
    int[] leftArr = mergeSort(nums, l, mid); //左有序数组
    int[] rightArr = mergeSort(nums, mid + 1, h); //右有序数组
    int[] newNum = new int[leftArr.length + rightArr.length]; //新有序数组
    
    int m = 0, i = 0, j = 0; 
    while (i < leftArr.length && j < rightArr.length) {
      newNum[m++] = leftArr[i] < rightArr[j] ? leftArr[i++] : rightArr[j++];
    }
    while (i < leftArr.length)
      newNum[m++] = leftArr[i++];
    while (j < rightArr.length)
      newNum[m++] = rightArr[j++];
    return newNum;
  }

非递归代码：

/**
 * 归并排序
 */
public static <T extends Comparable> ArrayList<T> mergeSort(ArrayList<T> list) {
    if (list.size() < 2) {
        return list;
    }
    //总list长度
    int listLen = list.size();
    //子list长度
    int subLen = 2;
    ArrayList<T> newList = null;
    while (subLen < listLen) {
        newList = new ArrayList<>(8);
        int i = 2 * subLen;
        while (i < listLen) {
            newList.addAll(merge(list.subList(i - 2 * subLen, i - subLen), list.subList(i - subLen, i)));
            i = i + 2 * subLen;
        }
        if (listLen > (i - subLen)) {
            newList.addAll(merge(list.subList(i - 2 * subLen, i - subLen), list.subList(i - subLen, listLen)));
        } else {
            newList.addAll(list.subList(i - 2 * subLen, listLen));
        }
        subLen = subLen * 2;
        list = newList;
    }
    return newList;
}

/**
 * 两路归并操作：将两个list合为一个list
 */
private static <T extends Comparable> ArrayList<T> merge(List<T> list1, List<T> list2) {
    ArrayList<T> list = new ArrayList<>(16);
    int i = 0, j = 0;
    T tmp1 = null, tmp2 = null;
    while (i < list1.size() && j < list2.size()) {
        tmp1 = list1.get(i);
        tmp2 = list2.get(j);
        if (tmp1.compareTo(tmp2) <= 0) {
            list.add(tmp1);
            i++;
        } else {
            list.add(tmp2);
            j++;
        }
    }
    if (i != list1.size()) {
        list.addAll(list1.subList(i, list1.size()));
    }
    if (j != list2.size()) {
        list.addAll(list2.subList(j, list2.size()));
    }
    return list;
}

归并排序是稳定的排序.即相等的元素的顺序不会改变.

交换排序

冒泡排序

img

快速排序

参考：八大排序-快速排序（搞定面试之手写快排）

参考：百度百科-快速排序算法

原理

快速排序的核心思想是分治：选择数组中某个数作为基数，通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数都比基数小，另外一部分的所有数都都比基数大，然后再按此方法对这两部分数据分别进行快速排序，循环递归，最终使整个数组变成有序。

基数选择

由于快速排序需要选定一个基数进行划分排序，关于基数选择有很多方式，而基数选择直接关系到快排的效率。事实上，选取基准元素应该遵循平衡子问题的原则：即使得划分后的两个子序列的长度尽量相同本篇以待排序数组首元素作为基数进行说明。本篇以最常见的使用数组首元素作为基数进行快速排序原理说明。

一趟排序

以数组int n[] = { 6, 5, 2, 7, 3, 9, 8, 4, 10, 1 }为例：

img

以第一个数字6作为基数，使用双指针i,j进行双向遍历：

  • 1、i从左往右寻找第一位大于基数（6）的数字，j从右往左寻找第一位小于基数（6）的数字；
  • 2、找到后将两个数字进行交换。继续循环交换直到i>=j结束循环；
  • 3、最终指针i=j,此时交换基数和i(j)指向的数字即可将数组划分为小于基数（6）/基数（6）/大于基数（6）的三部分，即完成一趟快排；
伪代码

见编码注释

编码实践
public class Test {

	public static void main(String[] args) {
		int n[] = { 6, 5, 2, 7, 3, 9, 8, 4, 10, 1 };
		quicksort(n);
		System.out.print("快排结果：");
		for (int m : n) {
			System.out.print(m + " ");
		}
	}

	public static void quicksort(int n[]) {
		sort(n, 0, n.length - 1);
	}

	public static void sort(int n[], int l, int r) {
		if (l < r) {
			// 一趟快排，并返回交换后基数的下标
			int index = patition(n, l, r);
			// 递归排序基数左边的数组
			sort(n, l, index - 1);
			// 递归排序基数右边的数组
			sort(n, index + 1, r);
		}

	}

	public static int patition(int n[], int l, int r) {
		// p为基数，即待排序数组的第一个数
		int p = n[l];
		int i = l;
		int j = r;
		while (i < j) {
			// 从右往左找第一个小于基数的数
			while (n[j] >= p && i < j) {
				j--;
			}
			// 从左往右找第一个大于基数的数
			while (n[i] <= p && i < j) {
				i++;
			}
			// 找到后交换两个数
			swap(n, i, j);
		}
		// 使划分好的数分布在基数两侧
		swap(n, l, i);
		return i;
	}

	private static void swap(int n[], int i, int j) {
		int temp = n[i];
		n[i] = n[j];
		n[j] = temp;
	}

}
复制代码
  • 结果
快排结果：1 2 3 4 5 6 7 8 9 10 
复制代码

选择排序

简单选择排序

选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

堆排序

参考：堆排序

堆是一种特殊的树,它每个结点都有一个值，堆的特点是根结点的值最小（或最大），且根结点的两个子树也是一个堆。就类似一堆东西一样，按照由大到小（或由小到大）“堆”起来。

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：

  1. 大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；
  2. 小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；

堆排序的平均时间复杂度为 Ο(nlogn)。

算法步骤
  1. 创建一个堆 H[0……n-1]；
  2. 把堆首（最大值）和堆尾互换；
  3. 把堆的尺寸缩小 1，并调用 shift_down(0)，目的是把新的数组顶端数据调整到相应位置；
  4. 重复步骤 2，直到堆的尺寸为 1。
堆排序动图示例

img

堆排序分步示例

参考：数据结构示例——堆排序过程

参考：数据结构例程——选择排序之堆排序

参考：算法从入门到“放弃”（10）- 堆排序

本文实例引用自数据结构示例——堆排序过程。

假设我们要对目标数组A {57, 40, 38, 11, 13, 34, 48, 75, 6, 19, 9, 7}进行堆排序。

首先第一步和第二步，创建堆，这里我们用最大堆；创建过程中，保证调整堆的特性。从最后一个分支的节点开始进行调整为最大堆。

img从右往左，从下至上

现在得到的最大堆的存储结构如下：

img初始堆创建完成

接着，最后一步，堆排序，进行（n-1）次循环。

img持续整个过程直至最后一个元素为止

这个迭代持续直至最后一个元素即完成堆排序步骤。

参考代码
//来源：https://blog.csdn.net/sxhelijian/article/details/50118439
#include <stdio.h>
#define MaxSize 20
typedef int KeyType;    //定义关键字类型
typedef char InfoType[10];
typedef struct          //记录类型
{
    KeyType key;        //关键字项
    InfoType data;      //其他数据项,类型为InfoType
} RecType;              //排序的记录类型定义

//调整堆
void sift(RecType R[],int low,int high)
{
    int i=low,j=2*i;                        //R[j]是R[i]的左孩子
    RecType temp=R[i];
    while (j<=high)
    {
        if (j<high && R[j].key<R[j+1].key)  //若右孩子较大,把j指向右孩子
            j++;                                //变为2i+1
        if (temp.key<R[j].key)
        {
            R[i]=R[j];                          //将R[j]调整到双亲结点位置上
            i=j;                                //修改i和j值,以便继续向下筛选
            j=2*i;
        }
        else break;                             //筛选结束
    }
    R[i]=temp;                                  //被筛选结点的值放入最终位置
}

//堆排序
void HeapSort(RecType R[],int n)
{
    int i;
    RecType temp;
    for (i=n/2; i>=1; i--) //循环建立初始堆
        sift(R,i,n);
    for (i=n; i>=2; i--) //进行n-1次循环,完成推排序
    {
        temp=R[1];       //将第一个元素同当前区间内R[1]对换
        R[1]=R[i];
        R[i]=temp;
        sift(R,1,i-1);   //筛选R[1]结点,得到i-1个结点的堆
    }
}

int main()
{
    int i,n=10;
    RecType R[MaxSize];
    KeyType a[]= {0,6,8,7,9,0,1,3,2,4,5};//a[0]空闲，不作为关键字
    for (i=1; i<=n; i++)
        R[i].key=a[i];
    printf("排序前:");
    for (i=1; i<=n; i++)
        printf("%d ",R[i].key);
    printf("\n");
    HeapSort(R,n);
    printf("排序后:");
    for (i=1; i<=n; i++)
        printf("%d ",R[i].key);
    printf("\n");
    return 0;
}

非比较类排序

不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。

非比较类排序有较大限制，一般要求待排序数为整数，且范围固定。

计数排序

参考：https://www.cnblogs.com/onepixel/p/7674659.html

比如输入数字限定为[0,MAX]，用一个数组记录各个数出现的次数。

桶排序

参考：https://www.cnblogs.com/onepixel/p/7674659.html

桶排序算是计数排序的升级版。比如输入数字限定为[0,MAX]，将[0,MAX]分成多个区段，称为桶。将待排数字放入对应的桶中。各桶内排好序后，按桶的顺序输出。

基数排序

参考：https://www.cnblogs.com/onepixel/p/7674659.html

img

  1. A* 算法详解的原文：https://www.gamedev.net/reference/articles/article2003.asp，译文：https://blog.csdn.net/hitwhylz/article/details/23089415 ↩︎

  2. 该段为CSDN博主「Artprog」的原创文章，遵循 CC 4.0 BY-SA 版权协议,原文链接：https://blog.csdn.net/Artprog/article/details/67049383 ↩︎

  3. [ ↩︎