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

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

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

            // 當(dāng)左側(cè)與右側(cè)相碰時(shí)，說(shuō)明兩邊都沒(méi)有找到，這一輪不用進(jìn)行交換
            // 等于表示，找到了中間的下標(biāo)
            if (l >= r) {
                break;
            }

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

            // 當(dāng)交換后，
            // 當(dāng)數(shù)組是： {-9, 78, 0, -23, 0, 70}  時(shí)（pivot的值在數(shù)組中有多個(gè)），就可以驗(yàn)證這里的邏輯
            // 如果沒(méi)有這個(gè)判定，將會(huì)導(dǎo)致，l 永遠(yuǎn) 小于 r。循環(huán)不能退出來(lái)的情況，就出現(xiàn)死循環(huán)了
            if (arr[l] == pivot) {
                /*
                  l 自己不能往前移動(dòng) 一步，因?yàn)楫?dāng)交換完成后為：{-9, 0, 0, -23, 78, 70}
                  l = 1,arr[l] = 0
                  r = 4,arr[r] = 78
                  再經(jīng)過(guò)一次循環(huán)后
                  l = 1,arr[l] = 0
                  r = 3,arr[r] = -23
                  交換后數(shù)組為：{-9，-23，0，0，78，70}
                  此時(shí) l = 1，arr[l] = -23;r = 3,arr[r] = 0
                  又經(jīng)過(guò)一次循環(huán)后
                  l = 2,arr[l] = 0
                  r = 3,arr[r] = 0
                  數(shù)組為：{-9，-23，0，0，78，70}
                  進(jìn)入了死循環(huán)
                  這里好好動(dòng)腦子想想
                  
                  這里為什么是用r-=1呢？是因?yàn)閕f里面的條件是arr[l] == pivot，如果要排序的數(shù)組中不存在多個(gè)和基準(zhǔn)值相等的值，
                  那么用l+=1的話(huà)，l就會(huì)跑過(guò)分界線(xiàn)（基準(zhǔn)值），跑到另一組去，這個(gè)算法也就失敗了，
                  還有一個(gè)原因是，r 是剛剛交換過(guò)的，一定比 基準(zhǔn)值大，所以沒(méi)有必要再和基準(zhǔn)值比較了
                 */
                r -= 1;
            }
            // 這里和上面一致，如果說(shuō)，先走了上面的 r-=1
            // 這里也滿(mǎn)足（也就是說(shuō)有多個(gè)值和基準(zhǔn)值相等），那么說(shuō)明，下一次是相同的兩個(gè)值，一個(gè)是 r == 一個(gè)是基準(zhǔn)值
            // 但是他們是相同的值，r后退一步 l前進(jìn)一步，不影響。但是再走這完這里邏輯時(shí)，就會(huì)導(dǎo)致  l > r，退出整個(gè)循環(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)從這條代碼中跳出就會(huì)l = r
		*/
        // 如果 l = r，會(huì)出現(xiàn)死循環(huán)，出現(xiàn)棧溢出
		//這里也要?jiǎng)幽X子想想
        if (l == r) {
            l++;
            r--;
        }

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

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

  /**
     * 快速排序默寫(xiě)實(shí)現(xiàn)
     * 
     *     基本思想：通過(guò)一趟將要排序的數(shù)據(jù)，分隔成獨(dú)立的兩個(gè)部分，一部分的所有數(shù)據(jù)都比另一部分的所有數(shù)據(jù)要小。
     *     思路分析：
     *      {-9, 78, 0, 23, -567, 70};  length=6
     *      1. 挑選中間的值作為 基準(zhǔn)值：(0 + (6 -1))/2= [2] = 0
     *      2. 左側(cè) left 部分，從 0 開(kāi)始到中間值 -1： 0,1: -9, 78,找出一個(gè)比基準(zhǔn)值大的數(shù)
     *      3. 右側(cè) right 部分，從中間值 + 1 到數(shù)組大小-1：3,5：23,-567, 70，找出一個(gè)比基準(zhǔn)值小的數(shù)
     *      4. 如果找到，則將他們進(jìn)行交換，這樣一輪下來(lái)，就完成了一次快速排序：一部分的所有數(shù)據(jù)都比另一部分的所有數(shù)據(jù)要小。
     *      4. 如果左側(cè)部分還可以分組，則進(jìn)行左側(cè)遞歸調(diào)用
     *      5. 如果右側(cè)部分還可以分組，則進(jìn)行右側(cè)遞歸調(diào)用
     *
     *    簡(jiǎn)單說(shuō)：一輪快速排序示意圖如下：
     *                   中間的基準(zhǔn)值
     *      l ------------ pivot --------------- r
     *      一組從左往右找               一組從右往左找
     *      找到比基準(zhǔn)值大的數(shù)          找出一個(gè)比基準(zhǔn)值小的數(shù)
     *                    然后進(jìn)行交換
     * 
     */
    @Test
    public void quickSortTest() {
        int arr[] = {-9, 78, 0, 23, -567, 70};
//        int arr[] = {-9, 78, 0, -23, 0, 70}; // 在推導(dǎo)過(guò)程中，將會(huì)導(dǎo)致交換異常的數(shù)組，在這里不會(huì)出現(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) {
            // 從左往右找，直到找到一個(gè)數(shù)，比基準(zhǔn)值大的數(shù)
            while (arr[l] < pivot) {
                l++;
            }
            // 從右往左找，知道找到一個(gè)數(shù)，比基準(zhǔn)值小的數(shù)
            while (arr[r] > pivot) {
                r--;
            }
            // 表示未找到
            if (l >= r) {
                break;
            }
            // 進(jìn)行交換
            int temp = arr[l];
            arr[l] = arr[r];
            arr[r] = temp;

            // 那么下一輪，左側(cè)的這個(gè)值將不再參與排序，因?yàn)閯偨粨Q過(guò)，一定比基準(zhǔn)值小
            // 那么下一輪，右側(cè)的這個(gè)值將不再參與排序，因?yàn)閯偨粨Q過(guò)，一定比基準(zhǔn)值大
            r--;
            l++;
        }

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

    /**
     * 大量數(shù)據(jù)排序時(shí)間測(cè)試
     */
    @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);  // 和老師的原版代碼對(duì)比，結(jié)果是一樣的
        quickSort(arr, 0, arr.length - 1);
        if (arr.length < 10) {
            System.out.println("排序后：" + Arrays.toString(arr));
        }
        Instant endTime = Instant.now();
        System.out.println("共耗時(shí)：" + Duration.between(startTime, endTime).toMillis() + " 毫秒");
    }