数据结构与算法_c++有 n 只食肉斯特,他们居住的地方构成了一棵树

数据结构

物理结构

逻辑结构

时间与空间复杂度

一个算法的优劣主要从算法的执行时间和所需要占用的存储空间两个方面衡量。

时间复杂度

时间复杂度=算法中语句的执行次数

//时间复杂度为O（1）常数阶
for (int i = 0; i <= 常数; i++) {
    x = x+1;
}

//时间复杂度为O（log2^n）对数阶
for (int i = 0; i <= N; i++) {
    for (int j = 0; j <= N; j++) {
        x = x+1;
    }
}

//时间复杂度为O（n）线性阶
for (int i = 0; i <= n; i++) {
    x = x+1;
}

//时间复杂度为O（n*log2^n）线性对数阶
  for (int i = 0; i <= N; i++) {
    for (int j = 0; j <= N; j++) {
        x = x+1;
    }
}

//时间复杂度为O（n^2）平方阶
  for (int i = 0; i <= N; i++) {
    for (int j = 0; j <= N; j++) {
        x = x+1;
    }
}


//时间复杂度为O（2^n）指数阶
  for (int i = 0; i <= N; i++) {
    for (int j = 0; j <= N; j++) {
        x = x+1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

空间复杂度

空间复杂度=程序从开始到结束所需要的存储空间

数据结构

数组Array

内存地址连续存储。

Arrays

package com.liu.utils;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.stream.Stream;

/**
 * @author liubo
 */
public class ArraysUtils {

    private static int[] arr = new int[6];
    private static String[] strArray = {"2", "5", "0", "4", "6", "-10"};
    private static int[] oneDimensional = {2, 5, 0, 4, 6, -10};
    private static int[][] twoDimensional = {{2, 5}, {0, 4}, {6, -10}};

    public static void main(String[] args) {
        System.out.println("--------------------数组覆写值--------------------");
        Arrays.fill(arr, 1);
        System.out.println(Arrays.toString(arr));

        arr = new int[6];
        Arrays.fill(arr, 0, arr.length, 2);
        System.out.println(Arrays.toString(arr));

        System.out.println("--------------------数组复制--------------------");
        System.out.println("1)System.arraycopy()。效率最高");
        int[] arraycopy = new int[6];
        System.arraycopy(oneDimensional, 0, arraycopy, 0, arr.length);
        System.out.println(Arrays.toString(arraycopy));


        System.out.println("2)clone()");
        int[] clone = oneDimensional.clone();
        System.out.println(Arrays.toString(clone));

        System.out.println("3)Arrays.copyof()");
        int[] copyOf = Arrays.copyOf(oneDimensional, oneDimensional.length);
        System.out.println(Arrays.toString(copyOf));

        System.out.println("4)Arrays.copyofRange()");
        int[] copyOfRange = Arrays.copyOfRange(oneDimensional, 0, oneDimensional.length);
        System.out.println(Arrays.toString(copyOfRange));

        System.out.println("--------------------数组排序--------------------");
        System.out.println(Arrays.toString(oneDimensional));
        Arrays.sort(oneDimensional);
        System.out.println(Arrays.toString(oneDimensional));

        System.out.println("--------------------数组查询--------------------");
        System.out.println("数组必须先进行sort排序；查询key的下标，没有则为-1");
        Arrays.sort(oneDimensional);
        int index = Arrays.binarySearch(oneDimensional, 5);
        System.out.println(oneDimensional[index]);


        System.out.println("--------------------数组类型转化--------------------");
        int[] strToInt1 = Arrays.stream(strArray).mapToInt(Integer::parseInt).toArray();
        int[] strToInt2 = Stream.of(strArray).mapToInt(Integer::parseInt).toArray();
        System.out.println(Arrays.toString(strToInt1));
        System.out.println(Arrays.toString(strToInt2));

        System.out.println("--------------------二纬数组字符串格式--------------------");
        System.out.println(Arrays.deepToString(twoDimensional));
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

sort排序原理

Arrays类重载很多个sort方法,这些sort方法可以分为两类：

对基本类型的排序（int、long、short、char、byte、float、double）
对非基本类型的排序（Object、T）

对基本类型的排序是通过调用对应的 DualPivotQuicksort.sort() 函数完成的。

对非基本类型的排序采用的是 TimSort 或者归并排序，在 JDK 1.7 之前，默认采用归并排序，JDK 1.7 及之后，默认采用 TimSort，但可以通过设置 JVM 参数 -Djava.util.Arrays.useLegacyMergeSort=true 继续使用归并排序。

DualPivotQuicksort双轴快排

TimSort归并算法简化版

归并排序的思想：通过不断合并两个有序子数组，完成整个数组的排序。

为了得到两个有序子数组，我们先将整个数组不断一分为二，拆分至每个子数组只剩下一个元素时，我们就认为这个子数组是有序的。

TimSort 优化了归并排序拆分出子数组的过程。

TimSort 的主要思想是：通过遍历数组，将数组拆分成若干个单调递增的子数组。每一块称为一个 run。拆分完成后，再将 run 两两合并起来。在遍历数组时，如果遇到单调递减的小块，TimSort 会将其翻转使其单调递增。为了提升合并 run 小块时的效率，在拆分时，并不是简单的将数组划分为单调递增的小块，而是设定了一些拆分规则，使得每一个 run 小块的长度都比较接近，不至于相差太大导致合并时需要拷贝大量的「尾巴」。

对于数组 [1,4,2,3]，TimSort 会将其拆分为两个 run: [1,4]、[2,3]
对于数组 [3,4,5,1]，TimSort 会将其拆分为两个 run: [3,4,5]、[1]
对于数组 [3,2,1,4,5]，TimSort 会将其拆分为两个 run: [1,2,3]、[4,5]，其中第一个 run 是由 [3,2,1] 翻转而来。

而现实世界中的数据往往总是部分有序的。比如：

一个年级的多个班统计成绩，每个班的成绩已经排好序，最后需要将每个班的成绩表综合起来排出全年级排名。
商场统计产品销量时，每家商店的产品销量已经排好序，需要将所有商店的产品销量综合起来找出畅销商品总排行。

TimSort 非常适合处理这类场景，因为整个数组可以拆分成少量的 run 小块，将其合并即可完成排序。

只能被拆分成少量 run 小块的数组称为highly structured「高度结构化」。

这里的 TimSort 只是将数组划分为单调递增的小块就开始合并了，相当于 TimSort 的简化版。

在拆分 run 小块的过程中，有两个条件会停止调用 TimSort，改为调用 sort(int[] a, int left, int right, boolean leftmost) 函数进行排序

经典题目

搜索

二分查找

双索引技巧 - 对撞指针

双索引技巧 - 滑动窗口 时间复杂度O(n)

排序

集合

java是面向对象的语言，集合能方便的存储与操作对象。

Collection单值

集合与数组的区别

注：

1）Collection与Collections的区别

Collection是集合的顶级接口。

Collections是集合类的一个工具类，用于对集合中元素进行排序、搜索以及线程安全等各种操作。reverse()反转，emptylist()清除

List列表

注：

1）ArrayList的插入，删除操作也不一定比LinkedList慢，如果在List靠近末尾的地方插入，那么ArrayList只需要移动较少的数据，而LinkedList则需要一直查找到列表尾部，反而耗费较多时间，这时ArrayList就比LinkedList要快。

2）有序的原理：使用Collections.sort()进行排序。

3）List 的 contains 方法普遍时间复杂度是 O(n) ，如果在代码中需要频繁调用 contains 方法查找数据，可以先将 list 转换成 HashSet 实现，将 O(n) 的时间复杂度降为 O(1) 。

ArrayList

LinkedList链表

Vector

Stack栈

先进后出

栈顶：

push入栈（返回插入元素的类型，push方法,最后还是调用了add方法。），add入栈（返回布尔类型）

pop出栈，peek获取不移除

栈Stack：对象存放的地方

堆Heap：值存放的地方

String str = new String(“字符串”);

String str1 = “字符串1”;

str与str1 在栈中

字符串 在堆中

字符串1 在堆中的常量池。

String s1 = "abc";
String s2 ="abc";
String s3 = new String("abc");
String s4 = new String("abc");
System.out.println(s1 == s2);
//true，均指向常量池中对象。
System.out.println(s3 == s4);
//false，两个引用指向堆中的不同对象。
System.out.println(s1 == s3);
//s1在栈，s3指向堆
System.out.println(s3 == s4.intern());
System.out.println(s3 == s1.intern());
System.out.println(s1 == s3.intern());
//false，false，true。

System.out.println("-----------------");

String st1 = "abc";
String st2 = "a";
String st3 = "bc";
String st4 = st2 + st3;
final String st5 = "a";
final String st6 = "bc";
String st7 = st5 + st6;
System.out.println(st1 == st4);
//false，因为s2+s3实际上是使用StringBuilder.append来完成，会生成不同的对象。
System.out.println(st1 == st7);
//true，因为final变量在编译后会直接替换成对应的值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

Set集

不可重复实现原理：

1）实现Comparable接口中的compareTo()方法

2）实现Comparator接口中的compare()方法

HashSet

存放元素的原理:

1.计算需要存放对象的hash值。

2.hash值经过计算获取元素在散列中应该存放的位置。

若位置上无元素，直接存放。

若位置上存在元素，使用未被重写的equals()方法进行比较。

若相等，则不存入(HashSet不允许存在重复值的原因)

若不相等，则形成单向链表结构，存入已存在元素的下一个节点。

3.HashSet存放的元素是无序，指的是元素在存放进入散列时，不是根据存入的先后顺序存放的，而是根据计算的HashCode值存入的，一旦存入元素，顺序将被固定。

LinkedHashSet

TreeSet

1.TreeSet中大部分方法是基于TreeMap实现的。

2.TreeSet中的对象都需要参与排序。

若须存入自定义的类，那么自定义的类必须实现Comparable接口中的compareTo()方法(或者实现Comparator接口中的compare()方法)，并指定对象的对比方案（所有属性都需要对比）。

str1.compareTo(str2);按字典大小返回结果，str1>str2返回正，str1=str2返回0，str1<str2返回负。

3.去掉重复元素

覆写hashCode();唯一的hash值是否相等。

覆写equals();具体指进行匹配。

SortedSet

单值排序

Queue队列

https://www.cnblogs.com/shangxiaofei/p/10617104.html

https://benjaminwhx.com/2018/05/05/%E8%AF%B4%E8%AF%B4%E9%98%9F%E5%88%97Queue/

先进先出

队头：poll获取并移除，peek获取不移除

队尾：offer插入（队列已满插入失败返回false)，add插入（队列已满插入失败抛出IllegalStateException异常)

offer()方法,最后还是调用了add方法,只是最后返回值不一样，add返回布尔类型 而push则返回插入元素的类型。

Deque双端队列

一种具有队列与栈性质的数据结构。

双端队列中的元素可以从两端弹出，插入和删除操作限定在队列的两边进行。

BlockingQueue阻塞队列

SynchronousQueue 公平模式

LinkedBlockingQueue 无界阻塞

LinkedTransferQueue 无界阻塞

AbstractQueue并发队列

PriorityvQueue优先队列

先进先出的基础上赋予优先级。使用二叉堆实现。

优先队列的元素按照其自然顺序进行排序，或者构造队列时提供Comparator进行排序。

ConcurrentLinkedQueue

Map键值对

HashMap哈希表\散列表

HashMap实现原理

HashMap结合了两者的优点，本质上是采用空间换时间的方式，提高了读写的效率。

HashMap的主干是一个数组，jdk1.7时是Entry数组，jdk1.8后是Node数组，每个数组映射一个链表，存储key-value值。它是通过key的hashCode来计算hash值，不同的hash值就映射数组下标，当hash值相同即产生hash冲突时，就采用链表(或者红黑树)解决哈希冲突。

HashMap是线程不安全的，线程安全的采用ConcurrentHashMap。

HashMap的整体结构如下：

如果定位到的数组位置不含链表（当前entry的next指向null）,那么对于查找，添加等操作很快，仅需一次寻址即可；如果定位到的数组包含链表：

对于添加操作，其时间复杂度为O(n)，首先遍历链表，存在即覆盖，否则新增；

对于查找操作来讲，仍需遍历链表，然后通过key对象的equals方法逐一比对查找。所以，性能考虑，HashMap中的链表出现越少，性能才会越好。

JDK1.7

JDK1.8

Entry

Entry是HashMap中的一个静态内部类。代码如下

	static class Entry<K, V> implements Map.Entry<K, V> {
        // map中key值，可以为null。
		final K key;
        // map中的value值，可以为null。
		V value;
		// 存储指向下一个Entry的引用，单链表结构
		Entry<K, V> next;
		// 对key的hashcode值进行hash运算后得到的值，存储在Entry，避免重复计算
		int hash;

		/**
		 * 构造函数
		 */
		Entry(int h, K k, V v, Entry<K, V> n) {
			value = v;
			next = n;
			key = k;
			hash = h;
		}
        
        // key值重写equals方法
        public final boolean equals(Object o) {
            if (!(o instanceof Map.Entry))
                return false;
            Map.Entry e = (Map.Entry)o;
            Object k1 = getKey();
            Object k2 = e.getKey();
            if (k1 == k2 || (k1 != null && k1.equals(k2))) {
                Object v1 = getValue();
                Object v2 = e.getValue();
                if (v1 == v2 || (v1 != null && v1.equals(v2)))
                    return true;
            }
            return false;
        }
       
        // 重写hashCode值
        public final int hashCode() {
            return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue());
        }
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

HashMap源码

public class HashMap<K, V> extends AbstractMap<K, V> implements Map<K, V>, Cloneable, Serializable {

	/**
	 * hashMap默认初始容量(16) 1<<4就是1乘以2的4次幂=16
	 */
	static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

	/**
	 * hashMap默认最大容量（2的30次幂）
	 */
	static final int MAXIMUM_CAPACITY = 1 << 30;

	/**
	 * 默认负载因子值0.75
	 */
	static final float DEFAULT_LOAD_FACTOR = 0.75f;

	/**
	 * threshold最大值 Integer.MAX_VALUE
	 */
	static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;

	/**
	 * Node数组，数组长度总是2的幂次倍
	 */
	transient Node<K, V>[] table;

	/**
	 * 实际存储的key-value键值对的个数，注意这个不等于数组的长度。
	 */
	transient int size;

	/**
	 * 阈值。 hashmap的实际元素数量。当实际数量(容量*填充因子)超过临界值时，就调用resize方法进行扩容，也会对链表中的元素进行rehash。
	 */
	int threshold;

	/**
	 * 负载因子。
	 */
	final float loadFactor;

	/**
	 * 每次扩容和更改map结构的计数器。
	 * 非线程安全。,如果期间因为其他线程的参与，导致HashMap的结构发生变化了（比如put，remove等操作），需要抛出异常ConcurrentModificationException
	 */
	transient int modCount;

	/**
	 * JDK 1.8 新增
	 */
	// 如果数组中某一个链表 >= 8 需要转化为红黑树
	static final int TREEIFY_THRESHOLD = 8;
	// 如果数组中某一个链表转化为红黑树后的节点 < 6 的时候 继续转为 链表
	static final int UNTREEIFY_THRESHOLD = 6;
	// 如果当链表元素 >= 8 并且数组 > 64 的时候转化红黑树
	static final int MIN_TREEIFY_CAPACITY = 64;

	/**
	 * HashMap构造器。
	 * HashMap根据initialCapacity和loadFactor的组合，共有4个构造器。如果没有某个参数会使用默认值，initialCapacity默认为16，loadFactory默认为0.75
	 * 
	 * @param initialCapacity
	 * @param loadFactor
	 */
	public HashMap(int initialCapacity, float loadFactor) {
		// 初始容量不能小于0
		if (initialCapacity < 0)
			throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);

		// 初始容量不能大于最大值，否则为最大值MAXIMUM_CAPACITY = 1<<30
		if (initialCapacity > MAXIMUM_CAPACITY)
			initialCapacity = MAXIMUM_CAPACITY;

		// 填充因子不能小于或等于0，不能为非数字
		if (loadFactor <= 0 || Float.isNaN(loadFactor))
			throw new IllegalArgumentException("Illegal load factor: " + loadFactor);

		// 初始化负载因子
		this.loadFactor = loadFactor;

		// 初始化threshold大小
		this.threshold = initialCapacity;
	}

	/**
	 * HashMap存储
	 */
	public V put(K key, V value) {
		// 允许存放null的key和null的value，当其key为null时，调用putForNullKey方法，放入到table[0]的这个位置
		if (key == null)
			return putForNullKey(value);

		// 对key的hashcode进一步计算，确保散列均匀
		int hash = hash(key);

		// 根据上一步骤中求出的hash得到在数组中的索引
		int i = indexFor(hash, table.length);

		// 如果索引i处的Node不为null，则执行遍历每个元素。新value放在链头，旧value放在链尾。
		for (Node<K, V> e = table[i]; e != null; e = e.next) {
			Object k;
			if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
				V oldValue = e.value;
				e.value = value;
				e.recordAccess(this);
				return oldValue;
			}
		}
		// 记录hashmap中修改结构的次数。保证并发访问时，若HashMap内部结构发生变化，快速抛出异常。
		modCount++;
		// 新增一个Node,将key、value添加到i索引处。
		addNode(hash, key, value, i);
		return null;
	}

	/**
	 * 检查容量是否达到阈值threshold
	 * 
	 * @param hash
	 * @param key
	 * @param value
	 * @param bucketIndex
	 */
	void addNode(int hash, K key, V value, int bucketIndex) {
		if ((size >= threshold) && (null != table[bucketIndex])) {
			resize(2 * table.length);
			hash = (null != key) ? hash(key) : 0;
			bucketIndex = indexFor(hash, table.length);
		}
		createNode(hash, key, value, bucketIndex);
	}

	/**
	 * HashMap读取
	 */
	public V get(Object key) {
		if (key == null)
			return getForNullKey();

		Node<K, V> Node = getNode(key);

		return null == Node ? null : Node.getValue();
	}

	final Node<K, V> getNode(Object key) {
		int hash = (key == null) ? 0 : hash(key);
		for (Node<K, V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) {
			Object k;
			if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
				return e;
		}
		return null;
	}

	/**
	 * hash算法
	 * 
	 * @param key
	 * @return
	 */
	static final int hash(Object key) {
		int h;
		return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
	}

	/**
	 * HashMap的容量
	 */
	static int indexFor(int h, int length) {
		return h & (length - 1);
	}

	/**
	 * hashmap扩容
	 * 
	 * @param newCapacity
	 */
	final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table;
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        int oldThr = threshold;
        int newCap, newThr = 0;
        // 步骤1：旧数组不为空
        if (oldCap > 0) {
            // 步骤1.1：如果旧数组长度大于等于最大容量，重新设置临界值
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            // 步骤1.2：如果旧数组容量大于默认容量且右移一位小于最大容量，双倍扩容
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; 
        }
        // 步骤2.如果旧数组为空，临界值大于0，设置新数组容量为临界值
        else if (oldThr > 0)
            newCap = oldThr;
        // 步骤3.如果旧数组为空，临界值小于等于0，设置容量与临界值为默认值
        else {
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        // 步骤4：如果新数组临界值为0，设置临界值
        if (newThr == 0) {
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        threshold = newThr;
        @SuppressWarnings({"rawtypes","unchecked"})
        // 步骤5：创建新数组
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;
        // 步骤6：如果旧数组不为空，遍历旧数组将结点平移至新数组
        if (oldTab != null) {
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
                    // 步骤6.1：如果oldTab[index]只有一个Node结点，重新计算index，将该结点注入新数组
                    if (e.next == null)
                        newTab[e.hash & (newCap - 1)] = e;
                    // 步骤6.2：如果oldTab[index]是树
                    else if (e instanceof TreeNode)
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    // 步骤6.3：如果oldTab[index]为链表，按照高低位平移链表至新数组
                    else {
                        Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        do {
                            next = e.next;
                            // 步骤6.3.1：如果为低位，将链表按顺序平移到以loHead为头，loTail为尾的链表中
                            if ((e.hash & oldCap) == 0) {
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            // 步骤6.3.2：如果为高位，将链表按顺序平移到以hiHead为头，loTail为尾的链表中
                            else {
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        // 步骤6.3.4：将loHead赋值给新数组
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        // 步骤6.3.5：将hihead赋值给新数组
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }
	
	/**
	 * 移动元素：遍历原来table中每个位置的链表，并对每个元素进行重新hash，在新的newTable找到归宿，并插入。
	 * 
	 * @param newTable
	 * @param rehash
	 */
	void transfer(Node[] newTable, boolean rehash) {
		int newCapacity = newTable.length;
		for (Node<K, V> e : table) {
			while (null != e) {
				Node<K, V> next = e.next;
				if (rehash) {
					e.hash = null == e.key ? 0 : hash(e.key);
				}
				int i = indexFor(e.hash, newCapacity);
				e.next = newTable[i];
				newTable[i] = e;
				e = next;
			}
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289

ConcurrentHashMap并发

https://blog.csdn.net/weixin_44460333/article/details/86770169

JDK1.7

JDK1.8

LinkedHashMap线程安全

常见问题

哈希函数

存储位置 = f(关键字)

函数f一般称为哈希函数

查找，插入操作，先通过哈希函数计算出实际存储地址，然后从数组中对应地址取出即可。

哈希冲突\哈希碰撞

如果两个不同的元素，通过哈希函数得出的实际存储地址相同怎么办？

1）开放定址法（发生冲突，继续寻找下一块未被占用的存储地址）

2）再散列函数法

3）链地址法

而HashMap即是采用了链地址法，也就是数组+链表的方式。

HashMap默认的最小容量和最大容量分别是多少？

默认最小容量(2的4次幂) 1<<4

默认最大容量 (2的30次幂) 1<<30

HashMap默认的最大容量为什么是2的30次幂？

int类型长度为4个字节共32位，去掉最高位也就是符号位（0正1负），按理说可以向左移动31位即2的31次幂。但是事实上由于二进制数字中，所以只能向左移动30位，而不能移动到处在最高位的符号位。

容量为什么要满足 2 的 n 次方？ – indexFor()

从性能和分布均匀两方面来考虑的:

加快 hash 计算速度;

均匀分布, 减少 hash 冲突;

2 的 n 次方, 可以通过位移操作来实现, 可以加快 hash 计算速度, 结合按位与计算加快数组下标的计算. 例如在 HashMap 做扩容时, 满足 2 的幂就是相当于每次扩容都是翻倍 (就是 <<1 右移一位), 这样扩容时在重新计算下标位置时, 只有两种情况, 一种是下标不变, 另一种是下标变为: 原下标位置 + 扩容前容量, 这样扩容后节点移动相对较少, 也可以提高性能…

可以改善数据的均匀分布, 减少 hash 冲突, 毕竟 hash 冲突越大, 代表数组中一个链的长度越大, 这样的话会降低 hashmap 的性能.

其中关键代码为 HashMap 中的数组下标计算: i = (n - 1) & hash, 该计算方法可以实现一个均匀分布.

modCount与Fail-Fast 机制

我们知道 java.util.HashMap 不是线程安全的，因此如果在使用迭代器的过程中有其他线程修改了map，那么将抛出ConcurrentModificationException，这就是所谓fail-fast策略。这一策略在源码中的实现是通过 modCount 域，modCount 顾名思义就是修改次数，对HashMap 内容的修改都将增加这个值，那么在迭代器初始化过程中会将这个值赋给迭代器的 expectedModCount。在迭代过程中，判断 modCount 跟 expectedModCount 是否相等，如果不相等就表示已经有其他线程修改了 Map：

modCount主要是为了防止在迭代过程中通过List的方法（非迭代器）改变了原集合，导致出现不可预料的情况，从而提前抛出并发修改异常，注意是“提前“，这可能也是Fail-Fast机制命名的由来。在可能出现错误的情况下提前抛出异常终止操作。

HashMap的put()方法流程

key(hashcode)–>hash算法【key_hashcode& (length-1)】–>计算出数组索引位置–>是否存在Entry

–>是–>hash冲突–>生成链表–>新value在链头，旧value在链尾。

–>否–>创建Entry，将key-value存放。

HashMap的get()方法流程

key(hashcode)–>hash–>indexFor–>数组索引索引位置–>索引位置的table[i]值–>是否有链表

–>是–>遍历链表。最惨的情况，就是所有元素都定位到同一个位置，形成一个长长的链表，这样get一个值时需要遍历所有节点，性能变成了O(n)–>通过key的equals方法比对查找对应的记录。

–>否–>通过key的equals方法比对查找对应的记录。

扩展问题：HashMap的get()方法定位到数组位置之后然后遍历链表的时候，e.hash == hash这个判断没必要，仅通过equals判断就可以?

如果传入的key对象重写了equals方法却没有重写hashCode，而恰巧此对象定位到这个数组位置，如果仅仅用equals判断可能是相等的，但其hashCode和当前对象不一致，这种情况，根据Object的hashCode的约定，不能返回当前对象，而应该返回null。

HashMap扩容

HashMap通过resize()方法进行扩容或者初始化的操作。

HashMap死循环=put->扩容+并发+get()

假设hashmap的容量是4，负载因子是1，阈值就是4，之前插入了3个节点，并且这3个节点通过hash函数计算出的index相同，意味着他们存放在同一链表上。

当插入第四个节点时，触发hashmap的resize()扩容机制，并且链表上的节点会rehash。不巧的是这3个节点rehash出的index又是相同的，又存放在同一链表上。

此时有两个线程同时进行，两个线程都会去新建新的数组。当采用头插法的方式移动节点，就有可能导致节点之间互相引用，形成了一个循环链表。

当在数组该位置get寻找对应的key时，就发生了死循环。

解决办法：避免在并发环境下使用HashMap，因为在HashMap本来就不支持多线程使用，要并发就用ConcurrentHashmap。

注：JDK1.8前扩容机制采用头插法的方式移动元素，JDK1.8中HashMap使用高低位来平移元素，这样保证效率的同时避免了多线程情况下扩容造成死循环的问题。

HashMap应用

缓存技术（比如memcached）的核心其实就是在内存中维护一张大的哈希表

HashTable

TreeMap

TreeMap没有调优选项，因为该树总处于平衡状态。

==与equals

对于==，如果作用于基本数据类型的变量，则直接比较其存储的值是否相等； 如果作用于引用类型的变量，则比较的是所指向的对象的地址。
对于equals方法，如果没有对equals方法进行重写，则比较的是引用类型的变量所指向的对象的地址；如果类对equals方法进行了重写的话，比较的是所指向的对象的内容。

注意：equals方法不能作用于基本数据类型的变量。

Intertor遍历

//list,set遍历
Intertor it = obj.Intertor();
//map遍历
Intertor it = obj.keySet().Intertor();
//是否有下一个值
while(it.hasNext()){
    //获取值
	it.next();
}
1
2
3
4
5
6
7
8
9

map取值

// 直接通过键找值
String v = hMap.get("3");
System.out.println(v);
// 遍历查询
// 方式一：遍历查询键值
for (Map.Entry<String, String> entry : hMap.entrySet()) {
	System.out.println("Key = " + entry.getKey() + ", Value = " + entry.getValue());
}
// 方式二：只遍历键或者值,比entrySet遍历在性能上稍好
// 只遍历map中的键
for (String key : hMap.keySet()) {
	System.out.println("Key = " + key);
}
// 只遍历map中的值
for (String value : hMap.values()) {
	System.out.println("Value = " + value);
}
// 方式三：遍历查询键值,可删除entries
Iterator<Map.Entry<String, String>> entries = hMap.entrySet().iterator();
while (entries.hasNext()) {
	Map.Entry<String, String> entry = entries.next();
	if ("3".equals(entry.getKey())) {
		entries.remove();
	} else {
		System.out.println("Key = " + entry.getKey() + ", Value = " + entry.getValue());
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

map排序

/**
	 * 将hashmap进行排序
	 * 
	 * @param hashMap
	 * @param sort 排序。asc升序,desc降序
	 * @param type 排序类型。key还是value
	 * @param b 是否打印排序前后的map
	 * @return
	 */
public Map<String, String> hashMapSort(Map<String, String> hashMap, String sort, String sortType, Boolean b) {
    System.out.println("排序" + sort + " 排序类型" + sortType);
    if (b) {
        for (Map.Entry<String, String> entry : hashMap.entrySet()) {
            System.out.println("排序前hashMap:" + entry.getKey() + " 值" + entry.getValue());
        }
    }

    // 这里将map.entrySet()转换成list
    List<Map.Entry<String, String>> list = new ArrayList<Map.Entry<String, String>>(hashMap.entrySet());
    Collections.sort(list, new Comparator<Map.Entry<String, String>>() {
        // o1.getXxx().compareTo(o2.getXxx());升序排序
        @Override
        public int compare(Entry<String, String> o1, Entry<String, String> o2) {
            if ("asc".equals(sort)) {
                if ("key".equals(sortType)) {
                    return o1.getKey().compareTo(o2.getKey());
                } else {
                    return o1.getValue().compareTo(o2.getValue());
                }
            } else {
                if ("key".equals(sortType)) {
                    return o2.getKey().compareTo(o1.getKey());
                } else {
                    return o2.getValue().compareTo(o1.getValue());
                }
            }
        }
    });
    
    if (b) {
        for (Map.Entry<String, String> map : list) {
            System.out.println("排序后hashMap:" + map.getKey() + " 值" + map.getValue());
        }
    }
    
    LinkedHashMap<String, String> linkedHashMap = new LinkedHashMap<String, String>();
    // 將list中的数据存入LinkedHashMap中
    for (Map.Entry<String, String> entry : list) {
        linkedHashMap.put(entry.getKey(), entry.getValue());
    }
    return linkedHashMap;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

树Tree

树可看作是链表的高配版。树的实现就是对链表的指针域进行了扩充，增加了多个地址指向子结点。同时将“链表”竖起来，从而凸显了结点之间的层次关系，更便于分析和理解。

树的存储结构适合存储具有“一对多”关系的数据。常见树的表示形式更接近“倒挂的树”，因为它将根朝上，叶朝下。

树的数据存储在结点中，每个结点有零个或者多个子结点。没有父结点的结点在最顶端，成为根节点；没有非根结点有且只有一个父节点；每个非根节点又可以分为多个不相交的子树。

这意味着树是具备层次关系的，父子关系清晰，家庭血缘关系明朗；这也是树与图之间最主要的区别。

树可以衍生出许多的结构，若将指针域设置为双指针，那么即可形成最常见的二叉树，即每个结点最多有两个子树的树结构。二叉树根据结点的排列和数量还可进一度划分为完全二叉树、满二叉树、平衡二叉树、红黑树等。

二叉树

二叉排序树

又名二叉查找树、二叉搜索树

对树上任意一个结点，数值必定大于等于其左子树上任意结点的数值，必小于等于其右子树上任意结点的数值。

遍历方式

1）前序遍历：根左右

2）中序遍历：左根右

3）后序遍历：左右根

注：

通过中序遍历所得到的序列，就是有序的。

能够唯一确定二叉树的遍历方式：前中，后中。

线段树

区间树

完全二叉树

除了最后一层结点，其它层的结点数都达到了最大值；最后一层的所有结点从左到右紧邻排布。

满二叉树

所有层的结点都有两个子结点。

AVL平衡二叉树

平衡二叉树又被称为AVL树，它是一棵二叉排序树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

二叉排序树：是一棵空树，或者：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉排序树。

树的高度：结点层次的最大值

平衡因子：左子树高度 - 右子树高度

二叉排序树意味着二叉树中的数据是排好序的，顺序为左结点<根节点<右结点，这表明二叉排序树的中序遍历结果是有序的。（还不懂二叉树四种遍历方式[前序遍历、中序遍历、后序遍历、层序遍历]的同学赶紧补习！）

平衡二叉树的产生是为了解决二叉排序树在插入时发生线性排列的现象。由于二叉排序树本身为有序，当插入一个有序程度十分高的序列时，生成的二叉排序树会持续在某个方向的字数上插入数据，导致最终的二叉排序树会退化为链表，从而使得二叉树的查询和插入效率恶化。

平衡二叉树的出现能够解决上述问题，但是在构造平衡二叉树时，却需要采用不同的调整方式，使得二叉树在插入数据后保持平衡。主要的四种调整方式有LL（左旋）、RR（右旋）、LR（先左旋再右旋）、RL（先右旋再左旋）。这里先给大家介绍下简单的单旋转操作，左旋和右旋。LR和RL本质上只是LL和RR的组合。

在插入一个结点后应该沿搜索路径将路径上的结点平衡因子进行修改，当平衡因子大于1时，就需要进行平衡化处理。从发生不平衡的结点起，沿刚才回溯的路径取直接下两层的结点，如果这三个结点在一条直线上，则采用单旋转进行平衡化，如果这三个结点位于一条折线上，则采用双旋转进行平衡化。

左旋：S为当前需要左旋的结点，E为当前结点的父节点。

左旋的操作可以用一句话简单表示：将当前结点S的左孩子旋转为当前结点父结点E的右孩子，同时将父结点E旋转为当前结点S的左孩子。可用动画表示：

右旋：S为当前需要左旋的结点，E为当前结点的父节点。右单旋是左单旋的镜像旋转。

左旋的操作同样可以用一句话简单表示：将当前结点S的左孩子E的右孩子旋转为当前结点S的左孩子，同时将当前结点S旋转为左孩子E的右孩子。可用动画表示：

红-黑树

平衡二叉树（AVL）为了追求高度平衡，需要通过平衡处理使得左右子树的高度差必须小于等于1。高度平衡带来的好处是能够提供更高的搜索效率，其最坏的查找时间复杂度都是O(logN)。但是由于需要维持这份高度平衡，所付出的代价就是当对树种结点进行插入和删除时，需要经过多次旋转实现复衡。这导致AVL的插入和删除效率并不高。

为了解决这样的问题，能不能找一种结构能够兼顾搜索和插入删除的效率呢？这时候红黑树便申请出战了。

红黑树具有五个特性：

1. 每个结点要么是红的要么是黑的。
2. 根结点是黑的。
3. 每个叶结点（叶结点即指树尾端NIL指针或NULL结点）都是黑的。
4. 如果一个结点是红的，那么它的两个儿子都是黑的。
5. 对于任意结点而言，其到叶结点树尾端NIL指针的每条路径都包含相同数目的黑结点。

红黑树通过将结点进行红黑着色，使得原本高度平衡的树结构被稍微打乱，平衡程度降低。红黑树不追求完全平衡，只要求达到部分平衡。这是一种折中的方案，大大提高了结点删除和插入的效率。C++中的STL就常用到红黑树作为底层的数据结构。

哈夫曼树

B树

2-3-4树

哈希树HashTree

字典树Trie

单词查找树

堆heap

了解完二叉树，再来理解堆就不是什么难事了。堆通常是一个可以被看做一棵树的数组对象。堆的具体实现一般不通过指针域，而是通过构建一个一维数组与二叉树的父子结点进行对应，因此堆总是一颗完全二叉树。

对于任意一个父节点的序号n来说（这里n从0算），它的子节点的序号一定是2n+1，2n+2，因此可以直接用数组来表示一个堆。

不仅如此，堆还有一个性质：堆中某个节点的值总是不大于或不小于其父节点的值。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

堆常用来实现优先队列，在面试中经常考的问题都是与排序有关，比如堆排序、topK问题等。由于堆的根节点是序列中最大或者最小值，因而可以在建堆以及重建堆的过程中，筛选出数据序列中的极值，从而达到排序或者挑选topK值的目的。

计算数值区间第K大值。

图Graph

图存储结构适合存储具有“多对多”关系的数据。

图的BFS与DFS算法，最小生成树prim算法与最短路径Dijkstra算法

图相较于上文的几个结构可能接触的不多，但是在实际的应用场景中却经常出现。比方说交通中的线路图，常见的思维导图都可以看作是图的具体表现形式。

图结构一般包括顶点和边，顶点通常用圆圈来表示，边就是这些圆圈之间的连线。边还可以根据顶点之间的关系设置不同的权重，默认权重相同皆为1。此外根据边的方向性，还可将图分为有向图和无向图。

图结构用抽象的图线来表示十分简单，顶点和边之间的关系非常清晰明了。但是在具体的代码实现中，为了将各个顶点和边的关系存储下来，却不是一件易事。

邻接矩阵

目前常用的图存储方式为邻接矩阵，通过所有顶点的二维矩阵来存储两个顶点之间是否相连，或者存储两顶点间的边权重。

无向图的邻接矩阵是一个对称矩阵，是因为边不具有方向性，若能从此顶点能够到达彼顶点，那么彼顶点自然也能够达到此顶点。此外，由于顶点本身与本身相连没有意义，所以在邻接矩阵中对角线上皆为0。

有向图由于边具有方向性，因此彼此顶点之间并不能相互达到，所以其邻接矩阵的对称性不再。

用邻接矩阵可以直接从二维关系中获得任意两个顶点的关系，可直接判断是否相连。但是在对矩阵进行存储时，却需要完整的一个二维数组。若图中顶点数过多，会导致二维数组的大小剧增，从而占用大量的内存空间。

而根据实际情况可以分析得，图中的顶点并不是任意两个顶点间都会相连，不是都需要对其边上权重进行存储。那么存储的邻接矩阵实际上会存在大量的0。虽然可以通过稀疏表示等方式对稀疏性高的矩阵进行关键信息的存储，但是却增加了图存储的复杂性。

因此，为了解决上述问题，一种可以只存储相连顶点关系的邻接表应运而生。

邻接表

在邻接表中，图的每一个顶点都是一个链表的头节点，其后连接着该顶点能够直接达到的相邻顶点。相较于无向图，有向图的情况更为复杂，因此这里采用有向图进行实例分析。

在邻接表中，每一个顶点都对应着一条链表，链表中存储的是顶点能够达到的相邻顶点。存储的顺序可以按照顶点的编号顺序进行。比如上图中对于顶点B来说，其通过有向边可以到达顶点A和顶点E，那么其对应的邻接表中的顺序即B->A->E，其它顶点亦如此。

通过邻接表可以获得从某个顶点出发能够到达的顶点，从而省去了对不相连顶点的存储空间。然而，这还不够。对于有向图而言，图中有效信息除了从顶点“指出去”的信息，还包括从别的顶点“指进来”的信息。这里的“指出去”和“指进来”可以用出度和入度来表示。

入度：有向图的某个顶点作为终点的次数和。

出度：有向图的某个顶点作为起点的次数和。

由此看出，在对有向图进行表示时，邻接表只能求出图的出度，而无法求出入度。这个问题很好解决，那就是增加一个表用来存储能够到达某个顶点的相邻顶点。这个表称作逆邻接表。

逆邻接表

逆邻接表与邻接表结构类似，只不过图的顶点链接着能够到达该顶点的相邻顶点。也就是说，邻接表时顺着图中的箭头寻找相邻顶点，而逆邻接表时逆着图中的箭头寻找相邻顶点。

邻接表和逆邻接表的共同使用下，就能够把一个完整的有向图结构进行表示。可以发现，邻接表和逆邻接表实际上有一部分数据时重合的，因此可以将两个表合二为一，从而得到了所谓的十字链表。

十字链表

十字链表似乎很简单，只需要通过相同的顶点分别链向以该顶点为终点和起点的相邻顶点即可。

但这并不是最优的表示方式。虽然这样的方式共用了中间的顶点存储空间，但是邻接表和逆邻接表的链表节点中重复出现的顶点并没有得到重复利用，反而是进行了再次存储。因此，上图的表示方式还可以进行进一步优化。

十字链表优化后，可通过扩展的顶点结构和边结构来进行正逆邻接表的存储：（下面的弧头可看作是边的箭头那端，弧尾可看作是边的圆点那端）

data：用于存储该顶点中的数据；

firstin指针：用于连接以当前顶点为弧头的其他顶点构成的链表，即从别的顶点指进来的顶点；

firstout指针：用于连接以当前顶点为弧尾的其他顶点构成的链表，即从该顶点指出去的顶点；

边结构通过存储两个顶点来确定一条边，同时通过分别代表这两个顶点的指针来与相邻顶点进行链接：

tailvex：用于存储作为弧尾的顶点的编号；

headvex：用于存储作为弧头的顶点的编号；

headlink 指针：用于链接下一个存储作为弧头的顶点的节点；

taillink 指针：用于链接下一个存储作为弧尾的顶点的节点；

以上图为例子，对于顶点A而言，其作为起点能够到达顶点E。因此在邻接表中顶点A要通过边AE（即边04）指向顶点E，顶点A的firstout指针需要指向边04的tailvex。同时，从B出发能够到达A，所以在逆邻接表中顶点A要通过边AB（即边10）指向B，顶点A的firstin指针需要指向边10的弧头，即headlink指针。依次类推。

十字链表采用了一种看起来比较繁乱的方式对边的方向性进行了表示，能够在尽可能降低存储空间的情况下增加指针保留顶点之间的方向性。具体的操作可能一时间不好弄懂，建议多看几次上图，弄清指针指向的意义，明白正向和逆向邻接表的表示。

拓扑排序

算法

查找

线性查找BFPRT

说明：顺序查找适合于存储结构为顺序存储或链接存储的线性表。

**基本思想：**顺序查找也称为线形查找，属于无序查找算法。从数据结构线形表的一端开始，顺序扫描，依次将扫描到的结点关键字与给定值k相比较，若相等则表示查找成功；若扫描结束仍没有找到关键字等于k的结点，表示查找失败。

复杂度分析：

查找成功时的平均查找长度为：（假设每个数据元素的概率相等） ASL = 1/n(1+2+3+…+n) = (n+1)/2 ;
当查找不成功时，需要n+1次比较，时间复杂度为O(n)；

所以，顺序查找的时间复杂度为O(n)。

二分查找

说明：元素必须是有序的，如果是无序的则要先进行排序操作。

基本思想：也称为是折半查找，属于有序查找算法。用给定值k先与中间结点的关键字比较，中间结点把线形表分成两个子表，若相等则查找成功；若不相等，再根据k与该中间结点关键字的比较结果确定下一步查找哪个子表，这样递归进行，直到查找到或查找结束发现表中没有这样的结点。

复杂度分析：最坏情况下，关键词比较次数为log2(n+1)，且期望时间复杂度为O(log2n)；

注：折半查找的前提条件是需要有序表顺序存储，对于静态查找表，一次排序后不再变化，折半查找能得到不错的效率。但对于需要频繁执行插入或删除操作的数据集来说，维护有序的排序会带来不小的工作量，那就不建议使用。

插值查找

在介绍插值查找之前，首先考虑一个新问题，为什么上述算法一定要是折半，而不是折四分之一或者折更多呢？
打个比方，在英文字典里面查“apple”，你下意识翻开字典是翻前面的书页还是后面的书页呢？如果再让你查“zoo”，你又怎么查？很显然，这里你绝对不会是从中间开始查起，而是有一定目的的往前或往后翻。
同样的，比如要在取值范围1 ~ 10000 之间 100 个元素从小到大均匀分布的数组中查找5， 我们自然会考虑从数组下标较小的开始查找。
经过以上分析，折半查找这种查找方式，不是自适应的（也就是说是傻瓜式的）。二分查找中查找点计算如下：
　　mid=(low+high)/2, 即mid=low+1/2*(high-low);
通过类比，我们可以将查找的点改进为如下：
　　mid=low+(key-a[low])/(a[high]-a[low])*(high-low)，
也就是将上述的比例参数1/2改进为自适应的，根据关键字在整个有序表中所处的位置，让mid值的变化更靠近关键字key，这样也就间接地减少了比较次数。
基本思想：基于二分查找算法，将查找点的选择改进为自适应选择，可以提高查找效率。当然，差值查找也属于有序查找。
注：对于表长较大，而关键字分布又比较均匀的查找表来说，插值查找算法的平均性能比折半查找要好的多。反之，数组中如果分布非常不均匀，那么插值查找未必是很合适的选择。
复杂度分析：查找成功或者失败的时间复杂度均为O(log2(log2n))。

斐波那契查找

在介绍斐波那契查找算法之前，我们先介绍一下很它紧密相连并且大家都熟知的一个概念——黄金分割。

黄金比例又称黄金分割，是指事物各部分间一定的数学比例关系，即将整体一分为二，较大部分与较小部分之比等于整体与较大部分之比，其比值约为1:0.618或1.618:1。

0.618被公认为最具有审美意义的比例数字，这个数值的作用不仅仅体现在诸如绘画、雕塑、音乐、建筑等艺术领域，而且在管理、工程设计等方面也有着不可忽视的作用。因此被称为黄金分割。

大家记不记得斐波那契数列：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89…….（从第三个数开始，后边每一个数都是前两个数的和）。然后我们会发现，随着斐波那契数列的递增，前后两个数的比值会越来越接近0.618，利用这个特性，我们就可以将黄金比例运用到查找技术中。

**基本思想：**也是二分查找的一种提升算法，通过运用黄金比例的概念在数列中选择查找点进行查找，提高查找效率。同样地，斐波那契查找也属于一种有序查找算法。

相对于折半查找，一般将待比较的key值与第mid=（low+high）/2位置的元素比较，比较结果分三种情况：

1）相等，mid位置的元素即为所求

2）>，low=mid+1;

3）<，high=mid-1。

斐波那契查找与折半查找很相似，他是根据斐波那契序列的特点对有序表进行分割的。他要求开始表中记录的个数为某个斐波那契数小1，及n=F(k)-1;

开始将k值与第F(k-1)位置的记录进行比较(及mid=low+F(k-1)-1),比较结果也分为三种

1）相等，mid位置的元素即为所求

2）>，low=mid+1,k-=2;

说明：low=mid+1说明待查找的元素在[mid+1,high]范围内，k-=2 说明范围[mid+1,high]内的元素个数为n-(F(k-1))= Fk-1-F(k-1)=Fk-F(k-1)-1=F(k-2)-1个，所以可以递归的应用斐波那契查找。

3）<，high=mid-1,k-=1。

说明：low=mid+1说明待查找的元素在[low,mid-1]范围内，k-=1 说明范围[low,mid-1]内的元素个数为F(k-1)-1个，所以可以递归 的应用斐波那契查找。

复杂度分析：最坏情况下，时间复杂度为O(log2n)，且其期望复杂度也为O(log2n)。

树表查找

二叉树

2-3查找树

红黑树

B树和B+树

分块查找

分块查找又称索引顺序查找，它是顺序查找的一种改进方法。
　　**算法思想：**将n个数据元素"按块有序"划分为m块（m ≤ n）。每一块中的结点不必有序，但块与块之间必须"按块有序"；即第1块中任一元素的关键字都必须小于第2块中任一元素的关键字；而第2块中任一元素又都必须小于第3块中的任一元素，……
　　算法流程：
　　step1 先选取各块中的最大关键字构成一个索引表；
　　step2 查找分两个部分：先对索引表进行二分查找或顺序查找，以确定待查记录在哪一块中；然后，在已确定的块中用顺序法进行查找。

哈希查找

什么是哈希表（Hash）？

我们使用一个下标范围比较大的数组来存储元素。可以设计一个函数（哈希函数， 也叫做散列函数），使得每个元素的关键字都与一个函数值（即数组下标）相对应，于是用这个数组单元来存储这个元素；也可以简单的理解为，按照关键字为每一个元素"分类"，然后将这个元素存储在相应"类"所对应的地方。但是，不能够保证每个元素的关键字与函数值是一一对应的，因此极有可能出现对于不同的元素，却计算出了相同的函数值，这样就产生了"冲突"，换句话说，就是把不同的元素分在了相同的"类"之中。后面我们将看到一种解决"冲突"的简便做法。

总的来说，"直接定址"与"解决冲突"是哈希表的两大特点。

什么是哈希函数？

哈希函数的规则是：通过某种转换关系，使关键字适度的分散到指定大小的的顺序结构中，越分散，则以后查找的时间复杂度越小，空间复杂度越高。

**算法思想：**哈希的思路很简单，如果所有的键都是整数，那么就可以使用一个简单的无序数组来实现：将键作为索引，值即为其对应的值，这样就可以快速访问任意键的值。这是对于简单的键的情况，我们将其扩展到可以处理更加复杂的类型的键。

算法流程：

1）用给定的哈希函数构造哈希表；

2）根据选择的冲突处理方法解决地址冲突；

常见的解决冲突的方法：拉链法和线性探测法。详细的介绍可以参见：浅谈算法和数据结构: 十一 哈希表。

3）在哈希表的基础上执行哈希查找。

哈希表是一个在时间和空间上做出权衡的经典例子。如果没有内存限制，那么可以直接将键作为数组的索引。那么所有的查找时间复杂度为O(1)；如果没有时间限制，那么我们可以使用无序数组并进行顺序查找，这样只需要很少的内存。哈希表使用了适度的时间和空间来在这两个极端之间找到了平衡。只需要调整哈希函数算法即可在时间和空间上做出取舍。

复杂度分析：

单纯论查找复杂度：对于无冲突的Hash表而言，查找复杂度为O(1)（注意，在查找之前我们需要构建相应的Hash表）。

使用Hash，我们付出了什么？
　　我们在实际编程中存储一个大规模的数据，最先想到的存储结构可能就是map，也就是我们常说的KV pair，经常使用Python的博友可能更有这种体会。使用map的好处就是，我们在后续处理数据处理时，可以根据数据的key快速的查找到对应的value值。map的本质就是Hash表，那我们在获取了超高查找效率的基础上，我们付出了什么？

Hash是一种典型以空间换时间的算法，比如原来一个长度为100的数组，对其查找，只需要遍历且匹配相应记录即可，从空间复杂度上来看，假如数组存储的是byte类型数据，那么该数组占用100byte空间。现在我们采用Hash算法，我们前面说的Hash必须有一个规则，约束键与存储位置的关系，那么就需要一个固定长度的hash表，此时，仍然是100byte的数组，假设我们需要的100byte用来记录键与位置的关系，那么总的空间为200byte,而且用于记录规则的表大小会根据规则，大小可能是不定的。

Hash算法和其他查找算法的性能对比：

排序

每种排序算法都各有优缺点。因此，在实用时需根据不同情况适当选用，甚至可以将多种方法结合起来使用。影响排序的因素有很多，平均时间复杂度低的算法并不一定就是最优的。相反，有时平均时间复杂度高的算法可能更适合某些特殊情况。同时，选择算法时还得考虑它的可读性，以利于软件的维护。一般而言，需要考虑的因素有以下四点：

1．待排序的记录数目n的大小；

2．记录本身数据量的大小，也就是记录中除关键字外的其他信息量的大小；

3．关键字的结构及其分布情况；

4．对排序稳定性的要求。

设待排序元素的个数为n。

1）当n较大，则应采用时间复杂度为O(nlog2n)的排序方法：快速排序、堆排序或归并排序。

快速排序：是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短；

堆排序：如果内存空间允许且要求稳定性的，

归并排序：它有一定数量的数据移动，所以我们可能过与插入排序组合，先获得一定长度的序列，然后再合并，在效率上将有所提高。

2）当n较大，内存空间允许，且要求稳定性，推荐归并排序

3）当n较小，可采用直接插入或直接选择排序。

直接插入排序：当元素分布有序，直接插入排序将大大减少比较次数和移动记录的次数。

直接选择排序 ：元素分布有序，如果不要求稳定性，选择直接选择排序

4）一般不使用或不直接使用传统的冒泡排序。

5）基数排序

它是一种稳定的排序算法，但有一定的局限性：

1.关键字可分解。

2.记录的关键字位数较少，如果密集更好

3.如果是数字时，最好是无符号的，否则将增加相应的映射复杂度，可先将其正负分开排序。

那么实际应用中要如何选择呢？有这些选择标准：

若n较小，采用插入排序和简单选择排序。由于直接插入排序所需的记录移动操作比简单选择排序多，所以当记录本身信息量比较大时，用简单选择排序更好。
若待排序序列基本有序，可以采用直接插入排序或者冒泡排序
若n较大，应该采用时间复杂度最低的算法，比如快排，堆排或者归并
细分的话，当数据随机分布时，快排最佳（这与快排的硬件优化有关，在之前的博文中有提到过）
堆排只需要一个辅助空间，而且不会出现快排的最坏情况
快排和堆排都是不稳定的，如果要求稳定的话可以采用归并，还可以把直接插入排序和归并结合起来，先用直接插入获得有序碎片，再归并，这样得到的结果也是稳定的，因为直接插入是稳定的

https://www.cnblogs.com/kkun/archive/2011/11/23/2260312.html

https://www.cnblogs.com/qy5201314/archive/2012/07/21/2602228.html

https://www.cnblogs.com/sunniest/p/4596182.html

插入排序

打扑克牌时，每次摸一张牌，就将它插入手上已有的牌中合适的位置，逐渐完成整个排序。

插入排序有两种写法：

交换法：在新数字插入过程中，不断与前面的数字交换，直到找到自己合适的位置。
移动法：在新数字插入过程中，与前面的数字不断比较，前面的数字不断向后挪出位置，当新数字找到自己的位置后，插入一次即可。

插入排序

每次只交换相邻两个元素

将第一个和第二个元素排好序，然后将第3个元素插入到已经排好序的元素中，依次类推

（插入排序最好的情况就是数组已经有序了）

希尔排序

1）将待排序数组按照一定的间隔分为多个子数组，每组分别进行插入排序。这里按照间隔分组指的不是取连续的一段数组，而是每跳跃一定间隔取一个值组成一组
2）逐渐缩小间隔进行下一轮排序
3）最后一轮时，取间隔为 1，也就相当于直接使用插入排序。但这时经过前面的「宏观调控」，数组已经基本有序了，所以此时的插入排序只需进行少量交换便可完成

示例：对 [84,83,88,87,61,50,70,60,80,99] 进行希尔排序：

第一遍（5 间隔排序）：按照间隔 5 分割子数组，共分成五组，分别是 [84,50],[83,70],[88,60],[87,80],[61,99]。对它们进行插入排序，排序后它们分别变成： [50,84],[70,83],[60,88],[80,87],[61,99]，此时整个数组变成 [50,70,60,80,61,84,83,88,87,99]
第二遍（2 间隔排序）：按照间隔 2 分割子数组，共分成两组，分别是 [50,60,61,83,87],[70,80,84,88,99]。对他们进行插入排序，排序后它们分别变成： [50,60,61,83,87],[70,80,84,88,99]，此时整个数组变成 [50,70,60,80,61,84,83,88,87,99]。这里有一个非常重要的性质：当我们完成 2 间隔排序后，这个数组仍然是保持 5 间隔有序的。也就是说，更小间隔的排序没有把上一步的结果变坏。
第三遍（1 间隔排序，等于直接插入排序）：按照间隔 1 分割子数组，分成一组，也就是整个数组。对其进行插入排序，经过前两遍排序，数组已经基本有序了，所以这一步只需经过少量交换即可完成排序。排序后数组变成 [50,60,61,70,80,83,84,87,88,99]，整个排序完成。

因为插入排序每次只能操作一个元素，效率低

元素个数N，取奇数k=N/2，将下标差值为k的数分为一组（一组元素个数看总元素个数决定），在组内构成有序序列，再取k=k/2，将下标差值为k的数分为一组，构成有序序列，直到k=1，然后再进行直接插入排序

选择排序

选择排序

选出最小的数和第一个数交换，再在剩余的数中又选择最小的和第二个数交换，依次类推

堆排序

以升序排序为例，利用小根堆的性质（堆顶元素最小）不断输出最小元素，直到堆中没有元素

1.构建小根堆

2.输出堆顶元素

3.将堆低元素放一个到堆顶，再重新构造成小根堆，再输出堆顶元素，以此类推

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

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

算法步骤：

创建一个堆H[0…n-1]

把堆首（最大值）和堆尾互换

3. 把堆的尺寸缩小1，并调用shift_down(0),目的是把新的数组顶端数据调整到相应位置

4. 重复步骤2，直到堆的尺寸为1

选择排序算法准则

划分排序

交换排序

冒泡排序

public static void bubbleSort(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        for (int j = 0; j < arr.length - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                // 如果左边的数大于右边的数，则交换，保证右边的数字最大
                swap(arr, j, j + 1);
            }
        }
    }
}
// 交换元素
private static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

改进1：如果某次冒泡不存在数据交换，则说明已经排序好了，可以直接退出排序

改进2：头尾进行冒泡，每次把最大的沉底，最小的浮上去，两边往中间靠1

快速排序

单轴快排

快速排序使用分治思想（Divide and conquer）把一个串行（list）分为两个子串行（sub-lists）。

快速排序算法的基本思想是：

1）从数组中取出一个数，称之为基数（pivot）
2）遍历数组，将比基数大的数字放到它的右边，比基数小的数字放到它的左边。遍历完成后，数组被分成了左右两个区域
3）将左右两个区域视为两个数组，重复前两个步骤，直到排序完成

选择一个基准元素，比基准元素小的放基准元素的前面，比基准元素大的放基准元素的后面，这种动作叫分区，每次分区都把一个数列分成了两部分，每次分区都使得一个数字有序，然后将基准元素前面部分和后面部分继续分区，一直分区直到分区的区间中只有一个元素的时候，一个元素的序列肯定是有序的嘛，所以最后一个升序的序列就完成啦

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较，但这种状况并不常见。事实上，快速排序通常明显比其他Ο(n log n) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。

算法步骤：

1 从数列中挑出一个元素，称为 “基准”（pivot），

2 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。

3 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会退出，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。

基数排序

找到最大的数，开个比最大的数大一点的数组，遍历每个元素，某个元素为k，则a[k]++,最好遍历数组a，a[k]等于多少就输出多少个k

只能处理整型数

归并排序

通过不断合并两个有序子数组，完成整个数组的排序。

将一个无序的数列一直一分为二，直到分到序列中只有一个数的时候，这个序列肯定是有序的，因为只有一个数，然后将两个只含有一个数字的序列合并为含有两个数字的有序序列，这样一直进行下去，最后就变成了一个大的有序数列

归并排序（Merge sort，台湾译作：合并排序）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

算法步骤：

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

TimSort

归并排序的思想：通过不断合并两个有序子数组，完成整个数组的排序。

为了得到两个有序子数组，我们先将整个数组不断一分为二，拆分至每个子数组只剩下一个元素时，我们就认为这个子数组是有序的。

TimSort 优化了归并排序拆分出子数组的过程。

TimSort 的主要思想是：通过遍历数组，将数组拆分成若干个单调递增的子数组。每一块称为一个 run。拆分完成后，再将 run 两两合并起来。在遍历数组时，如果遇到单调递减的小块，TimSort 会将其翻转使其单调递增。为了提升合并 run 小块时的效率，在拆分时，并不是简单的将数组划分为单调递增的小块，而是设定了一些拆分规则，使得每一个 run 小块的长度都比较接近，不至于相差太大导致合并时需要拷贝大量的「尾巴」。

对于数组 [1,4,2,3]，TimSort 会将其拆分为两个 run: [1,4]、[2,3]
对于数组 [3,4,5,1]，TimSort 会将其拆分为两个 run: [3,4,5]、[1]
对于数组 [3,2,1,4,5]，TimSort 会将其拆分为两个 run: [1,2,3]、[4,5]，其中第一个 run 是由 [3,2,1] 翻转而来。

而现实世界中的数据往往总是部分有序的。比如：

一个年级的多个班统计成绩，每个班的成绩已经排好序，最后需要将每个班的成绩表综合起来排出全年级排名。
商场统计产品销量时，每家商店的产品销量已经排好序，需要将所有商店的产品销量综合起来找出畅销商品总排行。

TimSort 非常适合处理这类场景，因为整个数组可以拆分成少量的 run 小块，将其合并即可完成排序。

只能被拆分成少量 run 小块的数组称为highly structured「高度结构化」。

计数排序

桶排序

枚举算法

枚举也叫穷举，暴力算法等。

将问题的所有可能解一一列举出来，根据判断条件判断此答案是否合适，一般用循环实现。

待解决问题的「可能解/候选解」的筛选条件，「可能解」之间相互的影响，穷举「可能解」的代价，「可能解」的穷举方式

采用枚举法能够很好的规避系统复杂性带来的冗余，同时或许在一定程度上还能够对空间进行缩减。

枚举思想的流程可以用下图来表示。通过实现事先确定好「可能解」，然后逐一在系统中进行验证，根据验证结果来对「可能解」进行分析和论证。这是一种很明显的结果导向型的思想，简单粗暴地试图从最终结果反向分析「可能解」的可行性。

不过，枚举思想的劣势当然也很明显。在实际的运行程序中，能够直接通过枚举方法进行求解的问题少之又少。而当「可能解」的筛选条件不清晰，导致「可能解」的数量和范围无法准确判断时，枚举就失去了意义。然而当「可能解」的规模比较小，同时依次验证的过程容易实施时，枚举思想不失为一种方便快捷的方式。只不过在具体使用时，还可以针对应用场景对「可能解」的验证进行优化。这种优化可以从两个方向入手；

一是问题的简化，尽可能对需要处理的问题进行模型结构上的精简。这种精简具体可体现在问题中的变量数目，减少变量的数据，从而能够从根本上降低「可能解」的组合。

二是对筛选「可能解」的范围和条件进行严格判断，尽可能的剔除大部分无效的「可能解」。

虽说如此，但是一般而言大部分枚举不可用的场景都是由于「可能解」的数量过多，无法在有限空间或有限时间内完成所有可能性的验证。不过实际上枚举思想是最接近人的思维方式，在更多的时候是用来帮助我们去理解问题，而不是解决问题。

案例：百钱买百鸡

鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一；百钱买百鸡，则翁、母、雏各几何？

案例：填写运算符

递推算法

Recursion

人脑在遇到未知的问题时，大多数人第一直觉都会从积累的「先验知识」出发，试图从「已知」推导「未知」，从而解决问题说服自己。事实上，这就是一种递推的算法思想。

1.顺推法：从已知条件出发，逐步推算出要解决问题的方法。

2.逆推法：从已知结果出发，用迭代表达式逐步推算出问题开始的条件，即顺推法的逆过程。

案例：斐波那契数列（顺推法）

案例：银行存款（逆推法）

案例：兔子问题

一对大兔子每月能生一对小兔子，且每对新生的小兔子经过一个月可以长成一对大兔子,具备繁殖能力，如果不发生死亡，且每次均生下一雌一雄，问一年后共有多少对兔子？

递归算法

是把问题转化成规模更小的同类子问题，先解决子问题，再通过相同的求解过程逐步解决更高层次的问题，直到获得最终的解。在函数或子过程的内部，直接或间接自己调用自己的算法。

递归三大要素

1：函数功能

2：结束条件（必须有，如果迭代过程中无法跳出，会造成栈溢出导致内存溢出而崩溃。）

3：函数等价关系式

在递推中，是逐次对问题进行推导直到获得最终解。而在递归中，则是逐次回归迭代直到跳出回归。

案例：汉诺塔

源于印度传说中，大梵天创造世界时造了三根金钢石柱子，其中一根柱子自底向上叠着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

package main.java.arithmetic;public class Recursion {    /**     *斐波那契数列     * 1、1、2、3、5、8、13、21、34、…     */    public int fibonacci(int n){        return fibonacci(n);    }    /**     *阶乘     * n!=1*2*3*4*5*...*n     */    public int factorial(int n){        return factorial(n);    }    /**     *上台阶     * 一次可以上1级台阶，也可以上2级台阶。求上一个n级的台阶总共有多少种方式     */    public int upStep(int n){        return upStep(n);    }    /**     *反转单链表     * 1->2->3->4反转为 4->3->2->1     */    public int reverseList(int n){        return reverseList(n);    }    /**     *三角数字     * 1,3,6,10,15,21...     */    public int triangle(int n){        return triangle(n);    }    /**     *汉诺塔     *有3根柱子A,B,C，其中n个盘子从小到大放在A柱上，现在要移到C柱上，问移动最少的步骤，其中一次只能移动一个，并且大盘不能在小盘上面     */    public int hanoi(int n){        return hanoi(n);    }    /**     *单词组合     *单词god的排列方式可为god,gdo,ogd,odg,dog,dgo六种     */    public int combine(int n){        return combine(n);    }    /**     *二分查找     *在数组中找到某个数据     */    public int binarySearch(int n){        return binarySearch(n);    }    /**     *归并排序     *有两个有序数组A,B,把A，B合并成新数组C，要求C数组也是有序的     */    public int mergeSort(int n){        return mergeSort(n);    }    public static void main(String[] args) {        Recursion recursion = new Recursion();        recursion.fibonacci(10);        recursion.factorial(10);        recursion.upStep(10);        recursion.reverseList(10);        recursion.triangle(10);        recursion.hanoi(10);        recursion.combine(10);        recursion.binarySearch(10);        recursion.mergeSort(10);    }}
1

分治算法

分而治之。分治算法的核心步骤就是两步，一是分，二是治。

将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。只要求出子问题的解，就可得到原问题的解。

一般步骤：

1.分解，将要解决的问题划分成若干个规模较小的同类问题

2.求解，当子问题划分得足够小时，用较简单的方法解决

3.合并，按原问题的要求，将子问题的解逐层合并构成原问题的解

分治思想的图解可见下图。通过层层粒度上的划分，将原问题划分为最小的子问题，然后再向上依次得到更高粒度的解。从上而下，再从下而上。先分解，再求解，再合并。

案例：归并排序

案例：大数相乘

案例：比赛日程安排

动态规划DP

Dynamic programming

把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

动态规划常常适用于有重叠子问题和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。

动态规划背后的基本思想非常简单。大致上，若要解一个给定问题，我们需要解其不同部分（即子问题），再合并子问题的解以得出原问题的解。 通常许多 子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，从而减少计算量： 一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个 子问题解之时直接查表。 这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。

讲完分治，我们知道分治思想最重要的一点是分解出的子问题是相互独立且结构特征相同的。这一点并不是所有问题都能满足，许多问题的划分的子问题往往都是相互重叠且互相影响的，那么就很难使用分治算法进行有效而又干净的子问题划分。

于是乎，动态规划来了。动态规划同样需要将问题划分为多个子问题，但是子问题之间往往不是互相独立的。当前子问题的解可看作是前多个阶段问题的完整总结。因此这就需要在在子问题求解的过程中进行多阶段的决策，同时当前阶段之前的决策都能够构成一种最优的子结构。这就是所谓的最优化原理。

最优化原理，一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。同时，这样的最优策略是针对有已作出决策的总结，对后来的决策没有直接影响，只能借用目前最优策略的状态数据。这也被称之为无后效性。

动态规划是在目前看来非常不接近人类思维方式一种算法，主要原因是在于人脑在演算的过程中很难对每一次决策的结果进行记忆。动态规划在实际的操作中，往往需要额外的空间对每个阶段的状态数据进行保存，以便下次决策的使用。

动态规划的求解思路如下图解。动归的开始需要将问题按照一定顺序划分为各个阶段，然后确定每个阶段的状态，如图中节点的F0等。然后重点是根据决策的方法来确定状态转移方程。也就是需要根据当前阶段的状态确定下一阶段的状态。

在这个过程中，下一状态的确定往往需要参考之前的状态。因此需要在每一次状态转移的过程中将当前的状态变量进行记录，方便之后的查找。

动态规划主要就是用来解决多阶段决策的问题，但是实际问题中往往很难有统一的处理方法，必须结合问题的特点来进行算法的设计，这也是这种算法很难真正掌握的原因。

案例：背包问题。

有 n 件物品和容量为 m 的背包，给出物品的重量以及价值。求解让装入背包的物品重量不超过背包容量且价值最大 。

算法步骤：

1. 最优子结构性质。如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质（即满足最优化原理）。最优子结构性质为动态规划算法解决问题提供了重要线索。
2. 子问题重叠性质。子问题重叠性质是指在用递归算法自顶向下对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。 动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只计算一次，然后将其计算结果保存在一个表格中，当再次需要计算已经计算过的子问题时，只是 在表格中简单地查看一下结果，从而获得较高的效率。

贪心算法

贪心算法在执行的过程中，每一次都会选择最大的收益，但是总收益却不一定最大。

从问题的一个初始解出发，每一次都作出「当前最优」的选择，直至遇到局部极值点。

贪心所带来的局限性很明显，无法保证最后的解是最优的，很容易陷入局部最优的情况。

但是它每一次做选择的速度很快，同时判断条件简单，能够比较快速的给出一种差不多的解决方案。这里的图解我用下图来表示。

局限：

不能保证最后的解是最优的；

不能求最大最小解问题；

只能求满足某些约束条件的可行解范围。

基本过程：

1.从问题的某一初始解出发

2.while能向给定总目标前进一步

3.求出可行解的一个解元素

4.由所有解元素组合成问题的一个可行解

下图表示的是求解对多条直线的交点。很显然，下图中的直线是不存在统一交点的，但是可以通过算法求得统一交点的最优解。若是采用贪心算法，那么在进行迭代时，每一次都会选择离此时位置最近的直线进行更新。这样一来，在经过多次迭代后，交点的位置就会在某一片区域无限轮回跳转。而这片区域也就是能求得出的大致的最优解区域。

案例：旅行推销员

给定一系列城市和每对城市之间的距离，求解访问每一座城市一次并回到起始城市的最短回路。

案例：装箱

案例：找零方案

回溯算法

回溯算法也叫试探算法。

基本思想是从一条路往前走，能进则进，不能进则退回来，重新选择一条路再试。

这样看起来，回溯算法很像是一种进行中的枚举算法，在行进的过程中对所有可能性进行枚举并判断。常用的应用场景就在对树结构、图结构以及棋盘落子的遍历上。

问题的解空间通常是在搜索问题的解的过程中动态产生的，这是回溯算法的一个重要特性。

基本步骤：

1.针对所给问题，定义问题的解空间

2.确定易于搜索的解空间结构

3.以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索

案例：八皇后

在8×8格的国际象棋上摆放8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。

案例：29选7彩票组合

DFS深度优先搜索

Depth-First-Search

【深度】一条路走到黑，不撞南墙不回头。
回溯

是搜索算法的一种。它沿着树的深度遍历树的节点，尽可能深的搜索树的分 支。当节点v的所有边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发 现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。DFS属于盲目搜索。

深度优先搜索是图论中的经典算法，利用深度优先搜索算法可以产生目标图的相应拓扑排序表，利用拓扑排序表可以方便的解决很多相关的图论问题，如最大路径问题等等。一般用堆数据结构来辅助实现DFS算法。

深度优先遍历图算法步骤：

1. 访问顶点v；

2. 依次从v的未被访问的邻接点出发，对图进行深度优先遍历；直至图中和v有路径相通的顶点都被访问；

3. 若此时图中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍历，直到图中所有顶点均被访问过为止。

上述描述可能比较抽象，举个实例：

DFS 在访问图中某一起始顶点 v 后，由 v 出发，访问它的任一邻接顶点 w1；再从 w1 出发，访问与 w1邻 接但还没有访问过的顶点 w2；然后再从 w2 出发，进行类似的访问，… 如此进行下去，直至到达所有的邻接顶点都被访问过的顶点 u 为止。

接着，退回一步，退到前一次刚访问过的顶点，看是否还有其它没有被访问的邻接顶点。如果有，则访问此顶点，之后再从此顶点出发，进行与前述类似的访问；如果没有，就再退回一步进行搜索。重复上述过程，直到连通图中所有顶点都被访问过为止。

BFS广度优先搜索

Breadth-First-Search
【广度】以我为中心，每条路都踩一脚再说。
队列

是一种图形搜索算法。简单的说，BFS是从根节点开始，沿着树(图)的宽度遍历树(图)的节点。如果所有节点均被访问，则算法中止。BFS同样属于盲目搜索。一般用队列数据结构来辅助实现BFS算法。

算法步骤：

1. 首先将根节点放入队列中。

2. 从队列中取出第一个节点，并检验它是否为目标。

如果找到目标，则结束搜寻并回传结果。

否则将它所有尚未检验过的直接子节点加入队列中。

3. 若队列为空，表示整张图都检查过了——亦即图中没有欲搜寻的目标。结束搜寻并回传“找不到目标”。
4. 重复步骤2。

双指针

指的是在遍历对象的过程中，不是普通的使用单个指针进行访问，而是使用两个相同方向（快慢指针）或者相反方向（对撞指针）的指针进行扫描，从而达到相应的目的。

换言之，双指针法充分使用了数组有序这一特征，从而在某些情况下能够简化一些运算。

对撞指针

快慢指针

迭代算法

迭代算法也叫辗转法。

将输出做为输入,再次进行处理

不断用变量的旧值递推新值的过程，解决问题时总是重复利用一种方法。

1.确定迭代变量：直接或间接地不断由旧值递推出新值的变量

2.建立迭代关系式：新值与旧值的公式或关系。（解决迭代问题的关系）

3.对迭代过程进行控制：确定迭代过程什么时候结束

所需的迭代次数是个确定值，可以计算出来：可以构建一个固定次数的循环来实现对迭代过程的控制；

所需的迭代次数无法确定：需要进一步分析出用来结束迭代过程的条件。

案例：求平方根

模拟算法

对真实场景或者过程尽可能的虚拟。

许多真实场景下，由于问题规模过大，变量过多等因素，很难将具体的问题抽象出来，也就无法针对抽象问题的特征来进行算法的设计。这个时候，模拟思想或许是最佳的解题策略。

模拟说起来是一种很玄幻的思想，没有具体的实现思路，也没有具体的优化策略。只能说，具体问题具体分析。

任意的输入，不规则的系统响应，但是只为了获得一个可靠的理想的输出。

案例：猜数字游戏

案例：掷骰子问题

位运算

并查集

戴克斯特拉算法

Dijkstra

迪科斯彻算法使用了广度优先搜索解决非负权有向图的单源最短路径问题，算法最终得到一个最短路径树。该算法常用于路由算法或者作为其他图算法的一个子模块。

该算法的输入包含了一个有权重的有向图 G，以及G中的一个来源顶点 S。我们以 V 表示 G 中所有顶点的集合。每一个图中的边，都是两个顶点所形成的有序元素对。(u, v) 表示从顶点 u 到 v 有路径相连。我们以 E 表示G中所有边的集合，而边的权重则由权重函数 w: E → [0, ∞] 定义。因此，w(u, v) 就是从顶点 u 到顶点 v 的非负权重（weight）。边的权重可以想像成两个顶点之间的距离。任两点间路径的权重，就是该路径上所有边的权重总和。已知有 V 中有顶点 s 及 t，Dijkstra 算法可以找到 s 到 t的最低权重路径(例如，最短路径)。这个算法也可以在一个图中，找到从一个顶点 s 到任何其他顶点的最短路径。对于不含负权的有向图，Dijkstra算法是目前已知的最快的单源最短路径算法。

算法步骤：

1. 初始时令 S={V0},T={其余顶点}，T中顶点对应的距离值

若存在<v0,vi>，d(V0,Vi)为<v0,vi>弧上的权值

若不存在<v0,vi>，d(V0,Vi)为∞

2. 从T中选取一个其距离值为最小的顶点W且不在S中，加入S

3. 对其余T中顶点的距离值进行修改：若加进W作中间顶点，从V0到Vi的距离值缩短，则修改此距离值

重复上述步骤2、3，直到S中包含所有顶点，即W=Vi为止

遗传算法

决策树-剪枝

蚁群算法

朴素贝叶斯分类

朴素贝叶斯分类算法是一种基于贝叶斯定理的简单概率分类算法。贝叶斯分类的基础是概率推理，就是在各种条件的存在不确定，仅知其出现概率的情况下， 如何完成推理和决策任务。概率推理是与确定性推理相对应的。而朴素贝叶斯分类器是基于独立假设的，即假设样本每个特征与其他特征都不相关。

朴素贝叶斯分类器依靠精确的自然概率模型，在有监督学习的样本集中能获取得非常好的分类效果。在许多实际应用中，朴素贝叶斯模型参数估计使用最大似然估计方法，换言之朴素贝叶斯模型能工作并没有用到贝叶斯概率或者任何贝叶斯模型。

安全算法

非对称算法

RSA1024

RSA2048

DSA3072

ECCP256

量子攻击非对称算法-shor 非对称算法不再安全

对称算法

3DES

AES128

AES256

量子攻击对称算法-Grover加速

哈希算法

SHA160

SHA256

SHA384

学习资料

《线性代数》《统计学习方法》《机器学习》《模式识别》《深度学习》

冒泡、选择、插入、希尔、归并、快排、堆排、桶排、基数的原理、平均时间复杂度、最坏时间复杂度、空间复杂度、是否稳定快排的partition函数与归并的Merge函数 对冒泡与快排的改进二分查找，与变种二分查找找到数组中第二小的元素找到数组中第一个没有重复的整数合并两个分类数组重新排列数组中的正值和负值## 表###  散列/哈希表Hash散列表也叫哈希表，是一种通过键值对直接访问数据的机构。在初中，我们就学过一种能够将一个x值通过一个函数获得对应的一个y值的操作，叫做映射。散列表的实现原理正是映射的原理，通过设定的一个关键字和一个映射函数，就可以直接获得访问数据的地址，实现O(1)的数据访问效率。在映射的过程中，事先设定的函数就是一个映射表，也可以称作散列函数或者哈希函数。散列表的实现最关键的就是散列函数的定义和选择。一般常用的有以下几种散列函数：> **直接寻址法**：取关键字或关键字的某个线性函数值为散列地址。>> **数字分析法**：通过对数据的分析，发现数据中冲突较少的部分，并构造散列地址。例如同学们的学号，通常同一届学生的学号，其中前面的部分差别不太大，所以用后面的部分来构造散列地址。>> **平方取中****法**：当无法确定关键字里哪几位的分布相对比较均匀时，可以先求出关键字的平方值，然后按需要取平方值的中间几位作为散列地址。这是因为：计算平方之后的中间几位和关键字中的每一位都相关，所以不同的关键字会以较高的概率产生不同的散列地址。>> **取随机数法**：使用一个随机函数，取关键字的随机值作为散列地址，这种方式通常用于关键字长度不同的场合。>> **除留取余法**：取关键字被某个不大于散列表的表长 n 的数 m 除后所得的余数 p 为散列地址。这种方式也可以在用过其他方法后再使用。该函数对 m 的选择很重要，一般取素数或者直接用 n。确定好散列函数之后，通过某个`key`值的确会得到一个唯一的`value`地址。但是却会出现一些特殊情况。即通过不同的`key`值可能会访问到同一个地址，这个现象称之为冲突。冲突在发生之后，当在对不同的`key`值进行操作时会使得造成相同地址的数据发生覆盖或者丢失，是非常危险的。所以在设计散列表往往还需要采用冲突解决的办法。常用的冲突处理方式有很多，常用的包括以下几种：> **开放地址法**（也叫开放寻址法）：实际上就是当需要存储值时，对Key哈希之后，发现这个地址已经有值了，这时该怎么办？不能放在这个地址，不然之前的映射会被覆盖。这时对计算出来的地址进行一个探测再哈希，比如往后移动一个地址，如果没人占用，就用这个地址。如果超过最大长度，则可以对总长度取余。这里移动的地址是产生冲突时的增列序量。>> **再哈希法**：在产生冲突之后，使用关键字的其他部分继续计算地址，如果还是有冲突，则继续使用其他部分再计算地址。这种方式的缺点是时间增加了。>> **链地址法**：链地址法其实就是对Key通过哈希之后落在同一个地址上的值，做一个链表。其实在很多高级语言的实现当中，也是使用这种方式处理冲突的。>> **公共溢出区**：这种方式是建立一个公共溢出区，当地址存在冲突时，把新的地址放在公共溢出区里。目前比较常用的冲突解决方法是链地址法，一般可以通过数组和链表的结合达到冲突数据缓存的目的。左侧数组的每个成员包括一个指针，指向一个链表的头。每发生一个冲突的数据，就将该数据作为链表的节点链接到链表尾部。这样一来，就可以保证冲突的数据能够区分并顺利访问。考虑到链表过长造成的问题，还可以使用红黑树替换链表进行冲突数据的处理操作，来提高散列表的查询稳定性。### 链表Link链表相较于数组，除了数据域，还增加了指针域用于构建链式的存储数据。链表中每一个节点都包含此节点的数据和指向下一节点地址的指针。由于是通过指针进行下一个数据元素的查找和访问，使得链表的自由度更高。这表现在对节点进行增加和删除时，只需要对上一节点的指针地址进行修改，而无需变动其它的节点。不过事物皆有两极，指针带来高自由度的同时，自然会牺牲数据查找的效率和多余空间的使用。一般常见的是有头有尾的单链表，对指针域进行反向链接，还可以形成双向链表或者循环链表。![在这里插入图片描述](https://img-blog.csdnimg.cn/20210307141928738.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjYwNzQzNw==,size_16,color_FFFFFF,t_70#pic_center)链表和数组对比链表和数组在实际的使用过程中需要根据自身的优劣势进行选择。链表和数组的异同点也是面试中高频的考察点之一。这里对单链表和数组的区别进行了对比和总结。![img](https://img-blog.csdnimg.cn/img_convert/27b8c6b296bf438b950f3572980a7990.png)###  跳表从上面的对比中可以看出，链表虽然通过增加指针域提升了自由度，但是却导致数据的查询效率恶化。特别是当链表长度很长的时候，对数据的查询还得从头依次查询，这样的效率会更低。跳表的产生就是为了解决链表过长的问题，通过增加链表的多级索引来加快原始链表的查询效率。这样的方式可以让查询的时间复杂度从O(n)提升至O(logn)。![在这里插入图片描述](https://img-blog.csdnimg.cn/20210307141943769.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjYwNzQzNw==,size_16,color_FFFFFF,t_70#pic_center)跳表通过增加的多级索引能够实现高效的动态插入和删除，其效率和红黑树和平衡二叉树不相上下。目前redis和levelDB都有用到跳表。从上图可以看出，索引级的指针域除了指向下一个索引位置的指针，还有一个down指针指向低一级的链表位置，这样才能实现跳跃查询的目的。### 线性表### 顺序表## 哈希表## 链表hash函数，冲突解决方法有哪些### 存储方式数组：顺序结构。连续的存储在内存地址链表：链式结构 。随机的存储在内存地址，每个元素都存储了下一个元素的地址 ### 操作的时间复杂度![](..\数据结构与算法\img\链表与数组1.png)插入多，读取少。用链表。 插入少，读取多。用数组。 ### 单向链表的操作单向链表：所有节点串成一列，而且指针所指的方向一样 操作特点：为节点分配空间。修改节点的联系。#### 尾插法：新的节点成为尾节点#### 头插法：新的节点成为头节点
1

https://github.com/MisterBooo/Article

https://www.cnblogs.com/eniac12/p/5329396.html

https://gitchat.csdn.net/activity/5d3175895daf051f53e81525

/**     * 快速排序     * @param arr     * @return     */    public  int[] quickSort(int[] arr){        Arrays.sort(arr);        return arr;    }    /**     * 选择排序     * 数组的每个元素都与首位下标值进行比较，判断是否交换位置，一个轮回后，首位下标后移一位。     * 2个for+贪吃蛇。j=i     */    public int[] selectionSort(int[] arr){        int temp = 0;        for (int i = 0; i < arr.length; i++) {            for (int j = i; j < arr.length; j++) {                if(arr[i]<arr[j]){                    temp = arr[i];                    arr[i] = arr[j];                    arr[j] = temp;                }            }        }        return arr;    }    /**     * 冒泡排序     * 数组的相邻值进行比较，判断是否交换位置，一个轮回后，首位下标后移一位。     * 2个for+贪吃蛇。j=i+1     */    public int[] bubbleSort(int[] arr){        int temp = 0;        for (int i = 0; i < arr.length; i++) {            for (int j = i+1; j < arr.length; j++) {                if(arr[i]<arr[j]){                    temp = arr[i];                    arr[i] = arr[j];                    arr[j] = temp;                }            }        }        return arr;    }    /**     * 插入排序     * 2个for+贪吃蛇     */    public int[] insertionSort(int[] arr){        int temp = 0;        for (int i = 0; i < arr.length; i++) {            for (int j = 0; j < arr.length; j++) {                if(arr[i]<arr[j]){                    temp = arr[i];                    arr[i] = arr[j];                    arr[j] = temp;                }            }        }        return arr;    }
1