知識點01：九大排序演算法

public class Sort {
    public static void main(String[] args) {
        testTime();
        testSort();
    }

    public static void testTime() {
        int[] arr = new int[10000];
        for (int i = 0; i < 10000; i++) {
            arr[i] = (int) (Math.random() * 100 + 1);
        }
        long s = System.currentTimeMillis();
//        bubbleSort(arr);
//        selectionSort(arr);
//        insertionSort(arr);
//        shellSort(arr);
//        quickSort(arr, 0, arr.length - 1);
//        mergeSort(arr, 0, arr.length - 1, new int[arr.length]);
//        radixSort(arr);
//        countingSort(arr);
//        heapSort(arr);
        long e = System.currentTimeMillis();
        System.out.println((e - s) + "ms");
    }

    public static void testSort() {
        int[] arr = new int[50];
        for (int i = 0; i < 50; i++) {
            arr[i] = (int) (Math.random() * 100 + 1);
        }
//        bubbleSort(arr);
//        selectionSort(arr);
//        insertionSort(arr);
//        shellSort(arr);
//        quickSort(arr, 0, arr.length - 1);
//        mergeSort(arr, 0, arr.length - 1, new int[arr.length]);
//        radixSort(arr);
//        countingSort(arr);
//        heapSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    //堆排序（大頂堆：升序演算法，小頂堆：降序演算法）
    public static void heapSort(int arr[]) {
        //創建大頂堆
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            heapAdjust(arr, i, arr.length);
        }
        //調整大頂堆
        for (int i = arr.length - 1; i > 0; i--) {
            //交換元素
            int temp = arr[i];
            arr[i] = arr[0];
            arr[0] = temp;
            //調整新堆
            heapAdjust(arr, 0, i);
        }
    }

    //堆調整
    public static void heapAdjust(int arr[], int ci, int length) {
        //快取當前結點
        int temp = arr[ci];
        //開始回圈調整
        for (int li = ci * 2 + 1; li < length; li = li * 2 + 1) {
            //說明左子結點的值小于右子結點的值
            if (li + 1 < length && arr[li] < arr[li + 1]) {
                li = li + 1;
            }
            //說明當前子結點的值大于父結點的值
            if (arr[li] > temp) {
                arr[ci] = arr[li];
                ci = li;
            } else {
                break;
            }
        }
        //放到調整位置
        arr[ci] = temp;
    }

