1.直接插入排序
（1）总体思路：（排升序）：
arr[end]比tmp小，就已经是升序的了，本次不需要调整，直接end+1进入下一环；arr[end]比tmp大，说明不是升序，则让arr[end+1]=arr[end],同时end--,让end与tmp循环比较，直至arr[end]<tmp为止，如果此时end已经变为负数，说明end所指的数据是目前来说最大的，此时直接arr[end+1]=tmp
（2）代码实现：
这是.h文件
#include<stdio.h>
//直接插入排序
void insertsort(int* arr, int n);这是sort.c文件
#include"sort.h"
//直接插入排序
void insertsort(int* arr, int n)
{
for (int i = 0; i < n-1; i++) //n为有效元素个数
{
int end = i;
int tmp = arr[end + 1];
while (end >= 0)
{
if (arr[end] > tmp)
{
arr[end + 1] = arr[end];
end--;
}
else
{
break;
}
}
arr[end + 1] = tmp;
}
}这是test.c文件
#include"sort.h"
void printarr(int* arr, int n)
{
for (int i = 0; i < n; i++)
{
printf("%d", arr[i]);
}
printf("\n");
}
void sorttest()
{
int arr[] = { 5,3,9,6,2,4,7,1,8 };
int n = sizeof(arr) / sizeof(arr[0]);
printf("排序之前：");
printarr(arr, n);
insertsort(arr, n);
printf("排序之后：");
printarr(arr, n);
}
int main()
{
sorttest();
return 0;
}运行结果：
细心的朋友不难发现，该算法的时间复杂度为O(N^2),当数组有序且为降序时。为此，为了降低时间复杂度，我们需要将其改进一下。
2.希尔排序
（1）基本思路：（升序）跟直接插入排序基本原理一样，只不过是将待排序数组分成了若干份进行排序，这若干份的排序是同时进行的，只不过可能有些“时延”
（2）代码实现：
这是.h文件
#include<stdio.h>
//希尔排序
void shellsort(int* a, int n);这是sort.c文件
#include"sort.h"
//希尔排序
void shellsort(int* arr, int n)
{
int gap = n;
while (gap > 1) //此处gap不能设为gap>=1,否则会死循环
{
gap = gap / 3 + 1; //要保证最后一次gap一定为1
for (int i = 0; i < n - gap; i++) //要保证最后一组的end不出界
{
int end = i;
int tmp = arr[end + gap];
while (end >= 0)
{
if (arr[end] > tmp)
{
arr[end + gap] = arr[end];
end -= gap;
}
else
{
break;
}
}
arr[end + gap] = tmp;
}
}
}
这是test.c文件
#include"sort.h"
void printarr(int* arr, int n)
{
for (int i = 0; i < n; i++)
{
printf("%d", arr[i]);
}
printf("\n");
}
void sorttest()
{
int arr[] = { 5,3,9,6,2,4,7,1,8 };
int n = sizeof(arr) / sizeof(arr[0]);
printf("排序之前：");
printarr(arr, n);
shellsort(arr, n);
printf("排序之后：");
printarr(arr, n);
}
int main()
{
sorttest();
return 0;
}运行结果：
3.堆排序
（1）基本思想：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列。[时间复杂度O(nlogn)]
（2）代码实现
这是.h文件
#include<stdio.h>
//堆排序
void heapsort(int* arr, int n);
这是sort.c文件
void swap(int* x, int* y)
{
int tmp = *x;
*x = *y;
*y = tmp;
}
//向下调整算法
void adjustdown(int* arr, int parent, int n) //这里我们建的是大堆
{
int child = parent * 2 + 1;
while (child < n)
{
if (child + 1 < n && arr[child] < arr[child + 1])
{
child++;
}
if (arr[child] > arr[parent])
{
swap(&arr[child], &arr[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
//堆排序
//排升序，建大堆，排降序，建小堆
//堆排序的基本思想是将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列。
void heapsort(int* arr, int n)
{
//根据给定的arr来进行建堆
//child:n-1 parent:(n-1-1)/2
//向下调整算法建堆
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
{
adjustdown(arr, i, n); //这里的建堆是将数组按大堆给堆起来
}
int end = n - 1;
while (end > 0)
{
swap(&arr[0], &arr[end]);
adjustdown(arr, 0, end);
end--;
}
}这是test.c文件
#include"sort.h"
void printarr(int* arr, int n)
{
for (int i = 0; i < n; i++)
{
printf("%d", arr[i]);
}
printf("\n");
}
void sorttest()
{
int arr[] = { 5,3,9,6,2,4,7,1,8 };
int n = sizeof(arr) / sizeof(arr[0]);
printf("排序之前：");
printarr(arr, n);
heapsort(arr, n);
printf("排序之后：");
printarr(arr, n);
}
int main()
{
sorttest();
return 0;
}运行结果：
4.冒泡排序
（1）基本思想：从首元素开始，进行两两比较，根据大小交换位置，直到最后将最大（小）的数据元素交换到了队尾，从而成为有序序列的一部分；重复这个过程，直到所有数据元素都排好序。
（2）代码实现
这是.h文件
#include<stdio.h>
//冒泡排序
void bubblesort(int* arr, int n);这是sort.c文件
#include"sort.h"
void swap(int* x, int* y)
{
int tmp = *x;
*x = *y;
*y = tmp;
}
//冒泡排序
void bubblesort(int* arr, int n)
{
for (int i = 0; i < n; i++)
{
int exchange = 0;
for (int j = 0; j < n - i - 1; j++)
{
if (arr[j] > arr[j + 1])
{
exchange = 1;
swap(&arr[j], &arr[j + 1]);
}
}
if (exchange == 0)
{
break;
}
}
}这是test.c文件
#include"sort.h"
void printarr(int* arr, int n)
{
for (int i = 0; i < n; i++)
{
printf("%d", arr[i]);
}
printf("\n");
}
void sorttest()
{
int arr[] = { 5,3,9,6,2,4,7,1,8 };
int n = sizeof(arr) / sizeof(arr[0]);
printf("排序之前：");
printarr(arr, n);
bubblesort(arr, n);
printf("排序之后：");
printarr(arr, n);
}
int main()
{
sorttest();
return 0;
}运行结果：
5.直接选择排序
（1）基本思想：
可以简单记为：两端夹击，左边放最小值，右边放最大值，之后“缩小包围圈”，重复该过程。
每次过程中默认begin位置上的值为maxi和mini，之后通过遍历调整，确定本次循环的最大值和最小值后，将begin和mini位置上的数据交换，end和maxi位置上的数据交换,，完成缩小包围圈的操作。值得注意的是，当maxi和begin在同一位置上时，我们的第一个交换操作会使真正的maxi“跑掉”，故此，我们只需让maxi=mini,使其发生第一次交换后maxi仍然是最大数的下标，此时在交换maxi和end即可(守株待兔），(注：若排降序就倒过来，将begin与maxi位置的数据互换，end与mini位置的数据互换,也是让小的先走，若maxi==end,则让maxi=mini(这里或者排完升序在将数组反转一下也可以)）
（2）代码实现
这是.h文件
#include<stdio.h>
//直接选择排序
void selectsort(int* arr, int n);这是sort.c文件
#include"sort.h"
void swap(int* x, int* y)
{
int tmp = *x;
*x = *y;
*y = tmp;
}
//直接选择排序
//可以简单记为：两端夹击，左边放最小值，右边放最大值，之后“缩小包围圈”，重复该过程
//每次过程中默认begin位置上的值为maxi和mini，之后通过遍历调整，确定本次循环的最大值和最小值后，将begin和mini位置上的数据交换，end和maxi位置上的数据交换,(若排降序就倒过来，将begin与maxi位置的数据互换，end与mini位置的数据互换,也是让小的先走，若maxi==end,则让maxi=mini(这里或者排完升序在将数组反转一下也可以)），完成缩小包围圈的操作。值得注意的是，当maxi和begin在同一位置上时，我们的第一个交换操作会使真正的maxi“跑掉”，故此，我们只需让maxi=mini,使其发生第一次交换后maxi仍然是最大数的下标，此时在交换maxi和end即可(守株待兔）
//交换次序不要改变！
void selectsort(int* arr, int n)
{
int begin = 0, end = n - 1;
while (begin < end)
{
int mini = begin, maxi = begin;
for (int i = begin + 1; i <= end; i++)
{
if (arr[i] > arr[maxi])
{
maxi = i;
}
if (arr[i] < arr[mini])
{
mini = i;
}
}
if (maxi == begin)
{
maxi = mini;
}
swap(&arr[mini], &arr[begin]);
swap(&arr[maxi], &arr[end]);
begin++;
end--;
}
}这是test.c文件
#include"sort.h"
void printarr(int* arr, int n)
{
for (int i = 0; i < n; i++)
{
printf("%d", arr[i]);
}
printf("\n");
}
void sorttest()
{
int arr[] = { 5,3,9,6,2,4,7,1,8 };
int n = sizeof(arr) / sizeof(arr[0]);
printf("排序之前：");
printarr(arr, n);
selectsort(arr, n);
printf("排序之后：");
printarr(arr, n);
}
int main()
{
sorttest();
return 0;
}运行结果：
6.快速排序(hoare版）
(1)总体思路：找基准值：right从右往左找比基准值小的数据，left从左往右找比基准值大的数据，找到之后，left和right交换；当left>right时，将keyi和right交换（此时right一定是比keyi值要小）
这是.h文件
//快速排序
void quicksort(int* arr, int left, int right);这是sort.c文件
#include"sort.h"
void swap(int* x, int* y)
{
int tmp = *x;
*x = *y;
*y = tmp;
}
int _quicksort(int* arr, int left, int right)
{
int keyi = left;
++left; //默认第一个元素为keyi,后面的为left
while (left <= right)
{
//right：从右往左找比基准值要小的数据
while (left <= right && arr[right] > arr[keyi])
{
right--;
}
//left:从左向右找比基准值大的数据
while (left <= right && arr[left] < arr[keyi])
{
left++;
}
//left和right交换
if (left <= right)
{
swap(&arr[left], &arr[right]);
}
}
//keyi和rght交换
swap(&arr[keyi], &arr[right]);
return right;
}
//快速排序
void quicksort(int* arr, int left, int right)
{
if (left >= right)
{
return;
}
//找基准值
int keyi = _quicksort(arr, left, right);
//二分
//[left,keyi-1] keyi [keyi+1,right]
//[0,2][4,5]
quicksort(arr, left, keyi - 1);
quicksort(arr, keyi + 1, right);这是test.c文件
#include"sort.h"
void printarr(int* arr, int n)
{
for (int i = 0; i < n; i++)
{
printf("%d", arr[i]);
}
printf("\n");
}
void sorttest()
{
int arr[] = { 5,3,9,6,2,4,7,1,8 };
int n = sizeof(arr) / sizeof(arr[0]);
printf("排序之前：");
printarr(arr, n);
quicksort(arr, 0, n-1);
printf("排序之后：");
printarr(arr, n);
}
int main()
{
sorttest();
return 0;
}运行结果：
7.快速排序（挖坑法版）
（1）基本思路：
每次循环都默认以第一个元素作为关键值以及坑位置，之后还是右找比基准值小的，找到后就用这个值填一开始默认设的坑，（注意填完之后别忘了改变一下新坑的位置），同理，左找比基准值大的数，填坑，如此循环下去，直到左大于等于右时，跳出循环，让关键值把最后一个坑填上
（2）代码实现：
这是.h文件
//快速排序
void quicksort(int* arr, int left, int right);这是sort.c文件
int _quicksort1(int* arr, int left, int right)
{
int hole = left;
int key = arr[hole];
while (left < right)
{
while (left<right && arr[right]>key)
{
right--;
}
arr[hole] = arr[right];
hole = right; //right位置的数据往前面填坑后，这个位置变成了一个坑
while (left < right && arr[left] < key)
{
left++;
}
arr[hole] = arr[left];
hole = left;
}
arr[hole] = key;
return hole;
}
//快速排序
void quicksort(int* arr, int left, int right)
{
if (left >= right)
{
return;
}
//找基准值
int keyi = _quicksort1(arr, left, right);
//二分
//[left,keyi-1] keyi [keyi+1,right]
//[0,2][4,5]
quicksort(arr, left, keyi - 1);
quicksort(arr, keyi + 1, right);
}这是test.c文件
#include"sort.h"
void printarr(int* arr, int n)
{
for (int i = 0; i < n; i++)
{
printf("%d", arr[i]);
}
printf("\n");
}
void sorttest()
{
int arr[] = { 5,3,9,6,2,4,7,1,8 };
int n = sizeof(arr) / sizeof(arr[0]);
printf("排序之前：");
printarr(arr, n);
quicksort(arr, 0, n-1);
printf("排序之后：");
printarr(arr, n);
}
int main()
{
sorttest();
return 0;
}运行结果：
8.快速排序（洛门托双指针法）
（1）基本思路：
定义两个指针，cur和prev，cur用于探路，找比基准值要小的数据，当cur指向的数据不比基准值小时，++cur ；当cur指向的数据比基准值小时，++prev，prev和cur数据交换，++cur
（2）代码实现：
这是.h文件
//快速排序
void quicksort(int* arr, int left, int right);这是sort.c文件
#include"sort.h"
void swap(int* x, int* y)
{
int tmp = *x;
*x = *y;
*y = tmp;
}
int _quicksort2(int* arr, int left, int right)
{
int prev = left, cur = prev + 1;
int keyi = left;
while (cur <= right)
{
if (arr[cur] < arr[keyi] && ++prev != cur) //后面的条件是避免无意义的交换
{
swap(&arr[cur], &arr[prev]);
}
++cur;
}
swap(&arr[prev], &arr[keyi]);
return prev;
}
//快速排序
void quicksort(int* arr, int left, int right)
{
if (left >= right)
{
return;
}
//找基准值
int keyi = _quicksort2(arr, left, right);
//二分
//[left,keyi-1] keyi [keyi+1,right]
//[0,2][4,5]
quicksort(arr, left, keyi - 1);
quicksort(arr, keyi + 1, right);
}这是test.c文件
#include"sort.h"
void printarr(int* arr, int n)
{
for (int i = 0; i < n; i++)
{
printf("%d", arr[i]);
}
printf("\n");
}
void sorttest()
{
int arr[] = { 5,3,9,6,2,4,7,1,8 };
int n = sizeof(arr) / sizeof(arr[0]);
printf("排序之前：");
printarr(arr, n);
quicksort(arr, 0, n-1);
printf("排序之后：");
printarr(arr, n);
}
int main()
{
sorttest();
return 0;
}运行结果：
9.快速排序（非递归版）
（1）基本思路：
借助栈结构，让待排序列的左和右依次入栈，（即确定了此次操作的区间），之后在栈不为空的情况下，连续取两次栈顶，赋给begin和end变量，之后用双指针法确定关键值的位置，并将原序列裂解为两个子序列，重复上一操作，直至序列的左右下标不可被再细分,完成排序
（2）代码实现：
这是.h文件
#include<stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
//快速排序--无递归版
void quicksortnoner(int* arr, int left, int right);这是sort.c文件
#include"sort.h"
#include"stack.h"
void swap(int* x, int* y)
{
int tmp = *x;
*x = *y;
*y = tmp;
}
void quicksortnoner(int* arr, int left, int right)
{
//基本思路：借助栈结构，让待排序列的左和右依次入栈，（即确定了此次操作的区间，之后在栈不为空的情况下，连续取两次栈顶，赋给begin和end变量，之后用双指针法确定关键值的位置，并将原序列裂解为两个子序列，重复上一操作，直至序列的左右下标不可被再细分
st st;
stinit(&st);
stackpush(&st, right);//[l r]
stackpush(&st, left);// r l
while (!stackempty(&st))
{
//取栈顶元素两次
int begin = stacktop(&st);
stackpop(&st);
int end = stacktop(&st);
stackpop(&st);
//对区间[begin,end]找基准值---双指针法
int prev = begin, cur = prev + 1;
int keyi = begin;
while (cur < end)
{
if (arr[cur] < arr[keyi] && ++prev != cur) //cur比基准值小时，先++prev，如果++后的prev与cur指向的不是同一个数据，就交换
{
swap(&arr[prev], &arr[cur]);
}
++cur;
}
swap(&arr[keyi], &arr[prev]);
keyi = prev;
//此时基准值的下标：keyi
//划分左右序列:[begin,keyi-1] [keyi+1,end]
if (keyi + 1 < end) //让右序列入栈
{
stackpush(&st, end);
stackpush(&st, keyi + 1);
}
if (keyi - 1 > begin) //这里写错了，让左序列入栈
{
stackpush(&st, keyi - 1);
stackpush(&st, begin);
}
}
stackdestroy(&st);
}这是test.c文件
#include"sort.h"
#include<time.h>
#include<stdlib.h>
void printarr(int* arr, int n)
{
for (int i = 0; i < n; i++)
{
printf("%d", arr[i]);
}
printf("\n");
}
void sorttest()
{
int arr[] = { 5,3,9,6,2,4,7,1,8 };
int n = sizeof(arr) / sizeof(arr[0]);
printf("排序之前：");
printarr(arr, n);
quicksortnoner(arr, 0, n-1);
printf("排序之后：");
printarr(arr, n);
}
int main()
{
sorttest();
return 0;
}运行结果：
10.归并排序
（1）基本思路：
反复的使用函数递归，将待排序数组不断地裂解，直至成为单一的元素，之后在通过比较的方法将各个数据按照顺序排序好
（2）代码实现：
这是.h文件
#include<stdio.h>
#include <stdlib.h>
#include <time.h>
//归并排序
void mergesort(int* arr, int n);这是sort.c文件
#include"sort.h"
void _mergesort(int* arr, int left, int right, int* tmp)
{
if (left >= right)
{
return;
}
int mid = (left + right) / 2;
//根据mid划分为两个序列:[left,mid] [mid+1,right]
_mergesort(arr, left, mid, tmp);
_mergesort(arr, mid + 1, right, tmp);
//合并[left,mid] [mid+1,right]
int begin1 = left, end1 = mid;
int begin2 = mid + 1, end2 = right;
int index = begin1;
while (begin1 <= end1 && begin2 <= end2)
{
if (arr[begin1] < arr[begin2])
{
tmp[index++] = arr[begin1++];
}
else
{
tmp[index++] = arr[begin2++];
}
}
//可能存在第一个序列中的数据没有全部放到tmp中
//可能存在第二个序列中的数据没有全部放到tmp中
while (begin1 <= end1)
{
tmp[index++] = arr[begin1++];
}
while (begin2 <= end2)
{
tmp[index++] = arr[begin2++];
}
//将tmp中数据挪回到arr中
for (int i = left; i <= right; i++)
{
arr[i] = tmp[i];
}
}
void mergesort(int* arr, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
_mergesort(arr, 0, n - 1, tmp);
free(tmp);
}这是test.c文件
#include"sort.h"
#include<time.h>
#include<stdlib.h>
void printarr(int* arr, int n)
{
for (int i = 0; i < n; i++)
{
printf("%d", arr[i]);
}
printf("\n");
}
void sorttest()
{
int arr[] = { 5,3,9,6,2,4,7,1,8 };
int n = sizeof(arr) / sizeof(arr[0]);
printf("排序之前：");
printarr(arr, n);
mergesort(arr, n);
printf("排序之后：");
printarr(arr, n);
}
int main()
{
sorttest();
return 0;
}运行结果：
11.计数排序
（1）基本思路：该排序方式采用“映射”思想，为了避免造成空间的浪费，我们要求出计数数组的下标范围，故此我们遍历待排序数组，找出最大值和最小值，之后malloc一个计数数组用于统计各个数字的出现顺序，统计完成后，将数据按照顺序还原回去，完成排序操作。
（2）代码实现：
这是.h文件
#include<stdio.h>
#include <stdlib.h>
#include <time.h>
//计数排序
void CountSort(int* arr, int n);这是sort.c文件
#include"sort.h"
//计数排序
void CountSort(int* arr, int n)
{
int min = arr[0], max = arr[0];
for (int i = 0; i < n; i++)
{
if (arr[i] < min)
{
min = arr[i];
}
if (arr[i] > max)
{
max = arr[i];
}
}
//max min已找到
int range = (max - min) + 1; //为开辟计数数组做准备
int* count = (int*)malloc(sizeof(int) * range);
if (count == NULL)
{
perror("malloc fail!");
}
memset(count, 0, sizeof(int) * range); //让count里面的数据都为0
for (int i = 0; i < n; i++)
{
count[arr[i] - min]++; //用相对值法统计出每个数据出现的次数，出现一次，count对应的数值就要++
}
//将count中出现的次数还原到原数组中
int index = 0;
for (int i = 0; i < n; i++)
{
while (count[i]--)
{
arr[index++] = i + min;
}
}
}这是test.c文件
#include"sort.h"
#include<time.h>
#include<stdlib.h>
void printarr(int* arr, int n)
{
for (int i = 0; i < n; i++)
{
printf("%d", arr[i]);
}
printf("\n");
}
void sorttest()
{
int arr[] = { 5,3,9,6,2,4,7,1,8 };
int n = sizeof(arr) / sizeof(arr[0]);
printf("排序之前：");
printarr(arr, n);
CountSort(arr, n);
printf("排序之后：");
printarr(arr, n);
}
int main()
{
sorttest();
return 0;
}运行结果：
12.各个排序的优缺点
3. 排序算法复杂度及稳定性分析 稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，⽽在排序后的序列中，r[i]仍在r[j]之 前，则称这种排序算法是稳定的；否则称为不稳定的。 辅助空间：这里简单理解为空间复杂度
为了更加直观的看一下哪个排序 更好，我们让这些方法排100000个数据，看一下运行的时间，单位：毫秒
这是用到的相关代码，感兴趣的可以看一下，此处不做讲解
#include"sort.h"
#include<time.h>
// 测试排序的性能对⽐
void TestOP()
{
srand(time(0));
const int N = 100000;
int* a1 = (int*)malloc(sizeof(int) * N);
int* a2 = (int*)malloc(sizeof(int) * N);
int* a3 = (int*)malloc(sizeof(int) * N);
int* a4 = (int*)malloc(sizeof(int) * N);
int* a5 = (int*)malloc(sizeof(int) * N);
int* a6 = (int*)malloc(sizeof(int) * N);
int* a7 = (int*)malloc(sizeof(int) * N);
for (int i = 0; i < N; ++i)
{
a1[i] = rand();
a2[i] = a1[i];
a3[i] = a1[i];
a4[i] = a1[i];
a5[i] = a1[i];
a6[i] = a1[i];
a7[i] = a1[i];
}
int begin1 = clock();
insertsort(a1, N);
int end1 = clock();
int begin2 = clock();
shellsort(a2, N);
int end2 = clock();
int begin3 = clock();
selectsort(a3, N);
int end3 = clock();
int begin4 = clock();
heapsort(a4, N);
int end4 = clock();
int begin5 = clock();
quicksort(a5, 0, N - 1);
int end5 = clock();
int begin6 = clock();
mergesort(a6, N);
int end6 = clock();
int begin7 = clock();
bubblesort(a7, N);
int end7 = clock();
printf("InsertSort:%d\n", end1 - begin1);
printf("ShellSort:%d\n", end2 - begin2);
printf("SelectSort:%d\n", end3 - begin3);
printf("HeapSort:%d\n", end4 - begin4);
printf("QuickSort:%d\n", end5 - begin5);
printf("MergeSort:%d\n", end6 - begin6);
printf("BubbleSort:%d\n", end7 - begin7);
free(a1);
free(a2);
free(a3);
free(a4);
free(a5);
free(a6);
free(a7);
}
int main()
{
TestOP();
return 0;
}
如果你从头开始看到这里，恭喜你，完成了对初级数据结构的学习！未来我将会陆续更新高级数据结构的知识，愿与诸位一同学习下去！一同完成C语言方向的相关课程的系统学习！ 我们c++见！！！
标签：arr,排序,end,int,void,printf,数据结构 From： https://blog.csdn.net/2401_85878549/article/details/143430540