快速排序

给定一个数组 [3, 5, 2, 1, 6, 2, 5, 8]

快速排序就是利用不停分割的思想将数组分块排序

首先选定一个基准，即key，这里一般选择最左边的，我们从两边开始移动指针分别找到小于基准和大于基准的数，进行交换

例如这个，left开始找到第一个大于3的数即5，right找到第一个小于3的数即2，进行交换

public int partition(int[] arr, int left, int right){
    int key = left;
    while(left < right){
        while(left < right && arr[right] > arr[key])
            right--;
        while(left < right && arr[left] < arr[key])
            left++;
        // swap请自行实现
        swap(arr[left], arr[right]);
     }
    swap(arr[key], arr[right]);
    return left;
}

之后对每次分的区进行再分区排序

public void quickSort(int[] arr, int left, int right){
    // 只有一个数就不用排序了
    if(left >= right)
        return;
    int key = partition(arr, int left, int right);
    quickSort(arr, left, key - 1);
    quickSort(arr, key + 1, right);
}