排序算法复习，插入排序，选择排序，冒泡排序，希尔排序，[[归并排序]]，堆排序，快排。

关于排序算法的 stable 稳定性，排序保存原始数据顺序则稳定，否则不稳定。

关于原址排序，算法需要额外的空间计算或者保存数据， in-place sorting ，归并排序为非原址排序 not-in-place sorting。

关于时间复杂度，归并排序，堆排序，快排有相对较快的速度 O(n*log(n))

稳定性

排序前后两个相等的数的相对位置不变。

有一些排序算法天然是稳定的，比如 Insertion Sort, Merge Sort, Bubble Sort。

为什么需要有稳定性？

加入有一组英文名，包括 First Name 和 Last Name，要求先按照 Last Name(姓) 排序，然后按照 First Name （名） 排序，这个时候可以先排序 First Name (稳定或非稳定)，然后按照稳定的排序算法排序 Last Name，这样就可以保证排序完成之后，就是最终的结果。

插入排序

每次取一个元素插入正确的位置，适合少量元素。对于未排序的数据，从已排序的序列中从后向前扫描，找到相应的位置插入，实现上通常使用 in-place 排序，只需要使用额外 O(1) 空间，但是因为插入正确的位置之后，需要反复移动已经排序的序列，为新元素提供插入空间，因而比较费时。

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

1. 从第一个元素开始，该元素可以认为已经被排序
2. 取出下一个元素，在已经排序的元素序列中从后向前扫描
3. 如果该元素（已排序）大于新元素，将该元素移到下一位置
4. 重复步骤 3，直到找到已排序的元素小于或者等于新元素的位置
5. 将新元素插入到该位置后
6. 重复步骤 2~5

Algorithm

for i = 2:n,
    for (k = i; k > 1 and a[k] < a[k-1]; k--)
        swap a[k,k-1]
    → invariant: a[1..i] is sorted
end

Java 版本：

static void insert_sort(int[] array) {
    for(int i = 1; i < array.length; ++i) {
        int cur = array[i];
        for(int j = i - 1; j >= 0 && array[j] > cur; j--) {
            array[j + 1] = array[j];
            array[j] = cur;
        }
    }
}

Properties

• Stable
• O(1) extra space
• O(n^2^) comparisons and swaps
• Adaptive: O(n) time when nearly sorted
• Very low overhead

Example

list = [4,6,2,5,1,3,0,4,8,1,5,3,6]

# 升序
# 从第二个元素开始，每次循环将前 i 个元素排序
for i in range(1,len(list)):
    value = list[i]
    j = i-1
    # 将第 i 个元素的位置腾出
    while j >= 0 and list[j]>value:
        list[j+1] = list[j]
        j=j-1
    # 在排完序的 list[0...i] 中将值插入合适位置
    list[j+1]=value

# 降序
list = [4,6,2,5,1,3,0,4,8,1,5,3,6]

for i in range(len(list)-1, -1, -1):
    value = list[i]
    j=i+1
    while j<len(list) and value < list[j]:
        list[j-1] = list[j]
        j=j+1
    list[j-1]=value

print(list)

选择排序

每次选取数组中最小（或者最大）的元素，并将其与未排序数组中首元素交换，依次进行。

选择排序拥有最小的交换次数，适合交换元素开销比较大的情况。选择排序其他情况都比较低效。

Algorithm

for i = 1:n,
    k = i
    for j = i+1:n, if a[j] < a[k], k = j
    → invariant: a[k] smallest of a[i..n]
    swap a[i,k]
    → invariant: a[1..i] in final position
end

Properties

• Not stable
• O(1) extra space
• Θ(n^2^) comparisons
• Θ(n) swaps
• Not adaptive

Example

list = [4,6,2,5,1,3,0,4,8,1,5,3,6]

for i in range(0,len(list)):
    k = i
    for k in range(i+1, len(list)):
    # 没有完全按照定义写，不过这样交换的开销更大。
        if list[k] < list[i]:
            list[i], list[k] = list[k], list[i]

print(list)

Java 版：

static void selection_sort(int[] array) {
	if(array.length <= 1) return;
	for(int i = 0; i < array.length; i++) {
		int smallest = i;
		for(int j = i + 1; j < array.length; j++) {
			if (array[j] < array[smallest]) {
				smallest = j;
			}
		}
		int temp = array[i];
		array[i] = array[smallest];
		array[smallest] = temp;
	}
}

冒泡排序

[[冒泡排序]] 反复交换相邻未按次序排列的元素，一次循环之后最大的元素到数组最后。

Algorithm

for i = 1:n,
    swapped = false
    for j = n:i+1,
        if a[j] < a[j-1],
            swap a[j,j-1]
            swapped = true
    → invariant: a[1..i] in final position
    break if not swapped
end

Properties

• Stable
• O(1) extra space
• O(n^2^) comparisons and swaps
• Adaptive: O(n) when nearly sorted

Example

def bubble_sort_1(list):
    for i in range(0, len(list)):
        for j in range(1, len(list)-i):
            if list[j-1] > list[j]:
                list[j-1], list[j] = list[j], list[j-1]

def bubble_sort_2(list):
    for i in range(0, len(list)):
        swap = False
        for j in range(len(list)-1, i, -1):
            if list[j-1] > list[j]:
                list[j-1], list[j] = list[j], list[j-1]
                swap = True
        if swap is False:
            break

