快速排序 (Quick Sort)

public static void main(String[] args) {
    int[] arr = {9, 5, 7, 3, 1, 6, 8, 4, 2};
    quickSort(arr,0,arr.length - 1);
}

private static void quickSort(int[] arr, int left, int right) {
    if (left >= right) {
        return;
    }
    //先排序一遍，再递归拆分，和归并有区别，归并是先拆分，再合并排序
    int partition = partition(arr, left, right);//排序完找到前一趟基准值下标，作为左右数组的左右边界
    System.out.println(Arrays.toString(arr));
    quickSort(arr,left,partition - 1);//基准位置已经排序，不用向归并一样参加排序
    quickSort(arr,partition + 1,right);//基准位置已经排序，不用向归并一样参加排序


}

private static int partition(int[] arr, int left, int right) {
    //数组的第一个元素作为基准值
    int pivot = arr[left];
    int i = left;
    int j = right;
    int temp = 0;
    while (i < j) {
        //从右边开始找，找到小于基准值的数
        //跳出循环说明要么找到小于基准值的，要么就是j和i重了
        while (i<j && arr[j] >= pivot) {
            j--;
        }
        //从左边开始找，找到大于基准值的数
        //跳出循环说明要么找到小于基准值的，要么就是j和i重了
        while (i < j && arr[i] <= pivot) {
            i++;
        }
        //找到就开始替换，替换完毕开始下一轮找，直至拆分的数组左右都替换完成
        if (i < j) {
            temp = arr[j];
            arr[j] = arr[i];
            arr[i] = temp;
        }
    }
    //此时基准值还没动，所以把基准值放到指定位置
    temp = arr[i];//这里的i和j是重合的,所以用i和j都可以
    arr[i] = arr[left];//这里为什么是替换left下标,因为上面的循环中,我们是从小到大的顺序排序,i的位置一定是小于基准值的
    arr[left] = temp;
    return i;
}