本节回顾了数组、链表、栈、队列、递归、排序。

数组

array作为线性表数据结构，使用一组连续的内存空间存储一组相同类型的数据。

特点：支持随机访问，但插入、删除操作效率低，平均时间复杂度为O(n)。

线性表数据结构

而非线性表的数据结构有二叉树、堆、图。可以看到线性表数据之间的关系较为简单。

数据结构与数据在内存空间中存储是否连续无关，换句话说，连续的内存空间下对相同类型的数据具有随机访问特性。寻址将十分方便。

数组初始化：int[] a = new int[10]

int[] a = new int[10]

1 2	`//寻址，即偏移量计算 a[i]_address = base_address + i * data_type_size`

正常在数组上插入、删除是低效的，往往需要移动k位。插入数据到第k位，为避免大规模数据搬移，可以将第k位的数据搬移到数组最后，把新的数据直接放到第k位置；反之，删除操作下，为了内存的连续性将第k位删除后将尾部数据搬移到第k位，以填补中间的空洞。

如果追求数据的连续性，可以将多次删除操作集中在一起执行，先记录下已经删除的数据，当触发数组空间不够的时候再进行一次真正的删除操作，以达到大大减少删除操作导致的数据搬移。这就是JVM标记清楚垃圾回收算法的思想。

【警惕】数组的访问越界问题：

for循环的结束条件为i<=3，而当i=3时，数组a[3]访问越界，在有些运行环境下这个越界的地址刚好是i的内存地址，即a[3]=0相当于i=0，因此导致代码无限循环。

int main(int argc, char* argv[]){
    int i = 0;
    int arr[3] = {0};
    for(; i<=3; i++){
        arr[i] = 0;
        printf("hello world.")
    }
    return 0;
}

函数体的局部变量在栈上，连续压栈

针对数组类型，Java、cpp等提供了容器类，如ArrayList、vector。如ArrayList优势是将很多数组操作细节封装起来，并提供动态扩容（自动扩容1.5倍），但扩容操作涉及内存申请和数据搬移，所以仍建议事先确定数组大小。

如从数据库取出10000条数据，事先确定大小可以节省开销：

ArrayList<User> users = new ArrayList(10000);
for(int i=0; i< 10000; ++i){
    users.add(xxx);
}

一些经验：

ArrayList 无法存储基本类型，如int、long需要封装为Integer、Long类，而AutoBoxing、Unboxing有性能消耗，所以如果关注性能或使用基本数据类型，则选用数组。
数组大小已知、对数组操作简单；
表示多维数组时，数组Object[] [] array; 看着比较直观；在容器中需要这样： ArratList< ArrayList> array;
业务开发使用容器，省时省力；

链表

链表相对于数组，具有不同的内存组织方式，进而导致插入、删除、随机访问操作的不同。

引言：使用链表实现LRU缓存淘汰算法

常见的有CPU缓存，数据库缓存，浏览器缓存。在缓存满了时需要及时清理数据，因此需要缓存淘汰策略来定：first in first out，least frequently used， least recently used。

答：维护一个有序的单链表，越靠近链表尾部的结点是越早访问的，越近访问的越在表头。即当需要访问一个数据时，我们从链表的头部开始依次遍历。

如果待访问的数据已被缓存在该链表中，遍历得到该结点，将其从原来位置取出，再插入到链头；
如果数据不在该链表中：
1. 若缓存没满：将新的数据结点插入链表的头部。
2. 若缓存已满：将链尾结点删除，将新的数据结点插入链表的头部。

数组：

实现：连续的内存空间；-> CPU可预读数组中的数据，因此效率高些；
声明后大小固定，扩容需要拷贝；
按下标访问数据速度快，同时插入、删除需要移动数组，效率低。

链表：

实现：在内存中不连续；
支持动态扩容；
链表通过指针将一组零散的内存块串联起来使用；结点需要有数据、next指针和prev指针，存储同样的数据使用链表更耗费空间。
链表的插入、删除操作快，但随机访问第k个元素只能依次遍历结点。

