柚子不幼稚--4th

以往对于Spring，或者SpringBoot，都只作为纯粹的开发工具，却并未去了解背后的原理。对于Spring Cloud，更是没有实际上手使用过。

第四次柚子班开篇从Spring/SpringBoot/SpringCloud讲起。

Spring是一个生态体系（也可以说是技术体系），是集大成者，它包含了Spring framework、Spring Boot、Spring Cloud等（还包括Spring Cloud data flow、spring data、spring integration、spring batch、spring security、spring hateoas），可以参考链接：https://spring.io/projects，如下图所示。

我们看看官方对Spring Boot的定义：

Spring Boot is designed to get you up and running as quickly as possible, with minimal upfront configuration of Spring. Spring Boot takes an opinionated view of building production-ready applications.

即Spring Boot为快速启动且最小化配置的spring应用而设计，并且它具有用于构建生产级别应用的一套固化的视图。这里的固化的视图，其实就是1Spring Boot的约定，Spring Boot的设计理念之一就是约定大于实现。

Spring Cloud事实上是一整套**基于Spring Boot的微服务解决方案**。它为开发者提供了很多工具，用于快速构建分布式系统的一些通用模式，例如：配置管理、注册中心、服务发现、限流、网关、链路追踪等。

默认情况下，Spring Boot会使用内置的tomcat容器去运行应用程序，但偶尔我们也会考虑使用Jetty去替代Tomcat；
对于Tomcat和Jetty，Spring Boot分别提供了对应的starter，以便尽可能的简化我们的开发过程；
当我们想使用Jetty的时候，修改pom文件即可使用。

    org.springframework.boot  
    spring-boot-starter-web 
          
              
                org.springframework.boot  
                spring-boot-starter-tomcat  
              
          
  
  
  
    org.springframework.boot
    spring-boot-starter-jetty  

从时间复杂度和稳定性两个角度来分析排序算法。

• 平方阶 (O(n2)) 排序：各类简单排序：直接插入、直接选择和冒泡排序。
• 线性对数阶 (O(nlog2n)) 排序：快速排序、堆排序和归并排序；
• O(n1+§)) 排序，§ 是介于 0 和 1 之间的常数：希尔排序
• 线性阶 (O(n)) 排序：基数排序，桶排序。

• 稳定的排序算法：冒泡排序、插入排序、归并排序和基数排序。
• 不稳定的排序算法：选择排序、快速排序、希尔排序、堆排序。

现场手写了三种排序算法：冒泡排序、插入排序和快速排序。

算法步骤：

1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
3. 针对所有的元素重复以上的步骤，除了最后一个。
4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

public static void sort(int arr[]) {
    for (int i = 0; i < arr.length - 1; i++) {
        boolean flag = false;
        for (int j = 0; j < arr.length - 1 - i; j++) {
               if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    flag = true;
               }
        }
        if (flag == false) {
            break;
        }
    }
}

算法步骤：

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

public static void doInsertSort(int[] array) {
    for (int index = 1; index < array.length; index++) 
        int temp = array[index];
        int leftindex = index - 1;
        while (leftindex >= 0 && array[leftindex] > temp) {
            array[leftindex + 1] = array[leftindex];
            leftindex--;
        }
        array[leftindex + 1] = temp;
    }
}

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

public class QuickSort {

    private static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int index = getIndex(arr, low, high);

            quickSort(arr, low, index - 1);
            quickSort(arr, index + 1, high);
        }

    }

    private static int getIndex(int[] arr, int low, int high) {
        int tmp = arr[low];
        while (low < high) {
            while (low < high && arr[high] >= tmp) {
                high--;
            }
            arr[low] = arr[high];
            while (low < high && arr[low] <= tmp) {
                low++;
            }
            arr[high] = arr[low];

        }
        
        arr[low] = tmp;
        return low;
    }
}