思路解析

1）取最右侧的值为基准值base，从数组的左右两边分别开始查找，先从左往右找比基准值大的值，再从右往左找比基准值小的数，找到之后，将两个找到的数进行交换

2）在继续刚才的步骤，继续进行交换

3）直到left和right重合，就把重合的位置与基准值base交换

4）交换之后，原理的base就到了之前的重合位置，然后以这个数为分界线，分成左右两边，并对着两边的数组分别进行上述操作（递归）

代码示例

1）递归实现

 public static void quickSort(int[] array){
    //辅助完成递归过程
    quickSortHelper(array,0,array.length-1);
}

private static void quickSortHelper(int[] array, int left, int right) {
    if (left >= right){
        //区间中又0个元素或者1个元素，此时不需要排序 
        return;
    }
    int index = partition(array,left,right);//left和right的重合位置
    quickSortHelper(array,left,index-1);
    quickSortHelper(array,index + 1,right);
}

private static int partition(int[] array, int left, int right) {
    int i = left;
    int j = right;

    //取最右侧元素为基准值 
    int base = array[right];
    while (i < j){

        //从左往右找到比基准值大的元素 
        while (i < j && array[i] <= base){
            i++;
        }
        //当上面的循环结束时，i要么和j重合，要么i就指向一个大于base的值

        //从右往左找比基准值小的元素 
        while (i < j && array[j] >= base){
            j--;
        }
        //当上面的循环结束时，i要么和j重合，要么j就指向一个小于base的值

        //交换i和j的位置
        exchange(array,i,j);
    }
    //当i和j重合的时候，最后一步，要把重合位置的元素和基准值进行交换
    exchange(array,i,right);
    return i;
}

2）非递归实现（也与上述的思路分析一致）

public static void quickSortByLoop(int[] array){
    //借助栈，模拟实现递归的过程 
    //stack用来存放数组下标，通过下标来表示接下来要处理的区间是啥
    Stack<Integer> stack = new Stack<>();
    //初始情况下，先把右侧边界下标入栈，再把左侧边界入栈，左右边界仍然构成前闭后闭区间
    stack.push(array.length-1);//右侧
    stack.push(0);//左侧

    while (!stack.isEmpty()){
        int left = stack.pop();
        int right = stack.pop();
        if (left >= right){
            //区间中只有0个或1个元素，不需要整理 
            continue;
        }

        //通过partition把区间整理成以基准值为中心，左侧小于等于基准值，右侧大于等于基准值的形式 
        int index = partition(array,left,right);

        //准备一下区间 
        //[index=1,right]基准值右侧区间
        stack.push(right);
        stack.push(index+1);

        //[left,index+1]基准值左侧区间
        stack.push(index - 1);
        stack.push(left);
    }
}

性能分析

时间复杂度： 最好：O(n * log(n)) 平均：O(n * log(n)) 最坏：O(n^2)

空间复杂度： 最好：O(log(n)) 平均：O(log(n)) 最坏：O(n)

稳定性： 不稳定排序

注意事项

1）如果是是先从左往右找，再从右往左找，left和right重合位置的元素一定大于等于基准值； 如果是是先从右往左找，再从左往右找，left和right重合位置的元素一定小于等于基准值。

2）效率和基准值的好坏相关：基准值的是一个接近数组中位数的元素，划分出来的左右区间比较均衡，此时效率就比较高，如果当前取到的基准值是最大值或者最小值，此时的划分就不均匀，效率就低。

优化分析

1.优化基准值的取法：三个元素取中（最左侧元素，中间未知元素，最右侧元素）取中间基准值，把确认的基准值交换到数组末尾或者开始，为了后面整理动作做铺垫

2.当区间已经比较小的时候，再去递归其实效率已经不高了，不再继续递归，而是直接进行插入排序

3.如果区间特别大，递归深度也会非常深，当递归深度到达一定程度的时候，把当前区间的排序使用堆排序来进行优化