单链表

单链表的第一个结点叫头结点，最后一个结点叫尾结点。头结点记录链表的基地址，尾结点指向空地址NULL。

循环链表

循环链表适合处理具有环形结构的数据。如约瑟夫问题。

双向链表相对增加了前驱指针prev，如容器LinkedHashMap就用到双向链表来实现。

链表的删除操作：

插入操作：

查询：对一个有序链表，双向链表的按值查询效率更高，可以记录上次查找位置p

代码技巧一：理解指针（引用）的含义

// p结点中的next指针存储了q结点的内存地址
p->next = q;
// p结点的next指针存储了p结点的下下个结点的内存地址
p->next = p->next->next;

技巧二：警惕指针丢失和内存泄露

// 插入结点时需要注意操作顺序
// 删除链表结点时记得手动释放内存空间。
p->next = x;
x->next = p->next;

技巧三：利用哨兵简化实现难度（带头链表）

// 在结点p后面插入新的结点
// 正常这样：
new_node->next = p->next;
p->next = new_node;

// 但 向空结点中插入第一个结点需要特殊处理：
if (head == null){
    head = new_code;
}

// 删除结点p的后继结点:
p->next = p->next->next;

// 删除链表的最后一个结点，亦需要特殊处理：
if (head->next == null){
    head= null;
}

这里，head表示链表的头结点指针，指向链表中的第一个结点。

所以对插入、删除第一个结点或最后一个结点的情况需要特殊处理，操作比较繁琐，为此引入哨兵，变成带头链表：有哨兵结点一直存在且不存储数据。将操作统一：

技巧四：重点留意边界条件处理

如果链表为空时，代码是否能正常工作？
如果链表只包含1个结点时，
如果链表只包含2个结点时，
代码逻辑在处理头结点和尾结点时，？

技巧五：举例画图，辅助思考

技巧六：多写多练，熟能生巧

常见的5个链表操作：

单链表反转
链表中环的检测
两个有序的链表合并
删除链表倒数第n个结点
求链表的中间结点

栈

引言：使用2个栈实现浏览器的前进、后退功能

答：将首次浏览的页面入栈X，后退时该数据从X出栈，压入栈Y；当访问新页面时，清空Y栈，将新页面数据压栈X。

栈，是一种操作受限的线性表。用数组实现的叫顺序栈，用链表实现的叫链式栈，特性也有些许区别。

// 基于数组 实现顺序栈
public class ArrayStack {
    private String[] items;
    private int count; //栈中元素数量
    private int n; //栈的大小为n
    
    // 初始化数组，大小为n
    public ArrayStack(int n) {
        this.items = new String[n];
        this.n = n;
        this.count = 0;
    }
    // 入栈操作
    public boolean push(String item) {
        // 数组空间不够
        if (count == n) return false;
        // 将item放到下标count处
        items[count] = item;
        ++count;
        return true;
    }
    // 出栈操作
    public String pop() {
        // 栈为空
        if (count == 0) return null;
        // 注意这里count为元素个数，访问下标为count-1
        String temp = items[count-1];
        --count;
        return temp;
    }
}

栈的其他应用

函数调用栈
表达式求值

其中一个栈保存操作数，一个栈保存运算符。

括号匹配：从左到右扫描

队列

引言：队列在线程池等有限资源池中的应用

答：当线程池没有空闲资源时，新任务请求到线程资源，线程池可采用阻塞处理方式，将请求排队，等到有空闲线程时取出排队的请求并处理。

当然，排队应该是有限的，线程池可采用非阻塞处理方式，直接拒绝任务请求。

队列也是一种操作受限的线性表。有入队、出队操作，一般为先进先出特征。与栈只有栈顶指针不同的是，队列有head指针和tail指针。

与栈的实现类似，有用数组实现的顺序队列，以及用链表实现的链式队列。如用数组实现时，对数组元素的删除操作会使得元素存储不连续，此时需要触发搬移操作：

顺序队列

