快速排序

分治 + 填数

先从后向前找，再从前向后找

package com.ykk.StrategyFarm.CacheManager.Factor;

public class QuickSort {
    public static void main(String[] args) {
        int[] arr = {72, 6, 57, 88, 60, 42, 83, 73, 48, 85};

        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println("");

        sort(0, arr.length - 1, arr);
    }

    public static void sort(int start, int end, int[] arr) {
        if (start >= end) {
            return;
        }
        System.out.println("  " + start + " > " + end);
        int X = arr[start];
        int i = start;
        int j = end;
        while (i < j) {
            //从后向前
            for (; j > start && i < j; j--) {
                if (arr[j] < X) {
                    arr[i] = arr[j];
                    break;
                }
            }

            //从后向前
            for (; i < end && i < j; i++) {
                if (arr[i] > X) {
                    arr[j] = arr[i];
                    break;
                }
            }
        }
        arr[i] = X;

        for (int n = 0; n < arr.length; n++) {
            System.out.print(arr[n] + " ");
        }
        System.out.println("");

        sort(start, i - 1, arr);
        sort(i + 1, end, arr);
    }
}