l ------------ pivot --------------- r
一組從左往右找               一組從右往左找

    @Test
    public void processDemo() {
        int arr[] = {-9, 78, 0, 23, -567, 70};
        System.out.println("原始數(shù)組：" + Arrays.toString(arr));
        processQuickSort(arr, 0, arr.length - 1);
    }

    /**
     * @param arr
     * @param left  左邊這一組的下標起始點，到中間值，則為一組
     * @param right 右邊這一組的下標結(jié)束點，到中間值，則為一組
     */
    public void processQuickSort(int[] arr, int left, int right) {
        /*
         基本思想：選擇一個基準值，將基準值小分成一組，比基準值大的分成一組。
         這里的實現(xiàn)思路：
            1. 挑選的基準值為數(shù)組中間的值
            2. 中間值就把數(shù)組分成了兩組
            3. 左邊一組，從左到右，挨個與 基準值 比較，找出比基準值大的值
            4. 右邊一組，從右到左，挨個與 基準值 比較，找出比基準值小的值
            5. 左右兩邊各找到一個值，那么就讓這兩個值進行交換
            6. 然后繼續(xù)找，直到左右兩邊碰到，這一輪就結(jié)束。這一輪就稱為快速排序
            7. 繼續(xù)對分出來的小組，進行上述的快速排序操作，直到組內(nèi)只剩下一個數(shù)時，則排序完成

            l ------------ pivot --------------- r
            一組從左往右找               一組從右往左找
         */
        int l = left;
        int r = right;
        // 中心點，讓這個點作為基準值
        int pivot = arr[(left + right) / 2];
        // 當他們沒有碰到的時候，說明還這一輪還可以繼續(xù)找
        while (l < r) {
            // 左邊組：當找到大于基準值時，退出循環(huán)，則表示該值需要交換到右側(cè)去: arr[l] > pivot
            //      也就是說，如果 arr[l] < pivot，則表示還沒有找到比基準值大的數(shù)
            //      注意：不能等于 pivort，因為最差的情況沒有找到，則最后 arr[l] 就是 pivot 這個值，也同樣退出循環(huán)
            while (arr[l] < pivot) {
                l++; // 所以讓左邊這一組繼續(xù)找
            }

            // 右邊組：當找到小于基準值時，退出循環(huán)，則表示該值需要交換到左側(cè)去：arr[r] < pivot
            //      也就是說，如果 arr[l] > pivot，則表示還沒有找到比基準值小的數(shù)
            //注意：這里也同樣跟上面一樣，不能等于 pivort
            while (arr[r] > pivot) {
                r--;//讓右邊組繼續(xù)找
            }

            // 當左側(cè)與右側(cè)相碰時，說明兩邊都沒有找到，這一輪不用進行交換
            // 等于表示，找到了中間的下標
            if (l >= r) {
                break;
            }

            // 當找到時，則兩數(shù)進行交換。
            //注意：這里可能會出現(xiàn)有一組已經(jīng)找完了，或者沒有找到，但是另一組找到了，所以一個是指向 pivot 的，
            //另一個則是指向要交換的數(shù),交換后 pivot的值在數(shù)組中的位置會發(fā)生改變，下次的交換方式就會發(fā)生變化。這個地方要動腦筋想想。
            int temp = arr[l];
            arr[l] = arr[r];
            arr[r] = temp;

            // 當交換后，
            // 當數(shù)組是： {-9, 78, 0, -23, 0, 70}  時（pivot的值在數(shù)組中有多個），就可以驗證這里的邏輯
            // 如果沒有這個判定，將會導致，l 永遠 小于 r。循環(huán)不能退出來的情況，就出現(xiàn)死循環(huán)了
            if (arr[l] == pivot) {
                /*
                  l 自己不能往前移動 一步，因為當交換完成后為：{-9, 0, 0, -23, 78, 70}
                  l = 1,arr[l] = 0
                  r = 4,arr[r] = 78
                  再經(jīng)過一次循環(huán)后
                  l = 1,arr[l] = 0
                  r = 3,arr[r] = -23
                  交換后數(shù)組為：{-9，-23，0，0，78，70}
                  此時 l = 1，arr[l] = -23;r = 3,arr[r] = 0
                  又經(jīng)過一次循環(huán)后
                  l = 2,arr[l] = 0
                  r = 3,arr[r] = 0
                  數(shù)組為：{-9，-23，0，0，78，70}
                  進入了死循環(huán)
                  這里好好動腦子想想
                  
                  這里為什么是用r-=1呢？是因為if里面的條件是arr[l] == pivot，如果要排序的數(shù)組中不存在多個和基準值相等的值，
                  那么用l+=1的話，l就會跑過分界線（基準值），跑到另一組去，這個算法也就失敗了，
                  還有一個原因是，r 是剛剛交換過的，一定比 基準值大，所以沒有必要再和基準值比較了
                 */
                r -= 1;
            }
            // 這里和上面一致，如果說，先走了上面的 r-=1
            // 這里也滿足（也就是說有多個值和基準值相等），那么說明，下一次是相同的兩個值，一個是 r == 一個是基準值
            // 但是他們是相同的值，r后退一步 l前進一步，不影響。但是再走這完這里邏輯時，就會導致  l > r，退出整個循環(huán)
            if (arr[r] == pivot) {
                l += 1;
            }
        }
        System.out.println("第 1 輪排序后：" + Arrays.toString(arr));
    }

        System.out.println("第 1 輪排序后：" + Arrays.toString(arr));

		/*
		if (l >= r) {
                break;
            }
            循環(huán)從這條代碼中跳出就會l = r
		*/
        // 如果 l = r，會出現(xiàn)死循環(huán)，出現(xiàn)棧溢出
		//這里也要動腦子想想
        if (l == r) {
            l++;
            r--;
        }

        // 開始左遞歸
        // 上面算法是 r--，l++ ，往兩組的中間走，當 left < r 時，表示還可以繼續(xù)分組
        if (left < r) {
            processQuickSort(arr, left, r);
        }

        if (right > l) {
            processQuickSort(arr, l, right);
        }

  /**
     * 快速排序默寫實現(xiàn)
     * 
     *     基本思想：通過一趟將要排序的數(shù)據(jù)，分隔成獨立的兩個部分，一部分的所有數(shù)據(jù)都比另一部分的所有數(shù)據(jù)要小。
     *     思路分析：
     *      {-9, 78, 0, 23, -567, 70};  length=6
     *      1. 挑選中間的值作為 基準值：(0 + (6 -1))/2= [2] = 0
     *      2. 左側(cè) left 部分，從 0 開始到中間值 -1： 0,1: -9, 78,找出一個比基準值大的數(shù)
     *      3. 右側(cè) right 部分，從中間值 + 1 到數(shù)組大小-1：3,5：23,-567, 70，找出一個比基準值小的數(shù)
     *      4. 如果找到，則將他們進行交換，這樣一輪下來，就完成了一次快速排序：一部分的所有數(shù)據(jù)都比另一部分的所有數(shù)據(jù)要小。
     *      4. 如果左側(cè)部分還可以分組，則進行左側(cè)遞歸調(diào)用
     *      5. 如果右側(cè)部分還可以分組，則進行右側(cè)遞歸調(diào)用
     *
     *    簡單說：一輪快速排序示意圖如下：
     *                   中間的基準值
     *      l ------------ pivot --------------- r
     *      一組從左往右找               一組從右往左找
     *      找到比基準值大的數(shù)          找出一個比基準值小的數(shù)
     *                    然后進行交換
     * 
     */
    @Test
    public void quickSortTest() {
        int arr[] = {-9, 78, 0, 23, -567, 70};
//        int arr[] = {-9, 78, 0, -23, 0, 70}; // 在推導過程中，將會導致交換異常的數(shù)組，在這里不會出現(xiàn)那種情況
        int left = 0;
        int right = arr.length - 1;
        System.out.println("原始數(shù)組：" + Arrays.toString(arr));
        quickSort(arr, left, right);
        System.out.println("排序后：" + Arrays.toString(arr));
    }

    public void quickSort(int[] arr, int left, int right) {
        // 找到中間值
        int pivotIndex = (left + right) / 2;
        int pivot = arr[pivotIndex];
        int l = left;
        int r = right;
        while (l < r) {
            // 從左往右找，直到找到一個數(shù)，比基準值大的數(shù)
            while (arr[l] < pivot) {
                l++;
            }
            // 從右往左找，知道找到一個數(shù)，比基準值小的數(shù)
            while (arr[r] > pivot) {
                r--;
            }
            // 表示未找到
            if (l >= r) {
                break;
            }
            // 進行交換
            int temp = arr[l];
            arr[l] = arr[r];
            arr[r] = temp;

            // 那么下一輪，左側(cè)的這個值將不再參與排序，因為剛交換過，一定比基準值小
            // 那么下一輪，右側(cè)的這個值將不再參與排序，因為剛交換過，一定比基準值大
            r--;
            l++;
        }

        // 當一輪找完后，沒有找到，則是中間值時，
        // 需要讓他們擦肩而過，也就是重新分組，中間值不再參與分組
        // 否則，在某些情況下，會進入死循環(huán)
        if (l == r) {
            l++;
            r--;
        }
        // 如果左側(cè)還可以繼續(xù)分組，則繼續(xù)快排
        // 由于擦肩而過了，那么左側(cè)的組值，則是最初的開始與中間值的前一個，也就是這里得到的 r
        if (left < r) {
            quickSort(arr, left, r);
        }
        if (right > l) {
            quickSort(arr, l, right);
        }
    }

    /**
     * 大量數(shù)據(jù)排序時間測試
     */
    @Test
    public void bulkDataSort() {
        int max = 80000;
//        int max = 8;
        int[] arr = new int[max];
        for (int i = 0; i < max; i++) {
            arr[i] = (int) (Math.random() * 80000);
        }
        if (arr.length < 10) {
            System.out.println("原始數(shù)組：" + Arrays.toString(arr));
        }
        Instant startTime = Instant.now();
//        processQuickSort(arr, 0, arr.length - 1);  // 和老師的原版代碼對比，結(jié)果是一樣的
        quickSort(arr, 0, arr.length - 1);
        if (arr.length < 10) {
            System.out.println("排序后：" + Arrays.toString(arr));
        }
        Instant endTime = Instant.now();
        System.out.println("共耗時：" + Duration.between(startTime, endTime).toMillis() + " 毫秒");
    }