【Princeton】算法(3):排序

排序(sort)是将一组对象按照某种逻辑顺序重新排列的过程,现实生活中我们经常需要对各种东西进行排序,在计算机上处理各种数据时也不例外。

这里介绍几种初级排序算法以及经典的归并排序、快速排序算法。

初级排序算法

排序规则

在计算机上编写程序解决各种问题时经常需要用到排序,而排序的对象多种多样,常见的有数字、字符串等,另外的一些自定义的类有时也要将它们的主键(key)按照某种方式进行排列。由此,就要有统一的方法,以方便地实现对多种不同的数据类型进行排序。

采用回调(callback)机制就能实现这么一种统一,在Java中这种机制是通过前面提到的接口实现的。排序需要通过大量的比较完成,而Java中有一个Comparable接口,各种不同的类只要实现该接口,重写其中的comperaTo方法后,对某两个该类元素v、w,就可以用v.compareTo(w)轻松实现它们的大小比较。如下面的Data类型所示:

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
public class Data implements Comparable<Data> {
private final int day;
private final int month;
private final int year;

public Data(int d, int m, int y) {
day = d;
month = m;
year = y;
}

public int day() {
return day;
}

public int month() {
return month;
}

public int year() {
return year;
}

public int compareTo(Data that) {
if (this.year > that.year) return +1;
if (this.year < that.year) return -1;
if (this.month > that.month) return +1;
if (this.month < that.month) return -1;
if (this.day > that.day) return +1;
if (this.day < that.day) return -1;
return 0;
}

public String toString() {
return month + "/" + day + "/" + year;
}
}

在compareTo方法中,习惯将用$+1$表示大于,$0$表示等于,$-1$则表示小于,且该方法需要实现如下全序(total order)关系:

  • 自反性(reflexive):$v = v$
  • 反对称性(antisymmetry):$v \le w$且$w \le v$,则$v = w$
  • 传递性(transitivity):$v \le w$且$w \le x$,则$v \le x$

在Java中,Comparable通常称为内比较器,而还存在一个更为灵活的外比较器Comparator,实现该接口后可以通过改写其中的compare方法,定义多种比较方式。

这里我们主要关注重新排列数组元素的算法。基本的排序过程都可以基于比较、移动元素这两种操作实现,因此在后面介绍的初级排序算法中,都会用到以下两个私有方法:

1
2
3
4
5
6
7
8
9
private static boolean less(Comparable v, Comparable w) {
return v.compareTo(w) < 0;
}

private static void exch(Comparable[] a, int i, int j) {
Comparable t = a[i];
a[i] = a[j];
a[j] = t;
}

也会用到以下私有方法判断是否完成排序:

1
2
3
4
5
6
private static boolean isSorted(Comparable[] a) {
for (int i = 1; i < a.length; i++)
if (less(a[i], a[i-1]))
return false;
return true;
}

在分析排序算法的运行效率以外,我们还需要注意排序算法的稳定性(Stability)。对多个关键字相同的记录,如果排序后这些记录的相对次序保持不变,则称该排序算法的是稳定的,否则是不稳定的。
稳定性的重要性

如上图所示,上表中已经按第一列中的首字母排好了顺序,如果需要继续按第二列的数字进行排序,选用了不稳定的排序算法将导致之前的顺序完全被打乱。

选择排序

一种最简单的排序算法是:找到数组中最小的元素后,将该元素与数组的第一个元素交换,接着在剩余的元素中找到最小值,与数组的第二个元素交换,如此往复,即可完成排序。这样一种算法,被称为选择排序(selection sort),如下图所示:
选择排序

该算法的具体实现为:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public calss Selection {
public static void sort(Comperable[] a) {
int N = a.length;
for (int i = 0; i < N; i++) {
int min = i;
for (int j = i + 1; j < N; j++)
if (less(a[j], a[min]))
min = j;
exch(a, i, min);
}
}

// less()、exch()、isSorted()方法见前面
}

分析以上过程可知,该算法的运行效率与数组中元素的初始顺序无关。对包含$N$个元素的数组,算法都要经过$(N - 1) + (N - 2) + \cdots + 1 + 0 = \frac{N(N-1)}{2} \sim \frac{N^2}{2}$次比较以及$N$次交换才能完成排序。

