算法系列之十大经典排序算法

曾经终败给现在 2023-01-15 08:26 133阅读 0赞

### 算法系列之十大经典排序算法 ###

*   *  1、有哪十大经典排序算法？
     *  2、冒泡排序
     *   *  2.1、算法步骤
         *  2.2、动画演示
         *  2.3、 代码实现
     *  3、选择排序
     *   *  3.1、算法步骤
         *  3.2、动画演示
         *  3.3、 代码实现
     *  4、插入排序
     *   *  4.1、算法步骤
         *  4.2、动画演示
         *  4.3、 代码实现
     *  5、希尔排序
     *   *  5.1、算法步骤
         *  5.2、动画演示
         *  5.3、 代码实现
     *  6、归并排序
     *   *  6.1、算法步骤
         *  6.2、动画演示
         *  6.3、 代码实现
     *  7、快速排序
     *   *  7.1、算法步骤
         *  7.2、动画演示
         *  7.3、 代码实现
     *  8、堆排序
     *   *  8.1、算法步骤
         *  8.2、动画演示
         *  8.3、 代码实现
     *  9、计数排序
     *   *  9.1、算法步骤
         *  9.2、动画演示
         *  9.3、 代码实现
     *  10、桶排序
     *   *  10.1、算法步骤
         *  10.2、动画演示
         *  10.3、 代码实现
     *  11、基数排序
     *   *  11.1、算法步骤
         *  11.2、动画演示
         *  11.3、 代码实现
     *  12、往期佳文
     *   *  12.1、面试系列
         *  12.2、技术系列
         *  12.3、源码系列
         *  12.4、数据结构和算法系列
         *  12.5、并发系列
         *  12.6、面试题系列
         *  12.7、JVM系列

## 1、有哪十大经典排序算法？ ##

1.  冒泡排序
2.  选择排序
3.  插入排序
4.  希尔排序
5.  归并排序
6.  快速排序
7.  堆排序
8.  计数排序
9.  桶排序  
    10.基数排序

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d0eWljeQ_size_16_color_FFFFFF_t_70]

## 2、冒泡排序 ##

冒泡排序（Bubble Sort）也是一种简单直观的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端。  
       作为最简单的排序算法之一，冒泡排序给我的感觉就像 Abandon 在单词书里出现的感觉一样，每次都在第一页第一位，所以最熟悉。冒泡排序还有一种优化算法，就是立一个 flag，当在一趟序列遍历中元素没有发生交换，则证明该序列已经有序。但这种改进对于提升性能来说并没有什么太大作用。

### 2.1、算法步骤 ###

1.  比较相邻的元素。如果第一个比第二个大，就交换它们两个；
2.  对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
3.  针对所有的元素重复以上的步骤，除了最后一个；
4.  重复步骤1~3，直到排序完成。

### 2.2、动画演示 ###

![在这里插入图片描述][20210422085349573.gif_pic_center]

### 2.3、 代码实现 ###

for(int i = 0; i < len-1; i++) { 
    	for(int j = 0; j < len -1 -i; j++) { 
    		if (arr[j] > arr[j+1]) { 
    			int temp = arr[j+1];
    			arr[j+1] = arr[j];
    			arr[j] = temp;
    		}
    	}
    }

## 3、选择排序 ##

选择排序是一种简单直观的排序算法，无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。

### 3.1、算法步骤 ###

1.  首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
2.  再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
3.  重复第二步，直到所有元素均排序完毕。

### 3.2、动画演示 ###

![在这里插入图片描述][20210422090104912.gif_pic_center]

### 3.3、 代码实现 ###

for (int i = 0; i < len-1; i++) { 
    	minIndex = i;
    	for (int j = i+1; j < len; j++) { 
    		if (arr[j] < arr[minIndex]) { 
    			minIndex = j;
    		}
    	}
    	temp = arr[i];
    	arr[i] = arr[minIndex];
    	arr[minIndex] = temp;
    }

## 4、插入排序 ##

插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

### 4.1、算法步骤 ###

1.  将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列
2.  从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）

### 4.2、动画演示 ###

![在这里插入图片描述][20210422091953805.gif_pic_center]

### 4.3、 代码实现 ###