public class ArrayQueue {
    private String[] items;
    private int n =0;
    private head = 0;
    private tail = 0;
    
    //申请大小为capacity的数组
    public ArrayQueue(int capacity) {
        items = new String[capacity];
        n = capacity;
    }
    //入队
    public boolean enqueue(String item){
        //入队前检查是否已满
        //if (tail == n) return false;
        // 改进：队尾满了的时候触发:判断队头是否有位置，有则数据搬移
        if (tail == n){
            if (head == 0) return false;
            for(int i=head; i<tail; ++i){
                items[i-head] = items[i];
            }
            //别忘记数据搬移完毕后，修改指针:
            tail = n-head;
            head = 0;
        }
        items[tail] = item;
        ++tail;
        return true;
    }
    //出队
    public String dequeue() {
        if(head == tail) return null;
        String temp = items[head];
        ++head;
        return temp;
    }
}

链式队列

根据链表的特性有些不同，

入队时 tail->next = new_node; tail = tail->next; 出队时 head = head->next;

循环队列

需要注意队列空、满时的条件判断：

tail == head 队列为空
(tail +1 )%n == head 队列已满

public class CircularQueue {
    private String[] items;
    private int n = 0;
    private head = 0;
    private tail = 0;
    
    //
    public CircularQueue(int capacity){
        items = new String[capacity];
        n = capacity;
    }
    //
    public boolean enqueue(String item){
        //判断队满
        if ((tail+1)%n == head) return false;
        items[tail] = item;
        // 注意这里的tail变化
        tail = (tail+1)%n;
        return true;
    }
    //
    public String dequeue(){
        //出队，先判断队列是否为空
        if (head==tail) return false;
        String temp = items[head];
        head = (head+1)%n;
        return temp;
    }
}

阻塞队列

阻塞队列是在队列的基础上增加了阻塞操作，即队列为空时从队头取元素会被阻塞，直到队列中有数据才能返回；如果队列已满，插入数据操作被阻塞。类似于“生产者-消费者模型”，用来调节生产、消费速度和提高数据处理效率。

并发队列

线程安全

递归

引言：找到最终推荐人

//逻辑代码,actor_id表示用户id，referrer_id表示推荐人id
long findRootReferrerId(long actorID){
    Long referrerID = select referrer_id from [table] where actor_id = actorId;
    if (referrerID == null) return actorID;
    return findRootReferrerId(referrerID)
}
// A --> B --> C
// 该思路不适合 递归太深的情况，或数据库里有无限循环

递归recursion是一种高效的编程技巧，但也需要注意堆栈溢出、重复计算、函数调用耗费时间、空间复杂度高等问题。

递归三要素：

将大问题分解为小问题的规律；
子问题的求解思路相同，
存在递归终止条件；

为了避免堆栈溢出，可以设置递归深度、克制递归调用规模、改写为非递归代码。

递归需要警惕重复计算

通过数据结构来保存求解过的值，在调用时先查询：

public int f(int n){
    if (n== 1) return 1;
    if (n== 2) return 2;
    
    // 将hasSolvedList理解为map，key为n，value是f()函数
    if (hasSolvedList.containsKey(n)){
        return hasSolvedList.get(n);
    }
    int ret = f(n-1) + f(n-2);
    hasSolvedList.put(n, ret);
    return ret;
}
// 在这个简单加法中,似乎hasSolvedList简化版可用数组，下标为key,数组中存储值。

改写为非递归代码

//简单递归
int f(int n) {
    if (n == 1) return 1;
    return f(n-1) + 1;
}

//改写为非递归代码：
int f(int n){
    int ret = 1;
    for (int i=2; i<=n; ++i){
        ret = ret+1;
    }
    return ret;
}