    //計數排序：升序演算法
    public static void countingSort(int[] arr) {
        if (arr == null || arr.length == 0) return;
        int max = arr[0];
        int min = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > max) max = arr[i];
            if (arr[i] < min) min = arr[i];
        }
        //統計次數
        int[] counts = new int[max - min + 1];
        for (int i = 0; i < arr.length; i++) {
            counts[arr[i] - min]++;
        }
        //累加次數
        for (int i = 1; i < counts.length; i++) {
            counts[i] += counts[i - 1];
        }
        //倒著重排
        int[] newArr = new int[arr.length];
        for (int i = arr.length - 1; i >= 0; i--) {
            newArr[--counts[arr[i] - min]] = arr[i];
        }
        //復制陣列
        for (int i = 0; i < arr.length; i++) {
            arr[i] = newArr[i];
        }
    }

    //基數排序：升序演算法
    public static void radixSort(int[] arr) {
        if (arr == null || arr.length == 0) return;
        int max = arr[0];
        int min = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > max) max = arr[i];
            if (arr[i] < min) min = arr[i];
        }
        for (int i = 0; i < arr.length; i++) {
            arr[i] -= min;
        }
        int maxLength = String.valueOf(max - min).length();
        int[][] bucket = new int[10][arr.length];
        int[] bucketIndex = new int[10];
        for (int rounds = 0, base = 1; rounds < maxLength; rounds++, base *= 10) {
            for (int i = 0; i < arr.length; i++) {
                int digit = arr[i] / base % 10;
                bucket[digit][bucketIndex[digit]++] = arr[i];
            }
            int pos = 0;
            for (int i = 0; i < bucketIndex.length; i++) {
                for (int j = 0; j < bucketIndex[i]; j++) {
                    arr[pos++] = bucket[i][j];
                }
                bucketIndex[i] = 0;
            }
        }
        for (int i = 0; i < arr.length; i++) {
            arr[i] += min;
        }
    }

    //歸并排序：升序演算法
    public static void mergeSort(int[] arr, int L, int R, int[] temp) {
        if (L >= R) return;
        int tIdx = L, left = L, middle = (L + R) / 2, right = middle + 1;
        mergeSort(arr, L, middle, temp);
        mergeSort(arr, right, R, temp);
        while (left <= middle && right <= R) {
            if (arr[left] <= arr[right]) {
                temp[tIdx++] = arr[left++];
            } else {
                temp[tIdx++] = arr[right++];
            }
        }
        while (left <= middle) temp[tIdx++] = arr[left++];
        while (right <= R) temp[tIdx++] = arr[right++];
        for (int i = L; i <= R; i++) {
            arr[i] = temp[i];
        }
    }

    //快速排序：升序演算法
    public static void quickSort(int[] arr, int L, int R) {
        if (L >= R) return;
        int left = L, right = R, pivot = arr[L];
        while (left < right) {
            while (left < right && arr[right] >= pivot) right--;
            arr[left] = arr[right];
            while (left < right && arr[left] <= pivot) left++;
            arr[right] = arr[left];
        }
        arr[left] = pivot;
        quickSort(arr, L, left - 1);
        quickSort(arr, left + 1, R);
    }

    //希爾排序：升序演算法
    public static void shellSort(int[] arr) {
        for (int step = arr.length / 2; step > 0; step /= 2) {
            for (int i = step; i < arr.length; i++) {
                int temp = arr[i];
                int j = i - step;
                while (j >= 0 && arr[j] > temp) {
                    arr[j + step] = arr[j];
                    j -= step;
                }
                arr[j + step] = temp;
            }
        }
    }

    //插入排序：升序演算法
    public static void insertionSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int temp = arr[i];
            int j = i - 1;
            while (j >= 0 && arr[j] > temp) {
                arr[j + 1] = arr[j];
                j -= 1;
            }
            arr[j + 1] = temp;
        }
    }

    //選擇排序：升序演算法
    public static void selectionSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[minIndex] > arr[j]) {
                    minIndex = j;
                }
            }
            if (minIndex != i) {
                int temp = arr[minIndex];
                arr[minIndex] = arr[i];
                arr[i] = temp;
            }
        }
    }

    //冒泡排序：升序演算法
    public static void bubbleSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            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;
                }
            }
        }
    }
}

知識點02：二分查找演算法

遞回版：

public static int binarySearch(int[] arr, int target) {
    return binarySearch(arr, 0, arr.length - 1, target);
}

private static int binarySearch(int[] arr, int left, int right, int target) {
    while (left <= right) {
        int middle = (left + right) / 2;
        if (target < arr[middle]) {
            right = middle - 1;
        } else if (target > arr[middle]) {
            left = middle + 1;
        } else {
            return middle;
        }
    }
    return -1;
}

迭代版：

public static int binarySearch(int[] arr, int target) {
    return binarySearch(arr, 0, arr.length - 1, target);
}

private static int binarySearch(int[] arr, int left, int right, int target) {
    if (left > right) return -1;
    int middle = (left + right) / 2;
    if (target < arr[middle]) {
        return binarySearch(arr, left, middle - 1, target);
    } else if (target > arr[middle]) {
        return binarySearch(arr, middle + 1, right, target);
    } else {
        return middle;
    }
}

知識點03：二叉樹的遍歷

樹結點：

class TreeNode {
    int data;
    TreeNode left;
    TreeNode right;

    public TreeNode() {}

    public TreeNode(int data) {
        this.data = data;
    }
}

遞回版：

//中左右
public static void preOrder(TreeNode root) {
    if (root == null) return;
    System.out.print(root.data + " ");
    preOrder(root.left);
    preOrder(root.right);
}

//左中右
public static void midOrder(TreeNode root) {
    if (root == null) return;
    midOrder(root.left);
    System.out.print(root.data + " ");
    midOrder(root.right);
}

//左右中
public static void postOrder(TreeNode root) {
    if (root == null) return;
    postOrder(root.left);
    postOrder(root.right);
    System.out.print(root.data + " ");
}

迭代版：

//中左右 => 右左(中空)
public static void preOrder(TreeNode root) {
    if (root == null) return;
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        if (node != null) {
            if (node.right != null) stack.push(node.right);
            if (node.left != null) stack.push(node.left);
            stack.push(node);
            stack.push(null);
        } else {
            node = stack.pop();
            System.out.print(node.data + " ");
        }
    }
}

//左中右 => 右(中空)左
public static void midOrder(TreeNode root) {
    if (root == null) return;
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        if (node != null) {
            if (node.right != null) stack.push(node.right);
            stack.push(node);
            stack.push(null);
            if (node.left != null) stack.push(node.left);
        } else {
            node = stack.pop();
            System.out.print(node.data + " ");
        }
    }
}