for (int i = 1; i < len; i++) { 
    	int temp = arr[i];
    	int j = i;
    	while ( j > 0 && temp < arr[j-1]) { 
    		arr[j] = arr[j-1];
    		j--;
    	}
    	if （j != i） { 
    		arr[j] = tmep;
    	}
    }

## 5、希尔排序 ##

1959年Shell发明，第一个突破O(n2)的排序算法，是简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。

### 5.1、算法步骤 ###

1.  选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
2.  按增量序列个数k，对序列进行k 趟排序；
3.  每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

### 5.2、动画演示 ###

![在这里插入图片描述][20210422102945478.gif_pic_center]

### 5.3、 代码实现 ###

for (int step = length / 2; step >= 1; step /= 2) { 
        for (int i = step; i < length; i++) { 
            temp = arr[i];
            int j = i - step;
            while (j >= 0 && arr[j] > temp) { 
                arr[j + step] = arr[j];
                j -= step;
            }
            arr[j + step] = temp;
        }
    }

## 6、归并排序 ##

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。 交换，则证明该序列已经有序。但这种改进对于提升性能来说并没有什么太大作用。

### 6.1、算法步骤 ###

1.  把长度为n的输入序列分成两个长度为n/2的子序列；
2.  对这两个子序列分别采用归并排序；
3.  将两个排序好的子序列合并成一个最终的排序序列。

### 6.2、动画演示 ###

![在这里插入图片描述][20210422103430364.gif_pic_center]

### 6.3、 代码实现 ###

int[] result = new int[left.length + right.length];
    int i = 0;
    while (left.length > 0 && right.length > 0) { 
        if (left[0] <= right[0]) { 
            result[i++] = left[0];
            left = Arrays.copyOfRange(left, 1, left.length);
        } else { 
            result[i++] = right[0];
            right = Arrays.copyOfRange(right, 1, right.length);
        }
    }
    
    while (left.length > 0) { 
        result[i++] = left[0];
        left = Arrays.copyOfRange(left, 1, left.length);
    }
    
    while (right.length > 0) { 
        result[i++] = right[0];
        right = Arrays.copyOfRange(right, 1, right.length);
    }

## 7、快速排序 ##

快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

### 7.1、算法步骤 ###

1.  从数列中挑出一个元素，称为 “基准”（pivot）；
2.  重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
3.  递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

### 7.2、动画演示 ###

![在这里插入图片描述][2021042210415471.gif_pic_center]

### 7.3、 代码实现 ###