选择排序过程中,会打乱数组中相同元素的相对位置,因此该算法是不稳定的。

插入排序

另一种简单的算法–插入排序(insertion sort),则是从前往后,依次选中数组中的一个元素,通过比较将它插入到其他已有序的元素中的适当位置,插入时为了腾出空间,需要将原位置上及位置后的元素都右移一位,如下图所示:
插入排序

该算法的具体实现为:

1
2
3
4
5
6
7
8
9
10
11
12
13
public calss Insertion {
public static void sort(Comperable[] a) {
int N = a.length;
for (int i = 0; i < N; i++)
for (int j = i + 1; j > 0; j--)
if (less(a[j], a[j-1]))
exch(a, j, j-1);
else
break;
}

// less()、exch()、isSorted()方法见前面
}

与选择排序不同,该算法的运行效率与数组中元素的初始顺序有关。最坏情况下,初始为逆序,排序过程中需要进行$\frac{N(N - 1)}{2} \sim \frac{N^2}{2}$次比较和$\frac{N(N + 1)}{2} \sim \frac{N^2}{2}$次交换;最好情况下,初始已有序,排序过程只需要进行$N - 1$次比较而不需要交换。平均下来,该算法要进行$\sim \frac{N^2}{4}$次比较和交换才能完成排序。

对于部分有序的数组,插入排序的运行效率很高。所谓的部分有序,是指数组中倒置的数量小于等于数组大小$N$的某个倍数$c$,而倒置是指数组中两个元素的顺序时颠倒的。典型的部分有序数组有:

  • 数组中各元素距其最终位置都不太远
  • 一个有序的大数组后接一个小数组
  • 数组中只有个别元素位置不对

在插入排序中,从来不会将一个元素移动到与它相同的另一个元素的前面,因此该算法是稳定的。

希尔排序

希尔排序(shell sort)是一种基于插入排序的快速排序算法,其主要思想是使数组中任意间隔为$h$的元素都是有序的,从而变成$h$有序数组。$h$有序数组就是$h$个相互独立的数组编织在一起组成的数组,如下图中$h=4$时所示:
h有序数组

首先选定一个较大的$h$,之后不断缩小$h$,将数组变成$h$有序,到最后$h=1$时,进行的也就是一次插入排序,结束后整个数组也变成有序了,如下图所示:
希尔排序

其中$h$的缩小过程不是随意的,而要根据通过一个递增序列进行设定。该序列存在多种选择,这里使用Knuth的巨著中用到的序列$3x+1$。该算法的具体实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Shell {
public static void sort(Comparable[] a) {
int N = a.length;
int h = 1;
while (h < N/3)
h = 3*h + 1; // h = 1, 4, 13, 40, 121, ...

while (h >= 1) {
for (int i = h, i < N; i++)
for (int j = i; j >= h && less(a[j], a[j-h]); j -= h)
exch(a, j, j-h);
h = h/3;
}
}

// less()、exch()、isSorted()方法见前面
}

至今还没有描述关于希尔排序运行效率的精确模型,大量的实验证明使用递增序列为$3x+1$的希尔排序算法进行排序时,最坏情况下比较次数为$O(N^{\frac{3}{2}})$。该算法实现起来比较简单,且在中等大小的数组上它的运行效率还是不错的。

进行希尔排序时,也会打乱数组中相同元素的相对位置,因此它是不稳定的。

归并排序

前面讨论的都是些基础的排序算法,在现实中,应用最广的是两种经典的排序算法–归并排序(merge sort)快速排序(quick sort),这里先学习前者。

实现

归并排序的思想说起来十分简单:把数组中的元素平均分成两半,之后各半递归地进行排序,结束后将两半归并起来及完成了排序过程。这里用到了高效算法设计中经典的分治(divide-and-conquer)策略,其中的的阶段是将大问题分解为小问题进行递归求解,在则是将分的阶段得到的答案统一到一起。

