思路

1. 从数组中选取一个基准值，然后把比基准值小的都放在其左边，比基准值大的都放在右边，如果相同放任意一边都可
2. 根据基准值就可以把一个数组拆分成两个数组，然后再对这两个数组再进行上述操作
3. 最后就可以得到有序数组了

Code

public class QuickSort {
    public void sort(int[] arr) {
        sort(arr, 0, arr.length - 1);
    }

    private void sort(int[] arr, int start, int end) {
        //起始位置大于等于结束位置，则返回
        if (start < end) {
            //找到基准值的索引
            int partitionIndex = getPartitionIndex(arr, start, end);
            //根据基准值索引，拆分数组
            //对基准值左边数组进行递归
            sort(arr, start, partitionIndex - 1);
            //对基准值右边数组进行递归
            sort(arr, partitionIndex + 1, end);
        }
    }

    private int getPartitionIndex(int[] arr, int start, int end) {
        //定义一个基准值，默认去起始位置处的值
        int partitionNum = arr[start];
        int i = start;
        int j = end;
        //起始位置大于等于结束位置，则循环结束
        while (i < j) {
            //从右向左找到第一个比基准值小的值的索引
            while (arr[j] >= partitionNum && i < j) {
                j--;
            }
            //从左向右找到第一个比基准值大的值的索引
            while (arr[i] <= partitionNum && i < j) {
                i++;
            }
            //交换两个索处出的值
            swap(arr, i, j);
        }
        //用基准值对数组记性划分
        swap(arr, start, i);
        return i;
    }

    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

时间复杂度：O(nlogn)

空间复杂度：O(logn)

稳定性：不稳定