相较于第一种直接冒泡，设定标志优化冒泡。

Java 版

static void bubble_sort(int[] arr) {
	int i, j, temp, len = arr.length;
	for (i = 0; i < len - 1; i++)
		for (j = 0; j < len - 1 - i; j++)
			if (arr[j] > arr[j + 1]) {
				temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
			}
}

希尔排序

分组插入排序，将数组拆分成若干子序列，由增量决定，分别进行直接插入排序，然后缩减增量，减少子序列，最后对全体元素进行插入排序。插入排序在基本有序的情况下效率最高。

Algorithm

h = 1
while h < n, h = 3*h + 1
while h > 0,
    h = h / 3
    for k = 1:h, insertion sort a[k:h:n]
    → invariant: each h-sub-array is sorted
end

Properties

• Not stable
• O(1) extra space
• O(n^3/2^) time as shown (see below)
• Adaptive: O(n·lg(n)) time when nearly sorted

Example

list = [4,6,2,5,1,3,0,4,8,1,5,3,6]

def insertion_sort(k,h,n):
    """
    :param k: group count
    :param h: step length
    :param n: total
    :return:
    """
    for i in range(k+h, n, h):
        value = list[i]
        j = i-h
        while j >= 0 and list[j]>value:
            list[j+h] = list[j]
            j=j-h
        list[j+h]=value


h = 1       # step length
while h < len(list):
    h = 3*h +1

while h > 0:
    h = int(h / 3)
    for k in range(0, h):           # devide into k groups
        insertion_sort(k, h, len(list))

print(list)

归并排序

[[归并排序]] 是一个典型的分治算法，将数组分成两个子数组，在子数组中继续拆分，当小组只有一个数据时可认为有序，之后合并，所以重点就到了合并有序数组。

Algorithm

# split in half
m = n / 2

# recursive sorts
sort a[1..m]
sort a[m+1..n]

# merge sorted sub-arrays using temp array
b = copy of a[1..m]
i = 1, j = m+1, k = 1
while i <= m and j <= n,
    a[k++] = (a[j] < b[i]) ? a[j++] : b[i++]
    → invariant: a[1..k] in final position
while i <= m,
    a[k++] = b[i++]
    → invariant: a[1..k] in final position

Properties

• Stable
• Θ(n) extra space for arrays (as shown)
• Θ(lg(n)) extra space for linked lists
• Θ(n·lg(n)) time
• Not adaptive
• Does not require random access to data

Example

From wiki

from collections import deque