归并排序中的归并过程,是将两个不同的有序的数组合并到第三个数组中,过程中需要对两个数组中的元素进行两两比较,以确定它们在第三个数组中的位置。下面实现了一种对一个数组中的两个有序的子数组进行原地归并的方法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static void merge(Comparable[] a, int lo, int mid, int hi) {
assert isSorted(a, lo, mid); // 判断是否有序
assert isSorted(a, mid + 1, hi);

int i = lo, j = mid + 1;

for (int k = lo; k <= hi; k++)
axu[k] = a[k];

for (int k = lo; k <= hi; k++)
if (i > mid)
a[k] = aux[j++];
else if (j > hi)
a[k] = aux[i++];
else if (less(aux[j], aux[i]))
a[k] = aux[j++]'
else
a[k] = aux[i++];
}

有了归并的方法后,归并排序的具体实现为:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Merge {
private static Comparable[] aux;

public static void sort(Comparable[] a) {
aux = new Comparable[a.length];
sort(a, 0, a.length - 1);
}

private static void sort(Comparable[] a, int lo, int hi) {
if (hi <= lo)
return;
int mid = lo + (hi - lo)/2;
sort(a, lo, mid); // 左半边
sort(a, mid + 1, hi); // 右半边
merge(a, lo, mid, hi); // 归并结果
}

// merge方法见上面
}

该算法的运行过程,如下图所示:
归并排序

对包含$N$个元素的数组,归并排序需要进行$\frac{N \log N}{2}$到$N \log N$次比较,至多访问数组$6N \log N$次。该算法存在的主要缺点,是其空间复杂度与$N$的大小成正比。

归并排序的稳定性取决于其中的merge方法,上面所示的merge方法在遇到相同的元素时,将保留它们原先的相对位置,因此是稳定的。

证明

归并排序时间复复杂度的证明过程如下:

用$C(N)$表示长度为$N$的数组排序时所需的比较次数,则对于上述归并排序算法,有:$$C(0) = C(1) = 0$$ $$C(\lceil \frac{N}{2}\rceil) + C(\lfloor \frac{N}{2} \rfloor) + \lfloor \frac{N}{2} \rfloor \le C(N)$$ $$C(N) \le C(\lceil \frac{N}{2}\rceil) + C(\lfloor \frac{N}{2} \rfloor) + N$$

其中$C(\lceil \frac{N}{2}\rceil)$、$C(\lfloor \frac{N}{2} \rfloor)$分别是前后两部分的比较次数,$\lfloor \frac{N}{2} \rfloor$、$N$则分别是归并时所需比较次数的下限和上限。当$N = 2^n$时:$$\lceil \frac{N}{2}\rceil = \lfloor \frac{N}{2} \rfloor = 2^{n-1}$$

上面第二个不等式在等号成立时,有:$$ C(2^n) = 2C(2^{n-1}) + 2^n$$ $$ \frac{C(2^n)}{2^n} = \frac{C(2^{n-1})}{2^{n-1}} + 1$$

用上面的等式替换上式中的右式,以此递推,可得:$$ \frac{C(2^n)}{2^n} = \frac{C(2^{n-2})}{2^{n-2}} + 1 + 1$$ $$ \vdots $$ $$ \frac{C(2^n)}{2^n} = \frac{C(2^0)}{2^0} + n$$

最后将$N = 2^n$回代,整理即得:$$C(N) = C(2^n) = n2^n = N\log N$$

除了利用上面的数学推导外,还可以通过下图所示的一棵归并依赖树证明该算法的复杂度:
依赖树

对$N$个元素进行归并排序,对将生成高度为$\log N$的依赖树,树中的每一层上,至多需要进行$N$次比较,访问数组$6N$次,因此整个排序过程至多比较$N\log N$次,访问数组$6N \log N$次。

更一般地,对于所有基于比较的排序算法,排序的过程都可以用一棵如下图所示的决策树(decision tree)来描述排序时的比较过程及结果:
决策树

对于$N$个不同元素,会有$N!$种不同的排列方式。而决策树的高度,代表了最坏情况下的比较次数,叶子结点的个数则代表了可能的排序结果的个数。一棵高度为$h$的二叉树至多包含$2^h$个叶子结点,由此有:$$2^h \ge N!$$

