本文源于极客时间的数据结构和算法的读书笔记

数据结构是一组数据的存储结构，

算法是操作数据的一组方法

来历，特点，适合解决的问题，和实际的应用场景

复杂度分析

代码运行的更快，代码更节省空间，执行效率是算法的一个非常重要的考量指标；

所有代码的执行时间T(n)与每行代码的执行次数n成正比

1
2
3

T(n)=O(f(n))
n为数据规模的大小，f（n）表示每行代码执行的次数总和，T(n)表示代码随数据规模增长的变化趋势。
当n很大时，f(n)公式中的低阶，常量，系数并不能左右增长趋势，我们只需要记录一个最大量级。

时间复杂度

分析技巧

只关注循环执行次数最多的一段代码
加法法则：总复杂度等于量级最大的那段代码的复杂度
乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

常见的时间复杂度

O(1)
O(logn)
O(n)
,O(nlogn)
O(n2)

最好、最坏、平均、均摊时间复杂度

最好：在最理想的情况下，执行这段代码的时间复杂度

最坏：在最糟糕的情况下，执行这段代码的时间复杂度

平均情况时间复杂度：代码在所有情况下执行的次数的加权平均值（概率乘以时间复杂度）表示

均摊时间复杂度：在代码执行的所有复杂度情况中绝大部分是低级别的复杂度，个别情况是高级别复杂度且发生具有时序关系时，可以将个别高级别复杂度均摊到低级别复杂度上，基本上均摊结果就等于低级别复杂度。

线性表与非线性表

线性表是数据排成一条线一样的结构，每个线性表上的数据最多只有前后两个方向。

数组、链表、队列、栈都是线性表结构

非线性表，数据不是简单的前后关系

二叉树、堆、图等就是非线性

数组

数组为什么要从0开始，而不是1开始

数组是一种线性表数据结构，用一组连续的内存空间，来存储一组相同类型的数据

数组的特点

随机访问：由于其线性表的结构、连续的内存空间和相同类型的数据；
插入、删除慢：平均复杂度为O(n)

链表

零散的内存块串联起来使用，常见的单链表、双向链表、循环链表

结点：每个内存块都叫做结点，结点存储数据以及记录链上的下一个结点的地址(后继指针next)

头结点、为链表第一个结点、记录链表的基地址

尾结点：为链表的最后一个结点，指向一个空地址NULL

循环链表是一种特殊的单链表：尾结点指向链表的头结点，这样从链尾到链头比较方便

双向链表：支持两个方向，有前区指针prev和后继指针next

链表的特点

插入、删除快，时间复杂度O(1)
随机访问慢：O(n)

单链表反转

//一边走，一边调整指针

链表中环的检测

//快慢指针

两个有序的链表合并

//两个指针

删除链表倒数第 n 个结点

//n+1长度的队列

求链表的中间结点

//快慢指针，奇偶之分

206，141，21，19，876

栈

后进者先出，先进者后出，操作受限的线性表

入栈：栈顶插入一个数据

出栈：从栈顶删除一个数据

用数组实现的栈叫做顺序栈、用链表实现的栈叫做链式栈。

应用：函数调用，运算符、浏览器前进后退

20,155,232,844,224,682,496.

队列

先进先出就是队列

入队：放一个数据到队列尾部

出队：从队列头部取一个元素

用数组实现的叫做顺序队列、用链表实现的叫做链式队列

队列的应用：循环队列、阻塞队列、并发队列

递归

使用递归的三个条件：

一个问题的解可以分解为几个子问题的解
这个问题与分解之后的子问题，除了数据规模不同，求解思路完全一样
存在递归终止条件

递归思路：找到如何将大问题分解为小问题的规律，并且写出递推公式、找到终止条件

注意点：

避免去想一层一层的调用关系、不要试图分解递归的每个步骤，只需要抽象为一个递推公式
警惕堆栈溢出
重复计算：通过散列表保存出现过的结果，递归过程中先从里面取

排序

如何分析一个排序算法：

排序算法的执行效率
1. 最好情况、最坏情况、平均情况时间复杂度：算法在不同数据（有序等）下的性能是不同的
2. 时间复杂度的系数、常数、低阶：数据规模，考虑实际使用场景
3. 比较次数和交换（移动）次数
排序算法的内存消耗：原地排序（空间复杂度O1）的排序算法
排序算法的稳定性：待排序的序列中存在值相等的元素，排序之后，相等元素之间原有顺序不变

冒泡、插入、选择O(n2)

冒泡排序

//冒泡排序

最好：一次冒泡O(n)，最坏：n次冒泡O(n2);平均复杂度：通过有序度于逆序度来分析O(n2)

- 有序度是具有有序关系的元素对的个数，排序就是增加有序度，减少逆序度的过程，最终达到满有序度的状态，逆序度数为排序的最少交换次数

原地排序：空间复杂度1

稳定排序算法

插入排序

原理：动态的往有序集合中添加元素

方案：将数组中的元素分为两个区间、已排序区间和未排序区间，初始已排序区间只有一个元素，然后取未排序区间中的元素，在已排序区间中找到合适的插入未知将其插入，并保证已排序区间数据一直有序。

//插入排序

最好：O(n);最坏：O(n2);;平均：O(n2)

原地排序

稳定排序

选择排序

原理：类似插入排序，不同的是每次都从未排序的集合中选择最小元素与到排序集合的末尾元素进行交换

最好，最坏，平均都是O(n2)

不稳定排序

为什么推荐插入排序：从代码实现，比较和交换次数上考虑

https://mp.weixin.qq.com/s/HQg3BzzQfJXcWyltsgOfCQ

https://visualgo.net

快排、归并O(nlongn)

快排

核心思想:选择一个合适的结点作为分区点，将小于分区点的放到左边，将大于分区点的放到右边，然后递归解决两个数组

递推公式：
quick_sort(p…r) = quick_sort(p…q-1) + quick_sort(q+1, r)

终止条件：
p >= r

// 快速排序，A 是数组，n 表示数组的大小
quick_sort(A, n) {
  quick_sort_c(A, 0, n-1)
}
// 快速排序递归函数，p,r 为下标
quick_sort_c(A, p, r) {
  if p >= r then return
  
  q = partition(A, p, r) // 获取分区点
  quick_sort_c(A, p, q-1)
  quick_sort_c(A, q+1, r)
}

归并

核心思想：排序一个数组，先把数组从中间分为前后两部分、然后对前后两部分分别排序，再将排好序的两部分合并在一起，整个数组就有序了。

书写方法：递归思想，写出递推公式、和终止条件

递推公式：
merge_sort(p…r) = merge(merge_sort(p…q), merge_sort(q+1…r))

终止条件：
p >= r 不用再继续分解

转化为代码

//归并排序n个元素A
merger_sort(A,n){
    merger_sort_c(A,0,n-1);
}
//将p到r的A数组进行排序
merger_sort_c(A,p,r){
    if p>= r then return;
    q= (p+r)/2;中间位置
     //分治递归
    merger_sort_c(A,p,q);
    merger_sort_c(A,q+1,r);
    //将两个有序数组合并和一个有序数组
    merge(A[p..r],A[p...q],A[q+1...r]);
}