//走台阶，一步可以跨1或2步，问n个台阶多少种走法
int f(int n) {
    if (n== 1) return 1;
    if (n== 2) return 2;
    return f(n-1) + f(n-2);
}
// 这样理解：走n个台阶的走法就是：先走1个台阶后，n-1个台阶的走法；+先走2个台阶后，n-2个台阶的走法
// 即 f(n) = f(n-1) + f(n-2)
// f(2) 表走2个台阶的走法。f(3)表示为先走一个台阶后的走法+先走2个台阶后的走法
//改写
// 这里在循环中，存储了n个台阶的走法。有点晕
int f(int n){
    if (n==1) return 1;
    if (n==2) return 2;
    
    int ret = 0;
    int pre = 2;
    int prepre = 1;
    for (int i=3; i<=n; ++i){
        ret = pre + prepre;
        prepre = pre;
        pre = ret;
    }
    return ret;
}

调试递归代码的方法

打印日志发现递归值；2. 结合条件断点进行调试；

排序

面对一个排序算法，需要从他执行效率、内存消耗、稳定性上搞清楚，时常问问：

是原地排序么
时间复杂度多少：最好、最坏、平均情况，以及原始数据情况下的算法复杂度
稳定么

冒泡排序

冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较看是否满足大小关系要求。决定是否互换。一次冒泡会让至少一个元素移动到应该在的位置，重复n就完成n个数据的排序工作。

如果某一次冒泡操作没有数据交换，即已经达到完全有序。

// a为数组，n表示数组大小
public void bubbleSort(int[] a,int n){
    if (n <= 1) return;
    boolean flag = false; //哨兵，表示提前退出冒泡循环的标志位
    for(int i=0; i<n; ++i){
        for(int j=0; j<n-i-1; ++j){
            if(a[j] > a[j+1]){
                int temp = a[j];
                a[j] = a[j+1];
                a[j+1] = temp;
                flag = true; //表示有数据交换
            }
        }
        // 某一次没有数据交换，退出
        if(!flag) break;
    }
}

插入排序

插入算法的核心思想是取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间数据一直有序。重复这个过程知道未排序区间中元素为空。

包含操作：元素比较、元素的移动；不同的查找插入点方法，元素的比较次数是有区别的。但对一个给定的初始序列，移动操作的次数总是固定的，等于逆序度。

满有序度= n*(n-1)/2

import java.util.Arrays;
public class InsertionSort {
    public static void main(String[] args){
        int[] data = new int[]{4,5,6,1,3,2};
        System.out.println(Arrays.toString(data));
        insertionSort(data, data.length);
        System.out.println(Arrays.toString(data));
    }
    
    //a为数组，n表示数组大小
    public static void insertionSort(int[] a, int n) {
        if(n<=1) return;
        for(int i=1; i<n; ++i){
            int value = a[i];
            int j = i-1;
            //查找插入位置
            for(;j>=0; --j){
                if(a[j] > value){
                    a[j+1] = a[j]; //交换数据，将较大的数据后移
                } else {
                    break;
                }
            }
            a[j+1] = value; //插入数据
        }
    }
}
// [4, 5, 6, 1, 3, 2]
// [1, 2, 3, 4, 5, 6]

选择排序

选择排序的实现类似于插入排序。每次从未排序区间中找到最小的元素，将其放到已排序区间外的末尾（该位置上的元素与该次找到的最小元素交换位置）。

归并排序

分治思想：分而治之，大问题分解成小问题来解决。递归编程技巧：分析出递推式，找到终止条件。

分区：

引言：如何在O(n)的时间复杂度内查找一个无序数组中的第k大元素？

答：对数组A做类似快排操作，每次排序A[0..n-1] = A[0..q-1] + A[q] + A[q+1.. n-1], A[q]的位置就被固定下来了，即第k大元素就是当q+1==k时的元素；如果k>p+1,说明元素在后面的区间里，继续找。

归并思想：对一个数组排序，先把数组从中间分成前后两部分，然后对前后两部分分别排序，再将排好序的两部分合并在一起，整个数组就有序了。这是一个下至上的排序过程。

// 分析
//递推公式
merge_sort(p..r) = merge( merge_sort(p..q), merge_sort(q+1,r) )
//分解的 终止条件
p >= r