//左右中 => (中空)右左
public static void postOrder(TreeNode root) {
    if (root == null) return;
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        if (node != null) {
            stack.push(node);
            stack.push(null);
            if (node.right != null) stack.push(node.right);
            if (node.left != null) stack.push(node.left);
        } else {
            node = stack.pop();
            System.out.print(node.data + " ");
        }
    }
}

層序遍歷：

public static void layerOrder(TreeNode root) {
    if (root == null) return;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        System.out.print(node.data + " ");
        if (node.left != null) queue.offer(node.left);
        if (node.right != null) queue.offer(node.right);
    }
}

知識點04：Spring IOC

執行流程：

生命周期：

回圈依賴：

1、如果只有一級快取能否解決回圈依賴問題？

如果只有一級快取的話，那就意味著成品物件和半成品物件都要放到一級快取中，在獲取物件的時候，就有可能獲取到半成品物件，而這個半成品物件是不能直接使用的，因此需要使用一級快取存放成品物件，用二級快取存放半成品物件，

2、只有一級二級快取能否解決回圈依賴問題？

只有一級二級快取可以解決回圈依賴問題，但是這個是有前提條件的，前提是不使用AOP，如果開啟了AOP，那么Spring將會創建代理物件，如果存在代理物件回圈依賴問題任然存在，

3、那么問題又來了，為什么需要三級快取呢？

三級快取是為了解決代理程序中的回圈依賴問題，

4、使用代碼演示一下回圈依賴執行整個流程？

<bean id="a" class="io.github.caochenlei.domain.A">
    <property name="b" ref="b"></property>
</bean>

<bean id="b" class="io.github.caochenlei.domain.B">
    <property name="a" ref="a"></property>
</bean>

public class ABTest {
    public static void main(String[] args) {
        ApplicationContext applicationContext = new ClassPathXmlApplicationContext("ab.xml");
        A a = applicationContext.getBean(A.class);
        System.out.println(a);
        B b = applicationContext.getBean(B.class);
        System.out.println(b);
    }
}

知識點05：Spring AOP

暫未更新

知識點06：TCP三次握手

• 第一次握手： 起初兩端都處于CLOSED關閉狀態，Client將標志位SYN置為1，隨機產生一個值seq=x，并將該資料包發送給Server，Client進入SYN-SENT狀態，等待Server確認；
• 第二次握手： Server收到資料包后由標志位SYN=1得知Client請求建立連接，Server將標志位SYN和ACK都置為1，ack=x+1，隨機產生一個值seq=y，并將該資料包發送給Client以確認連接請求，Server進入SYN-RCVD狀態，此時作業系統為該TCP連接分配TCP快取和變數；
• 第三次握手： Client收到確認后，檢查ack是否為x+1，ACK是否為1，如果正確則將標志位ACK置為1，ack=y+1，并且此時作業系統為該TCP連接分配TCP快取和變數，并將該資料包發送給Server，Server檢查ack是否為y+1，ACK是否為1，如果正確則連接建立成功，Client和Server進入ESTABLISHED狀態，完成三次握手，隨后Client和Server就可以開始傳輸資料，

知識點07：TCP四次揮手

• 第一次揮手： A的應用行程先向其TCP發出連接釋放報文段（FIN=1，序號seq=u），并停止再發送資料，主動關閉TCP連接，進入FIN-WAIT-1（終止等待1）狀態，等待B的確認，
• 第二次揮手： B收到連接釋放報文段后即發出確認報文段，（ACK=1，序號seq=v，確認號ack=u+1），B進入CLOSE-WAIT（關閉等待）狀態，此時的TCP處于半關閉狀態，A到B的連接釋放，A收到B的確認后，進入FIN-WAIT-2（終止等待2）狀態，等待B發出的連接釋放報文段，
• 第三次揮手： B沒有要向A發出的資料，B發出連接釋放報文段（FIN=1，ACK=1，序號seq=w，確認號ack=u+1），B進入LAST-ACK（最后確認）狀態，等待A的確認，
• 第四次揮手： A收到B的連接釋放報文段后，對此發出確認報文段（ACK=1，序號seq=u+1，確認號ack=w+1），A進入TIME-WAIT（時間等待）狀態，此時TCP未釋放掉，需要經過時間等待計時器設定的時間2MSL后，A才進入CLOSED狀態，