即:$$h \ge \log N! \sim N\log N$$

由此,任何基于比较的排序算法,在最坏情况下至少需要进行$N\log N$次比较,才能完成排序。而归并排序最坏情况下最多进行$N \log N$次比较就能完成排序,进一步也就说明它是基于比较的排序算法中,性能最优的算法。然而这种最优性能,是由所谓的“以空间换时间”而来的,该算法其复杂度并不是最优。

对于一些情况,上述的排序算法的性能下限会是不成立的,例如:

  • 数组中元素初始时已有一定顺序,排序时将不需要进行$N\log N$次比较
  • 数组中元素中包含重复项,排序也不需要进行$N\log N$次比较
  • 基数排序(radix sort)算法

改进

要进一步提高该算法的运行性能,可以用的方法有:设定一个CUTOFF值,使用插入排序来处理该算法中小规模的排序问题:

1
2
3
4
5
6
7
8
9
10
 private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi) {
if (hi <= lo + CUTOFF - 1) {
Insertion.sort(a, lo, hi);
return;
}
int mid = lo + (hi - lo)/2;
sort(a, lo, mid);
sort(a, mid + 1, hi);
merge(a, lo, mid, hi);
}

另外可以在sort操作后,先判断前半部分的最后一个元素是否小于后半部分的第一个元素,条件成立则不在进行merge操作:

1
2
3
4
5
6
7
8
9
10
private static void sort(Comparable[] a, int lo, int hi) {
if (hi <= lo)
return;
int mid = lo + (hi - lo)/2;
sort(a, lo, mid);
sort(a, mid + 1, hi);
if (!less(a[mid+1], a[mid]))
return;
merge(a, lo, mid, hi);
}

还可以取消merge方法中将数组a中的元素复制到数组aux的操作,更改为在aux数组中进行排序:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public static void merge(Comparable[] a, Comparable[] aux,int lo, int mid, int hi) {
int i = lo, j = mid + 1;

for (int k = lo; k <= hi; k++)
if (i > mid)
aux[k] = a[j++];
else if (j > hi)
aux[k] = a[i++];
else if (less(aux[j], aux[i]))
aux[k] = a[j++];
else
aux[k] = a[i++];
}

private static void sort(Comparable[] a, int lo, int hi) {
if (hi <= lo)
return;
int mid = lo + (hi - lo)/2;
sort(aux, lo, mid);
sort(aux, mid + 1, hi);
merge(a, aux, lo, mid, hi);
}

此外,还有一种不需要用到递归的自底向上的归并排序算法:

1
2
3
4
5
6
7
8
9
10
11
12
13
public class MergeBU {
private static Comparable[] aux;

public static void sort(Comparable[] a) {
int N = a.length;
aux = new Comparable[N];
for (int sz = 1; sz < N; sz = sz + sz)
for (int lo = 0; lo < N - sz; lo += sz+sz)
merge(a, lo, lo+dz-1, Math.min(lo+sz+sz-1, N-1));
}

// merge方法见前面
}

该算法的运行过程如下图所示:
自底向上归并

该算法与原归并排序算法的复杂度相同,只是排序的时比较和访问数组的次序不同。

快速排序

快速排序被誉为上个世纪最重要的算法之一,它的应用十分广泛。

实现

和归并排序相同,快速排序中也用到了分治策略,它将一个数组分成两个数组,分别进行排序。不同点在于,归并排序中直接将数组对半切分,而快速排序的关键就在于其切分数组的方法,另外归并排序中递归调用发生在处理整个数组之前,而快速排序则发生在处理完整个数组之后。

快速排序中对数组进行切分方法,是希望找到一个切分元素a[j],满足:

  • a[lo]到a[j-1]中所有的元素都不大于a[j]
  • a[j+1]到a[hi]中所有的元素都不小于a[j]

如此,以切分元素为界将数组分两部分,各部分递归地调用该切分方法,即可完成排序。