//归并排序伪代码， A为数组，n为数组大小
merge_sort(A, n){
    merge_sort_c(A, 0, n-1);
}
merge_sort_c(A, p, r){
    if p>=r then return;
    
    // 取中间位置
    q = (p+r)/2;
    //分治递归
    merge_sort_c(A, p, q-1);
    merge-sort_c(A, q+1, r);
    //将上面两个有序数组 合并至数组中，这里就是分解完毕后，从下至上合并排序过程
    merge(A[p..r], A[p..q], A[q+1..r]);
}

// 合并操作：临时数组TEMP与A大小相同，用游标ij分别比较两个子数组，小的先放入，对应所在数组的游标后移一位。
// 最后将临时数组中的数据拷贝至原数组
// merge伪代码
merge(A[p..r], A[p..q], A[q+1, ..r]){
    var i := p, j := q+1, k := 0; //初始化变量
    var tmp := new array[0, r-p]; //申请与A大小相同的数组
    while i<=q AND j<=r do {
        if A[i] <= A[j] {
            tmp[k++] = A[i++] //i++表示i:=i+1，先赋值后自增
        } else {
            tmp[k++] = A[j++]
        }
    }
    
    //判断出含有数据的剩余数组
    var start := i, end := q;
    //到这里，一定有一个数组中数据全部取完，另一个还存在
    if j<=r then start := j, end := r;
    
    // 将剩余的数组拷贝到tmp数组中
    while start <= end do {
        tmp[k++] = A[start++];
    }
    
    //将tmp拷贝回A[p..r]中
    for i :=0 to r-p do {
        // 要记得这里的A数组是某一次合并时 temp的拷贝写入,所以有p+i
        A[p+i] = tmp[i];
    }
}

//

快速排序

主要思想，选择分区点pivot，比pivot小的放在其左边。为了实现原地排序，选择比pivot小的放在左侧，数组元素交换顺序。

// 递推式
quick_sort(p..r) = quick(p ..q-1) +quick_sort(q+1..r);
//终止条件
p >= r;

//伪代码
quick_sort(A, n){
    quick_sort_c(A, 0, n-1);
}
quick_sort_c(A, p, r){
    if p >= r return;
    //分区点
    q = partition(A, p, r);
    quick_sort_c(A, p, q-1);
    quick_sort_c(A, q+1, r);
}

// 分区点函数，返回pivot应该所处的位置，并将A原地排序为：小,pivot,大
// 这里不搬移数组，而是采用交换，是不稳定算法
partition(A, p, r){
    pivot := A[r];
    i := p; //i表示pivot所处位置
    for j := p to r-1 do {
        if A[j] < pivot {
            swap A[i] with A[j]
            i := i+1;
        }
    }
    swap A[i] with A[r]
    return i
}

桶排序

计数排序

引言：根据年龄给100万用户排序

14排序优化

本节，以qsort()函数为例，介绍了实际情况下是如何设计一个通用、高性能排序的。

qsort()方法的实现结合了快排、归并排序等等；
例如，对小数据量的排序，使用归并排序；对大量数据，改为快排；
这意味着着实现一个算法，要求我了解不同算法的特性、空间时间复杂度等等，针对具体情况作切换/退化，毕竟合适的才是最好的。

例如，在上面的学习中了解到快排平均时间复杂度为 $O(n*logn)$ ，最坏的情况下(数据有序情况)退化到 $O(n^2)$ 。这是因为，快排每次的分区点pivot默认选择最后一位，以至于可能使每次前后分区大小失衡。

qsort()中的快排使用了“三数取中法”。也就是取前、中、后三个数的平均值作为每次的分区点，减少分区出现极端情况的可能性。

其二，递归太深有堆栈溢出的风险，可以自己手工实现堆上的栈。

其三，哨兵（类似于前面出现过的flag），辅助件事状态的变化，以简化代码实现、提高效率。

algorithm

算法-基础篇1

https://youdef.com/posts/36/

作者

阿成

发布于

2020年7月2日

许可协议

算法基础篇2 上一篇

基本算法回顾1 下一篇