def merge_sort(lst):
    if len(lst) <= 1:
        return lst

    def merge(left, right):
        merged,left,right = deque(),deque(left),deque(right)
        while left and right:
            merged.append(left.popleft() if left[0] <= right[0] else right.popleft())  # deque popleft is also O(1)
        merged.extend(right if right else left)
        return list(merged)

    middle = int(len(lst) // 2)
    left = merge_sort(lst[:middle])
    right = merge_sort(lst[middle:])
    return merge(left, right)

堆排序

利用最大堆的性质，堆性质，子结点的值小于父节点的值。每次将根节点最大值取出，剩下元素进行最大堆调整，依次进行。

Algorithm

# heapify
for i = n/2:1, sink(a,i,n)
→ invariant: a[1,n] in heap order

# sortdown
for i = 1:n,
    swap a[1,n-i+1]
    sink(a,1,n-i)
    → invariant: a[n-i+1,n] in final position
end

# sink from i in a[1..n]
function sink(a,i,n):
    # {lc,rc,mc} = {left,right,max} child index
    lc = 2*i
    if lc > n, return # no children
    rc = lc + 1
    mc = (rc > n) ? lc : (a[lc] > a[rc]) ? lc : rc
    if a[i] >= a[mc], return # heap ordered
    swap a[i,mc]
    sink(a,mc,n)

Properties

• Not stable
• O(1) extra space (see discussion)
• O(n·lg(n)) time
• Not really adaptive

Example

def max_heapify(lst, i):
    """
    下标为 i 的根节点调整为最大堆
    :param lst:
    :param i:
    :return:
    """
    l = 2 * i + 1
    r = 2 * (i + 1)
    if l < len(lst) and lst[l] > lst[i]:
        largest = l
    else:
        largest = i
    if r < len(lst) and lst[r] > lst[largest]:
        largest = r
    if largest != i:
        lst[i], lst[largest] = lst[largest], lst[i]
        max_heapify(lst, largest)


def build_max_heap(lst):
	"""
    建立最大堆
    """
    for i in range((len(lst)-1)/2, 0, -1):
        max_heapify(lst, i)


def heap_sort(lst):
    build_max_heap(lst)
    ret = []
    for i in range(len(lst)-1, -1, -1):
        ret.append(lst[0])
        lst.remove(lst[0])
        max_heapify(lst, 0)
    return ret

L = [16, 4, 10, 14, 7, 9, 3, 2, 8, 1]
R = heap_sort(L)
print(R)

快排

从数列中挑出元素，将比挑出元素小的摆放到前面，大的放到后面，分区操作。然后递归地将小于挑出值的子数列和大于的子数列排序。

Algorithm

# choose pivot
swap a[1,rand(1,n)]

# 2-way partition
k = 1
for i = 2:n, if a[i] < a[1], swap a[++k,i]
swap a[1,k]
→ invariant: a[1..k-1] < a[k] <= a[k+1..n]

# recursive sorts
sort a[1..k-1]
sort a[k+1,n]

Properties

• Not stable
• O(lg(n)) extra space (see discussion)
• O(n^2^) time, but typically O(n·lg(n)) time
• Not adaptive

Example

list_demo = [2,8,7,1,3,5,6,4]

def partition(lst, p, r):
    """
    划分
    :param lst: 待排序数组
    :param p: 起始下标，子数组第一个元素
    :param r: 终止下标，子数组最后一个元素 r < len(lst)
    :return: 划分结果下标
    """
    if r >= len(lst) or p < 0:
        return
    x = lst[r]
    i = p - 1
    for j in range(p, r):
        if lst[j] <= x:
            i += 1
            lst[i], lst[j] = lst[j], lst[i]
    lst[i+1], lst[r] = lst[r], lst[i+1]
    return i + 1


def quick_sort(lst, p, r):
    if p < r:
        q = partition(lst, p, r)
        quick_sort(lst, p, q-1)
        quick_sort(lst, q+1, r)

quick_sort(list_demo, 0, len(list_demo)-1)
print(list_demo)

分配排序

箱排序

箱排序也称桶排序 (Bucket Sort)，其基本思想是：设置若干个箱子，依次扫描待排序的记录 R[0]，R[1]，…，R[n-1]，把关键字等于 k 的记录全都装入到第 k 个箱子里（分配），然后按序号依次将各非空的箱子首尾连接起来（收集）。对于有限取值范围的数组来说非常有效，时间复杂度可以可达 O(n). 例如给人年龄排序，人的年龄只能在 0~100 多之间，不可能有人超过 200, 适用桶排序。

• 箱排序中，箱子的个数取决于关键字的取值范围。 若 R[0..n-1] 中关键字的取值范围是 0 到 m-1 的整数，则必须设置 m 个箱子。因此箱排序要求关键字的类型是有限类型，否则可能要无限个箱子。

• 箱子的类型应设计成链表为宜 一般情况下每个箱子中存放多少个关键字相同的记录是无法预料的，故箱子的类型应设计成链表为宜。

• 为保证排序是稳定的，分配过程中装箱及收集过程中的连接必须按先进先出原则进行。

桶排序的平均时间复杂度是线性的，O(n), 但是最坏的情况可能是 O(n^2)

基数排序

基数排序是非比较排序算法，算法的时间复杂度是 O(n). 相比于快速排序的 O(nlgn), 从表面上看具有不小的优势。但事实上可能有些出入，因为基数排序的 n 可能具有比较大的系数 K. 因此在具体的应用中，应首先对这个排序函数的效率进行评估。

基数排序的主要思路是，将所有待比较数值（注意，必须是正整数）统一为同样的数位长度，数位较短的数前面补零. 然后，从最低位开始，依次进行一次稳定排序。这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列。

这个算法的难度在于分离数位，将分离出的数位代表原元素的代表，用作计数排序。但是分离数位不能脱离原来的数字，计数排序的结果，还是要移动原元素。

注意计数排序的元素数值与位置的联系，引申到基数排序的从元素得到中间值然后与位置的联系。

枚举排序

通常也被叫做秩排序 (Rank Sort) ，算法基本思想是：对每一个要排序的元素，统计小于它的所有元素的个数，从而得到该元素在整个序列中的位置，时间复杂度为 O（n^2）

reference

• http://www.sorting-algorithms.com/
• http://www.tutorialspoint.com/data_structures_algorithms/sorting_algorithms.htm
• http://blog.csdn.net/morewindows/article/details/17488865
• 分配排序
• 基数排序

最近配置路由器 pdnsd，经常需要调试 DNS 信息，就离不开调试工具了。 nslookup 用来查询 DNS 记录，查看域名解析是否正常，经常被用来在网络故障时诊断网络问题。

命令

在 Ubuntu 下可以使用如下命令安装：

sudo apt install dnsutils

格式：

   nslookup [-option] [name | -] [server]

使用

nslookup 是一个查询 Internet domain name server 的工具，nslookup 有两种模式：

• interactive 交互模式
• non-interactive 非交互模式

交互模式

进入交互模式，总共有两种方法。

第一种方法，直接输入 nslookup 命令，不加任何参数，则直接进入交互模式，此时 nslookup 会连接到默认的域名服务器（即 /etc/resolv.conf 的第一个 dns 地址）。

第二种方法，是支持选定不同域名服务器的。需要设置第一个参数为“-”，然后第二个参数是设置要连接的域名服务器主机名或 IP 地址。

如果你直接在 nslookup 命令后加上所要查询的 IP 或主机名，那么就进入了非交互模式。当然，这个时候你也可以在第二个参数位置设置所要连接的域名服务器。

例子

交互模式下查询域名

nslookup
> www.douban.com
Server:	127.0.1.1   // 连接的 DNS 服务器
Address:	127.0.1.1#53    // DNS 服务器 IP 地址与端口

Non-authoritative answer:    // 非权威答案，从连接的 DNS 服务器本地缓存中读取，非实际查询得到
Name:	www.douban.com
Address: 115.182.201.6    // IP 地址
Name:	www.douban.com
Address: 115.182.201.7
Name:	www.douban.com
Address: 115.182.201.8

交互模式下更改 DNS

进入交互模式之后，使用 server dns-server 来改变上连 DNS 服务器地址

查询域名 IP 地址

nslookup www.douban.com [dns-server]

如果没有指定 dns-server，使用系统默认的 DNS 服务器。

本来打算去的自然博物馆，可无奈去官网看的时候已经没有预订票，于是就去了中国美术馆。北京来了快6年而似乎该去的博物馆都尚未能去，想接下来的时间里能不能用自己的脚都走遍，用自己的眼睛都看遍。借用网友的一句话，“不能也不敢说自己懂艺术，只是单纯的喜欢，喜欢美，喜欢不同的表达，喜欢安静的可以欣赏思想与灵感的地方”。上一次画画还要追溯到初中，近十年时间没有接触任何艺术，也没有接受任何艺术形式的熏陶。在最初进入的时候确实是一头雾水，幸而我们这一次去的时候正好是中华民族大团结全国美术作品展，至少还有一个主题让我们可以想象。虽然进门看到如此主旋律的主题有点失望，然而从一个展厅进到另一个展厅，除了进门见到的习大大有点恶心之外，渐渐就开始敬佩起这些画家。

喜欢画画的人可以经常上美术馆的官网看看，不定期的会举办一些展览。

下面是三幅震撼到我的画：

这原本是一副很大的画，这里的两位只是画的一小部分，记得画的左边还有一位在回眸，右边也还有两位。

远看真的像是一副照片，细节部分也是栩栩如生，近看脸部的文理，光影的处理着实让我震惊了。

被萌到的小狗，哈士奇？不认识。

其他令我印象深刻的画作：

塔吉克新娘 官网

美术馆馆藏作品链接

很遗憾，写这篇文章的时候中途忘记保存了，漏掉了一些内容，现在凭感觉补了一些，却再也找不到当时的感觉，虽然只仅仅相隔一天。由此可见随时保存的重要性了。

Question 6

Method overriding is key to the concept of Polymorphism. 覆盖是多态的核心 True

多态可以概括成“一个接口，多个方法”，运行时决定调用函数。C++ 多态利用虚函数实现，虚函数允许子类重新定义方法，子类重新定义方法的做法称为“覆盖”，或者重写。（直接覆盖成员函数和覆盖虚函数，只有重写了虚函数的才能算作是体现了C++ 多态性）

封装可以使得代码模块化，继承可以扩展已存在的代码，而多态的目的则是为了接口重用。也就是说，不论传递过来的究竟是那个类的对象，函数都能够通过同一个接口调用到适应各自对象的实现方法。

最常见的用法就是声明基类的指针，利用该指针指向任意一个子类对象，调用相应的虚函数，可以根据指向的子类的不同而实现不同的方法。如果没有使用虚函数的话，即没有利用C++多态性，则利用基类指针调用相应的函数的时候，将总被限制在基类函数本身，而无法调用到子类中被重写过的函数。因为没有多态性，函数调用的地址将是一定的，而固定的地址将始终调用到同一个函数，这就无法实现一个接口，多种方法的目的了。

#include <iostream>  
using namespace std;  

class A  
{  
public:  
    void foo()  
    {  
        printf("1\n");  
    }  
    virtual void fun()  
    {  
        printf("2\n");  
    }  
};  
class B : public A  
{  
public:  
    void foo()  
    {  
        printf("3\n");  
    }  
    void fun()  
    {  
        printf("4\n");  
    }  
};  
int main(void)  
{  
    A a;  
    B b;  
    A *p = &a;  
    p->foo();  
    p->fun();  
    p = &b;  
    p->foo();  
    p->fun();  
    return 0;  
}  

输出
1 2
1 4

基类指针指向基类对象，调用基类函数；基类指针指向子类对象， p->foo() 指针是个基类指针，指向是一个固定偏移量的函数，因此此时指向的就只能是基类的foo()函数的代码了，因此输出的结果还是1。而p->fun() 指针是基类指针，指向的fun是一个虚函数，由于每个虚函数都有一个虚函数列表，此时p调用fun()并不是直接调用函数，而是通过虚函数列表找到相应的函数的地址，因此根据指向的对象不同，函数地址也将不同，这里将找到对应的子类的fun()函数的地址，因此输出的结果也会是子类的结果4。

上面例子，还有一种问法

B *ptr = (B *)&a;  ptr->foo();  ptr->fun();

输出
3 2

从原理上来解释，由于B是子类指针，虽然被赋予了基类对象地址，但是ptr->foo()在调用的时候，由于地址偏移量固定，偏移量是子类对象的偏移量，于是即使在指向了一个基类对象的情况下，还是调用到了子类的函数，虽然可能从始到终都没有子类对象的实例化出现。而ptr->fun()的调用，可能还是因为C++多态性的原因，由于指向的是一个基类对象，通过虚函数列表的引用，找到了基类中fun()函数的地址，因此调用了基类的函数。由此可见多态性的强大，可以适应各种变化，不论指针是基类的还是子类的，都能找到正确的实现方法。

“隐藏”是指派生类的函数屏蔽了与其同名的基类函数，规则如下： （1）如果派生类的函数与基类的函数同名，但是参数不同。此时，不论有无virtual 关键字，基类的函数将被隐藏（注意别与重载混淆）。 （2）如果派生类的函数与基类的函数同名，并且参数也相同，但是基类函数没有virtual 关键字。此时，基类的函数被隐藏（注意别与覆盖混淆）。

纯虚函数，virtual ReturnType Function()= 0;

C++支持两种多态性：编译时多态性，运行时多态性。

• 编译时多态性：通过重载函数实现
• 运行时多态性：通过虚函数实现。

虚函数是在基类中被声明为virtual，并在派生类中重新定义的成员函数，可实现成员函数的动态覆盖（Override） 包含纯虚函数的类称为抽象类。由于抽象类包含了没有定义的纯虚函数，所以不能定义抽象类的对象。

Q16

Which objected oriented design concept is key to the factory design pattern?

Inheritance

Q23

Which of the following describe the C++ programming language?

Compiled Declarative

Q25

The friend keyword is used to grant access to private class members. True

1. 友元函数：普通函数对一个访问某个类中的私有或保护成员。
2. 友元类：类A中的成员函数访问类B中的私有或保护成员。

友元函数

friend <类型><友元函数名>(<参数表>);  

友元函数只是一个普通函数，并不是该类的类成员函数，它可以在任何地方调用，友元函数中通过对象名来访问该类的私有或保护成员

#include <iostream>
using namespace std;

class Base{
public:
    Base(int _data):data(_data){};

    friend int getData(Base& _base);
private:
    int data;
};

int getData(Base& _base){
    return _base.data;
}

int main() {
    Base b(2);
    std::cout << getData(b) << endl;
    return 0;
}

友元类

friend class <友元类名>;

友元类的声明在该类的声明中，而实现在该类外。

#include <iostream>
using namespace std;

class Base{
public:
    Base(int _data):data(_data){};

    friend class FClass;
private:
    int data;
};

class FClass{
public:
    int getData(Base _base){
        return _base.data;		// call friend class private data
    }
};

int main() {
    Base b(2);
    FClass c;
    cout << c.getData(b) << endl;
    return 0;
}

Q38

Choose word or words to describe UML language.

• Picture
• Relational
• Interpreted
• Abstract
• None of the answers are correct.

只有 Picture 正确

The Unified Modeling Language (UML) is a general-purpose, developmental, modeling language in the field of software engineering, that is intended to provide a standard way to visualize the design of a system.

为啥没有 Relation 有点神奇～ UML 图能够看出类与类的关系的啊

Q40

Generalization is used by UML to describe Inheritance and the deriving of one class from another.

Generaliztion 是从属关系，可以表示继承，或者派生

http://www.uml-diagrams.org/generalization.html

Q44

#include <iostream>

void f0(int& sum){
    sum = 3+2*7;
}

int main() {
    int *p, sum = 0;
    (*p)++;
    sum = sum * 3;
    f0(sum);
    std::cout << sum << ",";
    return 0;
}

(*p)++ 一行有问题

具体问题内容请看这里

Linux 内核是开源类 Unix 系统宏内核。仅仅一个内核并不是一套完整的操作系统。有一套基于 Linux 内核的完整操作系统叫作 Linux 操作系统。Kernel 是 Linux 系统的核心，主要负责硬件的支持。

Linux 内核提供了安全补丁， bugfix 和新特性。

Linux 内核在 GNU 通用公共许可证第 2 版之下发布。

Linux 的 Kernel 主要提供以下五个基本的功能 ¹：

• 硬件管理以及硬件的抽象
• 进程和线程的管理，以及之间的通信
• 内存的管理，包括虚拟内存管理以及内存空间的包含
• I/O 设备，包括文件系统，网络接口，串行接口 (Serial interfaces) 等等
• 设备基本功能，包括开启启动，关闭，计时器，多任务管理等等

修改启动内核版本需要谨慎，每一步在确认知道自己在做什么的情况下再操作。Linux 内核版本变更可能导致网络访问异常，声音异常，甚至是桌面环境无法启动。在安装和移除内核时，确保已经已经阅读过相关帮助，确保自己知道如何选择不同版本的内核，如何恢复之前的版本，以及如何检查 DKMS 状态。

Linux 内核版本号的意义

Linux 内核版本号由 3 组数字组成：第一个组数字。第二组数字。第三组数字

• 第一个组数字：目前发布的内核主版本。
• 第二个组数字：偶数表示稳定版本；奇数表示开发中版本。
• 第三个组数字：错误修补的次数。

查看内核版本

在 Linux 机器上执行如下命令查看当前正在使用的内核版本

uname -r

使用如下命令查看当前系统安装的内核版本

dpkg -l | grep linux-image

如果使用的是 Linux Mint 那么在 Update Manager 中，选择 View -> Linux Kernels 可以查看当前安装的版本和正在使用的版本，或者选择安装新的版本切换。

安装和卸载内核版本

sudo apt search linux-image
sudo apt install xxx
sudo apt-get purge xxx

选择内核版本

一个系统可以同时安装多个内核，但是运行时只能选择一个，当启动电脑时，在显示 GRUB 菜单时可以选择加载哪一个内核。（当只有一个系统安装时，GRUB 菜单可能被跳过，强制显示 GRUB 菜单可以在启动电脑时一直按住 Shift 按键）

在 Advanced options 选项中，可以选择系统上安装的内核版本，在启动时选择一个即可。

DKMS

DKMS 全称是 Dynamic Kernel Module Support，它可以帮我们维护内核外的这些驱动程序，在内核版本变动之后可以自动重新生成新的模块。

sudo apt-get install dkms

内核包含了所有的开源驱动，一般都可以正常工作，私有的驱动（DVIDIA，AMD，Broadcom… 等等）不包含在其中。这些私有驱动（proprietary drivers）需要在安装时手动编译到每一个内核中。这个操作可以用 dkms 来完成。如果私有驱动无法正常编译到内核中，可能导致启动异常，所以需要提前检查

dkms status

reference

• https://en.wikipedia.org/wiki/Linux_kernel

adb and fastboot

从 Android 开发官网下载 Android SDK，从事过 Android 开发的应该知道 adb 和 fastboot 工具，在完整 SDK 中这两个工具在 platform-tools 文件夹下。如果想要方便的使用这两个工具，可以将文件路径加入到系统环境变量中，这样以后就可以在任何目录使用 adb 和 fastboot 命令。

flash factory image

救砖，或者在 recovery 下没有备份又无法开机的情况下只能刷回原厂镜像救砖机。因此折腾需谨慎，刷机前请一定使用 recovery 备份系统及数据。可以从 Google 官网下载镜像。

下载镜像

https://developers.google.com/android/nexus/images#shamu

解压之后应该会有如下文件

bootloader-shamu-moto-apq8084-71.15.img  2016/01/06  07:19        10,636,288
flash-all.bat                            2016/01/06  07:19               985
flash-all.sh                             2016/01/06  07:19               856
flash-base.sh                            2016/01/06  07:19               814
image-shamu-mmb29q.zip                   2016/01/06  07:19     1,009,825,337
radio-shamu-d4.01-9625-05.32+fsg-9625-02.109.img      2016/01/06  07:19       118,272,512

解锁bootloader

解锁 bootloader 会抹去手机一切内容，需谨慎，总之只需要一句命令

 fastboot oem unlock

然后利用音量键及电源键来确认解锁 bootloader, 之后运行

 fastboot reboot

重启手机。

刷镜像

1. 关机并进入 fastboot 也就是 bootloader模式，在关机状态下，同时按住“电源键”+“音量下”
2. 数据线连接手机与电脑，在驱动安装正确之后
3. 执行 flash-all.bat (Windows 下） 或者 flash-all.sh （MAC或者 Linux 下）
4. 等待执行完毕，手机恢复成出厂镜像

root

root 工具及教程来自 @Chainfire ，在此由衷的感谢他。

• 下载ZIP工具
• 解压文件，并将手机进入 bootloader/fastboot 模式
• 连接数据线，并运行 root-windows.bat （Windows 下）或者 chmod +x root-linux.sh 并运行 root-linux.sh （Linux下） Mac下同Linux

Recovery

第三方的 Recovery 有以下的功能：

• Wipe your phone’s data (Factory reset) and cache
• Make, restore and manage backups of your phone’s operating system and software
• Mount, unmount and format your phone’s internal as well as external storage partitions
• Install a custom ROM or application from a zip file to your phone
• Wipe Dalvik cache and battery statistics
• Make logs for error reporting and debugging

刷入 recovery

• 从官网 下载 Nexus 6 TWRP 的 recovery 文件
• 进入 bootloader/fastboot 模式

• 执行以下命令

  fastboot flash recovery recovery.img

  recovery.img 即下载的 Recovery 镜像。

• 利用音量键选择 recovery ，点击电源键选择，可以进入 “Recovery Mode”.

安装完 recovery 之后就能够快速的备份系统，恢复出厂设置，恢复备份数据，刷入新ROM，刷入ZIP

kernel

一张图解释什么是 kernel

Nexus 6 第三方的 kernel 有很多选择 比如 franco.kernel，这里推荐 ElementalX，有如下功能

• Easy installation and setup with Aroma installer
• overclock/underclock CPU
• user voltage control
• Advance color control
• MultiROM support
• optional USB fastcharge
• optional sweep2wake and doubletap2wake
• optional sweep2sleep
• sound control
• init.d support
• NTFS r/w and exFAT support
• option to disable fsync
• adjustable vibration
• does not force encryption

安装 ElementalX kernel

• 从ElementalX 官网下载，并保存到手机
• 进入 Recovery Mode
• 刷入 ZIP ，选择下载的文件，安装

Nexus 6 破解电信3G/4G

6.0.1 (MMB29Q) 有效

下载文件，教程中需要用的软件及文件 https://yunpan.cn/cxCaHyqkKPwg9 提取码 db02

• DFS
• QPST

还有这里

• moto x qc diag interface - 64bit.zip
• carrier_policy.xml

具体步骤参考nexus6破解电信教程

简单来说破解4G步骤：

• 用QPTS工具里面的EFS Explorer, 添加/policyman/carrier_policy.xml,nexus6 默认没有这个文件
• 进入BP TOOLS模式,安装好后，必须确认好你的设备管理器 端口（COM和LPT）中BP驱动的端口号
• 从开始菜单中，打开QPST configuration
• 先点Ports标签,然后点Add New Prot 输入你的设备端口号
• 点StartClient菜单中的EFS Explorer选项
• 连接上手机后,在EFS 根目录创建policyman目录
• 把carrier_policy.xml(见附件)拖进policyman目录中
• 完成后重启手机

破解完成后请在手机拨号面板那输入 *#*#4636#*#* 看下首选网络是不是LTE/GSM/CDMA auto(prl)

参考

• http://forum.xda-developers.com/nexus-6/general/guide-flash-factory-images-nexus-6shamu-t2954008
• http://forum.xda-developers.com/showpost.php?p=56938530&postcount=1
• http://bbs.gfan.com/android-7828699-1-1.html
• http://m.anruan.com/view_7100.html
• http://bbs.gfan.com/forum.php?mod=viewthread&tid=7795111
• http://bbs.gfan.com/android-8085647-1-1.html

部分内容为 《Linux 命令速查手册》读书记录。

系统

uname -a               # 查看内核 / 操作系统 /CPU 信息
head -n 1 /etc/issue   # 查看操作系统版本
cat /proc/cpuinfo      # 查看 CPU 信息
hostname               # 查看计算机名
lspci -tv              # 列出所有 PCI 设备
lsusb -tv              # 列出所有 USB 设备
lsmod                  # 列出加载的内核模块
env                    # 查看环境变量

资源

监视系统资源，包括跟踪正在运行的程序 （ps，top）终止进程（kill），列出打开的文件（lsof），报告系统内存占用（free），磁盘空间占用（df，du）等等。

ps aux                  # 查看系统正在运行的进程
ps -ef                  # 查看所有进程
ps f                    # 查看进程树
top                     # 实时显示进程状态
kill -9 PID             # 终止正在运行的进程 -9 强制中断， -15 正常中止
lsof                    # 列出打开的文件
free -m                 # 查看内存使用量和交换区使用量
df -h                   # 查看各分区使用情况
du -sh 《目录名》        # 查看指定目录的大小
grep MemTotal /proc/meminfo   # 查看内存总量
grep MemFree /proc/meminfo    # 查看空闲内存量
uptime                  # 查看系统运行时间、用户数、负载
cat /proc/loadavg       # 查看系统负载

磁盘和分区

mount | column -t      # 查看挂接的分区状态
fdisk -l               # 查看所有分区
swapon -s              # 查看所有交换分区
hdparm -i /dev/hda     # 查看磁盘参数（仅适用于 IDE 设备）
dmesg | grep IDE       # 查看启动时 IDE 设备检测状况

网络

这里列举了常用和网络相关的命令，包括查看本地 IP（ifconfig），判断网络连通性（ping，traceroute) 等等。其中 ifconfig, iwconfig ，route 等等命令都有双重用途，不仅能够查看网络连接属性，也能够进行配置。

ifconfig               # 查看所有网络接口的属性
ifup eth0              # 开启网络
ifdown eth0            # 关闭 eth0 网卡
iwconfig               # 查看无线接口属性
iptables -L            # 查看防火墙设置
ping                   # 网络连通性
route -n               # 查看路由表
netstat -lntp          # 查看所有监听端口
netstat -antp          # 查看所有已经建立的连接
netstat -s             # 查看网络统计信息
traceroute https://google.com  # 显示数据包从计算机路由到指定的主机经过的每一步
mtr                    # traceroute 更好的代替
host                   # 查看网站 DNS 结果
dhclient -r eth0       # 使用 DHCP 获得新网络地址

mtr 使用介绍

用户

w                      # 查看活动用户
id 《用户名》            # 查看指定用户信息
last                   # 查看用户登录日志
cut -d: -f1 /etc/passwd   # 查看系统所有用户
cut -d: -f1 /etc/group    # 查看系统所有组
crontab -l             # 查看当前用户的计划任务

服务

chkconfig --list       # 列出所有系统服务
chkconfig --list | grep on    # 列出所有启动的系统服务

wc 命令是 Linux 下 Word Count 的缩写，用来统计文件中的字节数，字数，行数等等。

命令格式

非常简单

    wc [options] files

选项

-c, --bytes 统计字节数
-l, --lines 统计行数
-m, --chars 统计字符数，不能和 -c 一起使用
-w 统计字数，一个字定义为由空白、空格或者换行分割的字串
-L, --max-line-length 最长行的长度

例子

查看文件字节数、字数、行数

命令：wc file.txt

比如有如下文件：

cat file.txt  
Linux
Debian
Ubuntu
Linux Mint

命令有如下结果

wc file.txt
 4  5 31 file.txt

wc -l file.txt
4 file.txt

wc -c file.txt
31 file.txt

wc -w file.txt
5 file.txt

wc -m file.txt
31 file.txt

wc -L file.txt
10 file.txt

直接使用命令 wc file.txt 输出的内容对应

wc file.txt 
4       5          31         file.txt
行数 单词数 字节数 文件名

不打印文件名

使用管道命令或者重定向来避免命令打印文件名

wc 命令如果从管道命令或者重定向命令中接受输入，则不产生文件名输出，参考如下例子：

当 wc 接受文件名作为参数时，打印出文件名

wc -l /etc/passwd
41 /etc/passwd 

当文件以管道形式或者标准输入时不打印文件名

cat /etc/passwd | wc -l 
41 

unusual redirection, but wc still ignores the filename 

< /etc/passwd wc -l
41 

typical redirection, taking standard input from a file 

wc -l < /etc/passwd
41

由此可以看到，当文件被当成 wc 的参数传递过去的时候会打印出文件名，而其他标准输入时候不会打印出文件名。某些情况下，你可能希望打印文件名，因此有必要知道何时会打印文件名，而何时不会打印。

MultiTail是一个开源的ncurses的实用工具，可用于在一个窗口或单一外壳，显示实时一样的尾巴命令，该命令拆分控制台为更多子窗口的日志文件的最后几行（很像显示多个日志文件到标准输出屏幕命令 ）。 它还支持颜色突出显示，过滤，添加和删除窗口等。

他和tail的区别就是他会在控制台中打开多个窗口，这样可以同时监控多个日志。

安装

apt install multitail

如果要在 CentOS，基于 Red Hat 的发行版中使用，需要开启 EPEL repository，然后安装

yum install -y multitail

使用

监控两个日志文件，窗口上下

multitail /var/log/syslog /var/log/auth.log

如果要让窗口左右排布

multitail -s 2 /var/log/syslog /var/log/auth.log

同理，-s num 来表示后接多少个文件

进入 multitail 之后，有一些交互式命令

• h 来打开帮助
• 使用 b 来选择打开的文件，使用上下键选择文件，一旦选择文件 multitail 会显示文件最后 100 行，使用 jk 移动光标，或者 gg/G 来快速移动到文件顶部或者最后，q 退出
• a 用来添加另外的监控日志文件

reference

• https://www.tecmint.com/view-multiple-files-in-linux/

Cache 在实际场景中有着非常广泛的使用，通常情况下如果遇到需要大量时间计算或者获取值的场景，就应当将值保存到缓存中。Cache 和 ConcurrentMap 类似，但又不尽相同。最大的不同是 ConcurrentMap 会永久的存储所有的元素值直到他们被显示的移除，但是 Cache 会为了保持内存使用合理，而配置自动将一些值移除。

通常情况下，Guava caching 适用于以下场景：

• 花费一些内存来换取速度
• 一些 key 会被不止一次被调用
• 缓存内容有限，不会超过内存空间的值，Guava caches 不会存储内容到文件或者到服务器外部，如果有此类需求考虑使用 Memcached, Redis 等类似工具

先来看一下 Guava 中 Cache 接口的定义：

com.google.common.cache.Cache
com.google.common.cache.Cache#asMap
com.google.common.cache.Cache#cleanUp
com.google.common.cache.Cache#get
com.google.common.cache.Cache#getAllPresent
com.google.common.cache.Cache#getIfPresent
com.google.common.cache.Cache#invalidate
com.google.common.cache.Cache#invalidateAll()
com.google.common.cache.Cache#invalidateAll(java.lang.Iterable<?>)
com.google.common.cache.Cache#put
com.google.common.cache.Cache#putAll
com.google.common.cache.Cache#size
com.google.common.cache.Cache#stats

Cache 接口定义的方法大都一目了然，值得一说的就是 stats() 方法，这个方法会返回一个 CacheStats 对象，这个对象包括了该 Cache 的一些统计信息，包括 hitCount， missCount，loadSuccessCount，loadExceptionCount，totalLoadTime 和 evictionCount。

Cache 通过 CacheBuilder 类的 Builder 模式获取，常见的用法：

LoadingCache<Key, Graph> graphs = CacheBuilder.newBuilder()
       .maximumSize(1000)
       .expireAfterWrite(10, TimeUnit.MINUTES)
       .removalListener(MY_LISTENER)
       .build(
           new CacheLoader<Key, Graph>() {
             public Graph load(Key key) throws AnyException {
               return createExpensiveGraph(key);
             }
           });

如果使用的场景中对应着 key 的值有默认的值，那么可以选择使用 CacheLoader，如果没有默认值，那么仍然可以原子的 get-if-absent-compute 方法，在 get 方法中提供一个 Callable，或者元素也可以通过 Cache.put 来直接插入到缓存中。

LoadingCache

LoadingCache 是一个附加着 CacheLoader 的 Cache。LoadingCache<K,V> 在 Guava 中是一个 interface，通常是用来本地 Cache 缓存 k-v 数据，value 会一直保存在内存中直到被移除或者失效。实现这个接口的类期望是线程安全的，能够安全的在多线程程序中被访问。

当第一次调用 get() 方法时，如果 value 不存在则会触发 load() 方法，load 方法不能返回 null，否则会报错。

LoadingCache 不能 Cache null

LoadingCache 是不支持缓存 null 值的，如果 load 回调方法返回 null，则在 get 的时候会抛出异常。

如果在 CacheLoader 中抛出异常，那么 Cache 会认为没有完成，所以新的值不会被 Cache。基于这一条规则，那么如何避免在 CacheLoader 中因为缓存 null 而抛出异常，那就是编程者自己处理 null 异常。

get() vs getUnchecked()

最正统的查询 LoadingCache 的方法是调用 get(k) 方法，这个方法如果查询到已经缓存的值会立即返回，否则使用缓存的 CacheLoader 自动加载一个新值到缓存并返回。因为 CacheLoader 可能会抛出异常，那么如果有异常，则LoadingCache.get(k) 会抛出 ExecutionException 异常。而如果 CacheLoader 抛出 unchecked 未检查的异常，则 get(k) 方法会抛出 UncheckedExecutionException 异常。

此时可以选择使用 getUnchecked(k) 方法，这个方法会将所有的异常包装在 UncheckedExecutionException 异常中。需要注意的是，如果 CacheLoader 声明了检查异常，也就是 CacheLoader 显式的定义了异常，就不能调用 getUnchecked(k) 方法

定时回收

CacheBuilder 在构建 Cache 时提供了两种定时回收的方法

• expireAfterAccess(long, TimeUnit) : 缓存项在给定时间内没有被读或写访问，则回收
• expireAfterWrite(long, TimeUnit)：缓存项在给定时间内没有被写访问（创建或覆盖），则回收

失效

调用 LoadingCache 的 invalidate 方法可以使得 key 失效

reference

• https://github.com/google/guava/wiki/CachesExplained