实现这么一种切分方法,一般的策略是直接选择a[lo]作为我们的切分元素,之后从a[lo]的左边开始向右扫描数组找到一个大于等于它的元素a[i],再从数组右边开始向左扫描数组找到一个小于等于它的数组a[j],交换a[i]和a[j]的位置,如此继续向左、向右扫描,交换位置,就可以保证i指针左侧的元素都小于a[lo],j指针右侧的元素都大于a[lo]。

直到两个指针i和j相遇后,将a[lo]交换到a[j],原来的a[lo]也就成为了我们想要的切分元素a[j]。如下图所示:
切分

切分方法的具体实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
private partition(Comparable[] a, int lo, int hi) {
int i = lo, j = hi + 1;

while (true) {
while (less(a[++i], a[lo])) // 左向右扫描
if (i == hi)
break;
while (less(a[lo], a[--j])) // 右向左扫描
if (j == lo)
break;
if (i >= j) // 是否相遇
break;
exch(a, i, j);
}

exch(a, lo, j);
return j;
}

有了切分方法,实现快速排序只要将它递归调用,具体为:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Quick {
public static sort(Comparable[] a) {
StadRandom.shuffle(a);
sort(a, 0, a.length-1);
}

private static void sort(Comparable[] a, int lo, int hi) {
if (hi <= lo)
return;
int j = partition(a, lo, hi); // 切分
sort(a, lo, j-1); // 递归排序
sort(a, j+1, hi);
}
}

整个算法的执行过程,如下图所示:
快速排序

为了保证算法的性能,快速排序前进行shuffle操作,即将数组中元素的顺序完全打乱,是十分有必要的。因为该算法的最坏情况,便是数组中的元素初始已有序,这会导致切分不均匀而使得算法最多需要进行$\frac{N^2}{2}$次比较。

在最好情况下,该算法只需要比较$N\log N$次,且是在原地进行,不需要用额外的空间,这使得它优于归并排序。平均下来,将长度为N的无重复数组排序,快速排序算法需要进行$\sim 2N\ln N$次比较。

快速排序将打乱数组中相同元素的原来的相对位置,是不稳定的排序算法。

值得一提的是,在StdRandom中,shuffle方法使用交换实现的:

1
2
3
4
5
6
7
8
9
public class StdRandom {
public static void shuffle(Object[] a) {
int N = a.length;
for (int i = 0; i < N; i++) {
int r = StdRandom.uniform(i + 1); // 生成一个随机数
exch(a, i, r);
}
}
}

证明

要证明上面所述的快速排序的时间复杂度,用$C_N$表示长度为$N$的数组排序时平均所需的比较次数,则有:$$C(0) = C(1) = 0$$

当$N \ge 2$时,有:$$C_N = (N + 1) + (\frac{C_0 + C_{N - 1}}{N}) + (\frac{C_1 + C_{N - 2}}{N}) + \cdots + (\frac{C_{N - 1} + C_0}{N})$$

其中的$(N + 1)$是切分时的比较次数,切分的方法有$N$种,后面的项是切分后进行递归时的平均比较次数。将上式两边同乘$N$,有:$$NC_N = N(N + 1) + 2(C_0 + C_1 + \cdots + C_{N - 1})$$

上式减去$N - 1$时的相同等式,有:$$NC_N - (N - 1)C_{N - 1} = 2N + 2C_{N - 1}$$

两边同除以$N(N + 1)$:$$\frac{C_N}{N + 1} = \frac{2}{N + 1} + \frac{C_{N - 1}}{N}$$

归纳推导得:$$C_N = (N+1)(\frac{2}{3} + \frac{2}{4} + \cdots + \frac{2}{N+1})$$ $$ \sim 2(N+1) \int^{N + 1}_3 \frac{1}{x} \sim 2N\ln N$$

改进

要进一步改进快速排序算法,与归并排序一样,也可以设定一个CUTOFF值,用插入排序来处理该算法中小规模的排序问题:

1
2
3
4
5
6
7
8
9
 private static void sort(Comparable[] a,int lo, int hi) {
if (hi <= lo + CUTOFF - 1) {
Insertion.sort(a, lo, hi);
return;
}
int j = partition(a, lo, hi);
sort(a, lo, j-1);
sort(a, j+1, hi);
}

