import java.util.Arrays;

/**
 * 快速排序-分治思想
 * 描述：选择一个基准数，小于基准数的都放在左边，大于基准数的都放在右边。递归直到全部有序。
 */
public class QuickSort {
    public static void main(String[] args){
        // 待排序数组
        int[] arr = {3, 1, 6, 2, 5, 8, 4};
        // 排序结果
        quickSort(arr, 0, arr.length-1);
        System.out.println(Arrays.toString(arr));
    }
    /**
     * 快速排序
     */
    public static void quickSort(int[] arr, int sPos, int ePos){
        if(sPos > ePos){
            return;
        }
        // 开始位置
        int start = sPos;
        // 结束位置
        int end = ePos;
        // 基准数设为开始位置对应值
        int key = arr[sPos];
        while(start != end){
            // 从后面开始与基准数比较
            while(end > start && arr[end] >= key){
                // 比基准值大，结尾位置前移，继续比较直到小于基准值
                end--;
            }
            // 从前面开始与基准数比较
            while(end > start && arr[start] <= key){
                // 比基准值大，开始位置后移，继续比较直到大于基准值
                start++;
            }
            // 交换两个值，比基准数大的放在右边，小的放在左边
            if(start < end){
                int temp = arr[start];
                arr[start] = arr[end];
                arr[end] = temp;
            }
        }
        // 基准值放在中间
        arr[sPos] = arr[start];
        arr[start] = key;
        // 基准数左边的快排
        quickSort(arr, sPos, start - 1);
        // 基准数右边的快排
        quickSort(arr, start + 1, ePos);
    }
}