private int[] quickSort(int[] arr, int left, int right) { 
        if (left < right) { 
            int partitionIndex = partition(arr, left, right);
            quickSort(arr, left, partitionIndex - 1);
            quickSort(arr, partitionIndex + 1, right);
        }
        return arr;
    }
    
    private int partition(int[] arr, int left, int right) { 
        // 设定基准值（pivot）
        int pivot = left;
        int index = pivot + 1;
        for (int i = index; i <= right; i++) { 
            if (arr[i] < arr[pivot]) { 
                swap(arr, i, index);
                index++;
            }
        }
        swap(arr, pivot, index - 1);
        return index - 1;
    }
    
    private void swap(int[] arr, int i, int j) { 
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

## 8、堆排序 ##

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

### 8.1、算法步骤 ###

1.  将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；
2.  将堆顶元素R\[1\]与最后一个元素R\[n\]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R\[1,2…n-1\]<=R\[n\]；
3.  由于交换后新的堆顶R\[1\]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R\[1\]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。

### 8.2、动画演示 ###

![在这里插入图片描述][20210422110108520.gif_pic_center]

### 8.3、 代码实现 ###

private void buildMaxHeap(int[] arr, int len) { 
        for (int i = (int) Math.floor(len / 2); i >= 0; i--) { 
            heapify(arr, i, len);
        }
    }
    
    private void heapify(int[] arr, int i, int len) { 
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        int largest = i;
    
        if (left < len && arr[left] > arr[largest]) { 
            largest = left;
        }
    
        if (right < len && arr[right] > arr[largest]) { 
            largest = right;
        }
    
        if (largest != i) { 
            swap(arr, i, largest);
            heapify(arr, largest, len);
        }
    }
    
    private void swap(int[] arr, int i, int j) { 
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

## 9、计数排序 ##

计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

### 9.1、算法步骤 ###

1.  找出待排序的数组中最大和最小的元素；
2.  统计数组中每个值为i的元素出现的次数，存入数组C的第i项；
3.  对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；
4.  反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。

### 9.2、动画演示 ###

![在这里插入图片描述][20210422110422201.gif_pic_center]

### 9.3、 代码实现 ###

private int[] countingSort(int[] arr, int maxValue) { 
        int bucketLen = maxValue + 1;
        int[] bucket = new int[bucketLen];
    
        for (int value : arr) { 
            bucket[value]++;
        }
    
        int sortedIndex = 0;
        for (int j = 0; j < bucketLen; j++) { 
            while (bucket[j] > 0) { 
                arr[sortedIndex++] = j;
                bucket[j]--;
            }
        }
        return arr;
    }
    
    private int getMaxValue(int[] arr) { 
        int maxValue = arr[0];
        for (int value : arr) { 
            if (maxValue < value) { 
                maxValue = value;
            }
        }
        return maxValue;
    }

## 10、桶排序 ##

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）。

### 10.1、算法步骤 ###

1.  设置一个定量的数组当作空桶；
2.  遍历输入数据，并且把数据一个一个放到对应的桶里去；
3.  对每个不是空的桶进行排序；
4.  从不是空的桶里把排好序的数据拼接起来。

### 10.2、动画演示 ###

![在这里插入图片描述][20210422112106153.png]

### 10.3、 代码实现 ###

private int[] bucketSort(int[] arr, int bucketSize) throws Exception { 
        if (arr.length == 0) { 
            return arr;
        }
    
        int minValue = arr[0];
        int maxValue = arr[0];
        for (int value : arr) { 
            if (value < minValue) { 
                minValue = value;
            } else if (value > maxValue) { 
                maxValue = value;
            }
        }
    
        int bucketCount = (int) Math.floor((maxValue - minValue) / bucketSize) + 1;
        int[][] buckets = new int[bucketCount][0];
    
        // 利用映射函数将数据分配到各个桶中
        for (int i = 0; i < arr.length; i++) { 
            int index = (int) Math.floor((arr[i] - minValue) / bucketSize);
            buckets[index] = arrAppend(buckets[index], arr[i]);
        }
    
        int arrIndex = 0;
        for (int[] bucket : buckets) { 
            if (bucket.length <= 0) { 
                continue;
            }
            // 对每个桶进行排序，这里使用了插入排序
            bucket = insertSort.sort(bucket);
            for (int value : bucket) { 
                arr[arrIndex++] = value;
            }
        }
    
        return arr;
    }
    
    /** * 自动扩容，并保存数据 * * @param arr * @param value */
    private int[] arrAppend(int[] arr, int value) { 
        arr = Arrays.copyOf(arr, arr.length + 1);
        arr[arr.length - 1] = value;
        return arr;
    }

## 11、基数排序 ##

基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。

### 11.1、算法步骤 ###

1.  取得数组中的最大数，并取得位数；
2.  arr为原始数组，从最低位开始取每个位组成radix数组；
3.  对radix进行计数排序（利用计数排序适用于小范围数的特点）

### 11.2、动画演示 ###

![在这里插入图片描述][20210422112659827.gif_pic_center]

### 11.3、 代码实现 ###

/** * 获取最高位数 */
    private int getMaxDigit(int[] arr) { 
        int maxValue = getMaxValue(arr);
        return getNumLenght(maxValue);
    }
    
    private int getMaxValue(int[] arr) { 
        int maxValue = arr[0];
        for (int value : arr) { 
            if (maxValue < value) { 
                maxValue = value;
            }
        }
        return maxValue;
    }
    
    protected int getNumLenght(long num) { 
        if (num == 0) { 
            return 1;
        }
        int lenght = 0;
        for (long temp = num; temp != 0; temp /= 10) { 
            lenght++;
        }
        return lenght;
    }
    
    private int[] radixSort(int[] arr, int maxDigit) { 
        int mod = 10;
        int dev = 1;
    
        for (int i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) { 
            // 考虑负数的情况，这里扩展一倍队列数，其中 [0-9]对应负数，[10-19]对应正数 (bucket + 10)
            int[][] counter = new int[mod * 2][0];
    
            for (int j = 0; j < arr.length; j++) { 
                int bucket = ((arr[j] % mod) / dev) + mod;
                counter[bucket] = arrayAppend(counter[bucket], arr[j]);
            }
    
            int pos = 0;
            for (int[] bucket : counter) { 
                for (int value : bucket) { 
                    arr[pos++] = value;
                }
            }
        }
    
        return arr;
    }
    
    /** * 自动扩容，并保存数据 * * @param arr * @param value */
    private int[] arrayAppend(int[] arr, int value) { 
        arr = Arrays.copyOf(arr, arr.length + 1);
        arr[arr.length - 1] = value;
        return arr;
    }

--------------------

## 12、往期佳文 ##

### 12.1、面试系列 ###

1、[吊打面试官之一面自我介绍][Link 1]  
2、[吊打面试官之一面项目介绍][Link 2]  
3、[吊打面试官之一面系统架构设计][Link 3]  
4、[吊打面试官之一面你负责哪一块][Link 4]  
5、[吊打面试官之一面试官提问][Link 5]  
6、[吊打面试官之一面你有什么问题吗][Link 6]

······持续更新中······

### 12.2、技术系列 ###

1、[吊打面试官之分布式会话][Link 7]  
2、[吊打面试官之分布式锁][Link 8]  
3、[吊打面试官之乐观锁][Link 9]  
4、[吊打面试官之幂等性问题][Link 10]  
5、[吊打面试关之分布式事务][Link 11]  
6、[吊打面试官之项目线上问题排查][Link 12]

······持续更新中······

### 12.3、源码系列 ###

1、[源码分析之SpringBoot启动流程原理][SpringBoot]  
2、[源码分析之SpringBoot自动装配原理][SpringBoot 1]  
3、[源码分析之ArrayList容器][ArrayList]  
4、[源码分析之LinkedList容器][LinkedList]  
5、[源码分析之HashMap容器][HashMap]  
6、[源码分析之ConcurrentHashMap容器][ConcurrentHashMap]  
7、[源码分析之五种Map容器的区别][Map]

······持续更新中······

### 12.4、数据结构和算法系列 ###

1、[数据结构之八大数据结构][Link 13]  
2、[数据结构之动态查找树（二叉查找树，平衡二叉树，红黑树）][Link 14]

······持续更新中······

### 12.5、并发系列 ###

1、[并发系列之初识多线程][Link 15]  
2、[并发系列之JMM内存模型][JMM]  
3、[并发系列之synchronized解析][synchronized]  
4、[并发系列之volatile解析][volatile]  
5、[并发系列之synchronized与volatile的区别][synchronized_volatile]  
6、[并发系列之Lock解析][Lock]  
7、[并发系列之synchronized与lock的区别][synchronized_lock]  
8、[并发系列之CAS与原子操作][CAS]  
9、[并发系列之AQS分析][AQS]  
10、[并发系列之线程池解析][Link 16]  
11、[并发系列之锁的知识梳理][Link 17]

······持续更新中······

### 12.6、面试题系列 ###

1、[面试题系列之并发面试题][Link 18]  
2、[面试题系列之网络面试题][Link 19]  
3、[面试题系列之IO面试题][IO]  
4、[面试题系列之消息队列面试题][Link 20]

······持续更新中······

### 12.7、JVM系列 ###

1、[JVM系列之JVM介绍][JVM_JVM]  
2、[JVM系列之Class文件解析][JVM_Class]  
3、[JVM系列之Java 类加载机制][JVM_Java]  
4、[JVM系列之JVM内存结构][JVM_JVM 1]

······持续更新中······

--------------------

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d0eWljeQ_size_16_color_FFFFFF_t_70]: /images/20221022/58a4b6b08cec48778574b476fb9e60a8.png
[20210422085349573.gif_pic_center]: /images/20221022/d91f76cc986448f1b367ecaf495f6907.png
[20210422090104912.gif_pic_center]: /images/20221022/351f3c74491d442d965b0cfb83a7de90.png
[20210422091953805.gif_pic_center]: /images/20221022/4d8ddf64f1484fb6945349d2db36d444.png
[20210422102945478.gif_pic_center]: /images/20221022/609c2241c57545c48a106115564571ce.png
[20210422103430364.gif_pic_center]: /images/20221022/b1f2578bdc6844d2b0ed33c8819aedcc.png
[2021042210415471.gif_pic_center]: /images/20221022/04855c83fb5f4057b46344e7f0c782d1.png
[20210422110108520.gif_pic_center]: /images/20221022/1125de07838b406282bef62f3fbfe48d.png
[20210422110422201.gif_pic_center]: /images/20221022/188d777fdfbd4d6c87a84085fa9ee4ad.png
[20210422112106153.png]: /images/20221022/cb844cf467b74c428f4d5b8fd97b4cda.png
[20210422112659827.gif_pic_center]: /images/20221022/196ccd2ceed14677abf7959f9a27e61e.png
[Link 1]: https://blog.csdn.net/wtyicy/article/details/114933478
[Link 2]: https://blog.csdn.net/wtyicy/article/details/114983053
[Link 3]: https://blog.csdn.net/wtyicy/article/details/115005012
[Link 4]: https://blog.csdn.net/wtyicy/article/details/115064661
[Link 5]: https://blog.csdn.net/wtyicy/article/details/115296365
[Link 6]: https://blog.csdn.net/wtyicy/article/details/115402511
[Link 7]: https://blog.csdn.net/wtyicy/article/details/114685293
[Link 8]: https://blog.csdn.net/wtyicy/article/details/114915987
[Link 9]: https://blog.csdn.net/wtyicy/article/details/114915177
[Link 10]: https://blog.csdn.net/wtyicy/article/details/114888754
[Link 11]: https://blog.csdn.net/wtyicy/article/details/115081790
[Link 12]: https://blog.csdn.net/wtyicy/article/details/115292969
[SpringBoot]: https://blog.csdn.net/wtyicy/article/details/115181539
[SpringBoot 1]: https://blog.csdn.net/wtyicy/article/details/115233701
[ArrayList]: https://blog.csdn.net/wtyicy/article/details/115244565
[LinkedList]: https://blog.csdn.net/wtyicy/article/details/115314536
[HashMap]: https://blog.csdn.net/wtyicy/article/details/115365586
[ConcurrentHashMap]: https://blog.csdn.net/wtyicy/article/details/115549277
[Map]: https://blog.csdn.net/wtyicy/article/details/115551781
[Link 13]: https://blog.csdn.net/wtyicy/article/details/115342236
[Link 14]: https://blog.csdn.net/wtyicy/article/details/115353145
[Link 15]: https://blog.csdn.net/wtyicy/article/details/115386707
[JMM]: https://blog.csdn.net/wtyicy/article/details/115455467
[synchronized]: https://blog.csdn.net/wtyicy/article/details/115454573
[volatile]: https://blog.csdn.net/wtyicy/article/details/115502376
[synchronized_volatile]: https://blog.csdn.net/wtyicy/article/details/115512541
[Lock]: https://blog.csdn.net/wtyicy/article/details/115524613
[synchronized_lock]: https://blog.csdn.net/wtyicy/article/details/115536187
[CAS]: https://blog.csdn.net/wtyicy/article/details/115611453
[AQS]: https://blog.csdn.net/wtyicy/article/details/115614355
[Link 16]: https://blog.csdn.net/wtyicy/article/details/115653127
[Link 17]: https://blog.csdn.net/wtyicy/article/details/115372518
[Link 18]: https://blog.csdn.net/wtyicy/article/details/115681186
[Link 19]: https://blog.csdn.net/wtyicy/article/details/115921405
[IO]: https://blog.csdn.net/wtyicy/article/details/115922106
[Link 20]: https://blog.csdn.net/wtyicy/article/details/115940994
[JVM_JVM]: https://blog.csdn.net/wtyicy/article/details/115858906
[JVM_Class]: https://blog.csdn.net/wtyicy/article/details/115868372
[JVM_Java]: https://blog.csdn.net/wtyicy/article/details/115897057
[JVM_JVM 1]: https://blog.csdn.net/wtyicy/article/details/115906418