另一种方法是进行三取样切分,在数组中取三个元素作为样本,选择其中的中位数作为切分元素:

1
2
3
4
5
6
7
8
9
10
11
 private static void sort(Comparable[] a,int lo, int hi) {
if (hi <= lo)
return;

int m = medianOf3(a, lo, lo + (hi - lo)/2, hi);
swap(a, lo, m);

int j = partition(a, lo, hi);
sort(a, lo, j-1);
sort(a, j+1, hi);
}

数组中存在的相同元素会对影响快速排序的性能。在在前面的介绍的切分方法,我们的设定算法在遇到某个元素与切分元素相同时则停止的目的,就是为了防止当数组中所有的元素都相同时,排序陷入最坏情况。要消除相同元素的影响,还可以考虑进行三向切分

三向切分时,维护一个指针lt使得a[lo]到a[lt-1]都小于切分元素v,一个指针gt使得a[gt+1]到a[hi]都大于v,一个指针i使得a[lt]到a[i-1]都等于v。具体实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
private static void sort(Comparable[] a, int lo, int hi) {
if (hi <= lo)
return;

int lt = lo, gt = hi;
Comparable v = a[lo];
int i = lo;

while (i <= gt) {
int cmp = a[i].comparaTo(v);
if (cmp < 0)
exch(a, lt++, i++);
else if (cmp > 0)
exch(a, i, gt--);
else
i++;
}

sort(a, lo, lt-1);
sort(a, gt+1, hi);
}

使用三向切分进行排序的过程如下图所示:
三向切分排序

对于包含大量重复元素的数组,三向切分后将排序的时间从线性对数级别降低到了线性级别,同时该算法也是信息量最优的。

最后,总结一下这里学习过的所有排序算法:
排序算法总结

应用

凸包

凸包(Convex Hull)是计算机图形学中的概念,它指的是对于二维平面由$N$个点组成的集合中,由最外层的点连接起来所构成的凸多边形,所有的点将被包含在该多边形内。

给定一个点集,要用程序求解出它的凸包,一种简单有效的方法是Graham Scan算法。该算法的步骤为:

  1. 选取二维平面上的点集中$y$轴坐标最小的点作为起始点p;
  2. 将其他点按照它们与p之间的极角(polar angle)大小进行排序,极角相同的情况下比较与极点的距离,离极点比较近的优先;
  3. 将p点与排序后的第一个点连接后,尝试依次将后面的点连接起来;
  4. 如果连接某个点后,连接走向发生(如逆时针变成顺时针)变化,则抛弃之前连接的点,直到形成凸包。

其中的可以选择归并排序算法对点进行排序,执行这些步骤的过程如下图所示:
Graham Scan

连接的走向是否发生变化,好比判断从点a到b再到c是顺时针还是逆时针方向,可以用三个点形成的两个向量的叉乘结果来判断:
CCW

顺序统计量

在包含$N$个元素的数组中第$K$小的元素,就称为该数组的第$K$个顺序统计量。快速排序中的切分方法,可以用来查找某个顺序统计量:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static Comparable select(Comparable[] a, int k) {
StdRandom.shuffle(a);
int lo = 0, hi = a.length - 1;
while (hi > lo) {
int j = partition(a, lo, hi);
if (j < k)
lo = j + 1;
else if (j > k)
hi = j - 1;
else
return a[k];
}
return a[k];
}

该算法平均复杂度是线性的,因此能较为高效地找到某个顺序统计量。

编程作业:模式识别

描述

分析

实现

参考资料

  1. Algorithms-Coursera
  2. 算法(第四版)
  3. JAVA回调机制(CallBack)详解-博客园
  4. Java中Comparable和Comparator区别小结-博客园
  5. Graham Scan凸包算法-CSDN

注:本文涉及的图片及资料均整理翻译自Robert Sedgewick的Algorithms课程以及配套教材《算法(第四版)》,版权归其所有。翻译整理水平有限,如有不妥的地方欢迎指出。


更新历史:

  • 2019.03.31 完成初稿
文章作者: Hugsy
文章链接: http://binweber.top/2019/03/23/algs_3/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Sky Inside the Eyewall
支付宝打赏~
微信打赏~