Tim's Note

快速排序(Quick Sort)被称为20世纪对世界影响最大的算法之一，现在我们来看快速排序算法，习惯性把它简称为快排，快排利用的也是分治思想。乍看起来，它有点像归并排序，但是思路其实完全不一样。现在，我们先来看下快排的核心思想，最后将讲述快速排序的两个优化方案，其实还有一种三路快排的优化方案也是可以的，但是本片文章重点在于快速排序的原理和实现，所以三路快排的优化方案不会出现在这篇文章里，以后再详细记录一下。

之前几篇文章我介绍了三种O(n²)的排序算法 《O(n²)的三个排序算法》 （选择排序、插入排序和冒泡排序）以及它们的优化，然后顺便还写了一篇希尔排序的文章 《插入排序的优化之希尔排序》 ，但是其实用的比较多的还是直接插入排序，它们比较适合于小规模数据的排序 。下面我将记录时间复杂度为nlog(n)的几种排序算法之一 —— 归并排序算法，这种排序算法适合大规模的数据排序，比之前的O(n²)的三种排序算法更为常用，在学习之前我们可以先对比一下nlog(n)和n²是什么概念。

希尔排序是插入排序的一种，又称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法，可以说它是插入排序的高级版。我们可以先回顾一下直接插入排序的过程：

排序前将第一个元素看成有序的数列

• 第1趟排序后：得到一个长度为2的有序数列
• 第2趟排序后：得到一个长度为3的有序数列
• 第3趟排序后：得到一个长度为4的有序数列
• ……..每趟插入排序，都可以将一个无序值插入一个有序数列，直到全部元素有序

今天复习下最简单的三个排序算法，一个是选择排序，一个是插入排序，一个是冒泡排序，三者时间复杂度都是O(n²)，通过分析来发现三者的优劣，以及对最好的情况和最坏的情况进行分析。 另外，这三中排序算法都是基于比较的排序算法。基于比较的排序算法的执行过程，会涉及两种操作，一种是元素比较大小，另一种是元素交换或移动。所以，如果我们在分析排序算法的执行效率的时候，应该把比较次数和交换（或移动）次数也考虑进去。

我们知道SpringBoot的理念就是约定大于配置，这也使得我们在开发应用程序的过程更加便捷，以前的大量XML配置直接是噩梦呀，现在出现了SpringBoot明显降低了开发成本，而且大量的注解的使用帮我们省略掉了很多代码。本篇文章主要探究的是SpringBoot是如何实现自动配置并且如何加载配置Bean的，其实主要就是探究@EnableAutoConfiguration注解究竟发挥了怎样的作用。

ICO容器的结构如上图所示，首先要让IOC容器去读取Bean的配置信息，并在容器中生成一份相应的Bean定义注册表，根据这张注册表去实例化Bean，装配好Bean之间的依赖关系，为上层提供准备就绪的环境，Spring提供一个配置文件描述Bean还有Bean之间的依赖关系，利用Java语言的反射功能实例化Bean并建立Bean之间的依赖关系。

SpringIOC是Spring Core最核心的部分，要了解控制反转(Inversion of Control)，我觉得有必要先了解软件设计的一个重要思想：依赖倒置原则。

1、高层模块不应该依赖底层模块，二者都应该依赖抽象 2、抽象不应该依赖细节，细节应该依赖抽象。 3、依赖倒置的中心思想是面向接口编程。 4、依赖倒置原则是基于这样的设计理念：相对于细节的多变性，抽象的东西要稳定的多。以抽象为基础搭建的架构比以细节为基础搭建的架构要稳定的多。 5、使用接口或抽象类的目的是指定好规范，而不涉及任何具体操作，展现细节的任务交给他们的实现类来完成。

本篇文章主要记录了JUC的四个并发工具类，闭锁CountDownlatch、栅栏CyclicBarrier、信号量Semaphore、交换器Exchanger。CountDownlatch通常用于主线程等待其他任务线程执行完毕的场景；CyclicBarrier主要阻塞当前线程，等待其他线程（大家无论谁先跑到A点，必须要等其他线程也到达了A点，大家才能继续）。信号量Semaphore可以用来控制同时访问特定资源的线程数量（比如100个线程只能有10个线程可以获得MySQL连接）。交换器Exchanger很少用，只适用于两个线程在同步点交换数据的场景（如下图）。