笔记：排序----经典快排

快速排序的一次划分算法从两头交替搜索，直到left和right重合，因此其时间复杂度是O(n)；而整个快速排序算法的时间复杂度与划分的趟数有关。

理想的情况是，每次划分所选择的中间数恰好将当前序列几乎等分，经过logn趟划分，便可得到长度为1的子表。这样，整个算法的时间复杂度为O(nlogn)

最坏的情况是，每次所选的中间数是当前序列中的最大或最小元素，这使得每次划分所得的子表中一个为空表，另一子表的长度为原表的长度-1。这样，长度为n的数据表的快速排序需要经过n趟划分，使得整个排序算法的时间复杂度为O(n^2)

但是经过证明，快速排序的平均时间复杂度也是O(nlogn)。因此，该排序方法被认为是目前最好的一种内部排序方法。

从空间性能上看，尽管快速排序只需要一个元素的辅助空间，但快速排序需要一个栈空间来实现递归。最好的情况下，即快速排序的每一趟排序都将元素序列均匀地分割成长度相近的两个子表，所需栈的最大深度为log(n+1)；但最坏的情况下，栈的最大深度为n。这样，快速排序的空间复杂度为O(logn)。

代码如下：

/**
 *快速排序
 *时间复杂度：--O(nlogn)
 */
public class QuickSortDemo {

    public static void main(String[] args) {
        int[] nums = new int[10];
        Random random = new Random();
        for (int i = 0; i < 10; i++) {
            nums[i] = random.nextInt(100);
        }
        System.out.println(Arrays.toString(nums));
        System.out.println("------------");

        quickSort(nums, 0, nums.length - 1);  //调用方法
        
        System.out.println(Arrays.toString(nums));
    }

    /**
     *
     * @param nums 需要排序的数组
     * @param start 开始位置
     * @param end 结束位置
     */
    private static void quickSort(int[] nums, int start, int end) {
        if (start < end) {
            int base = nums[start]; //设定基准数
            int l = start, r = end;//记录左右开始位置
            while (l < r) {
                //移动r
                while (nums[r] > base && l < r) { //r开始移动，如果r位置大于基准数，则不交换并移动r位置
                    r--;
                }
                nums[l] = nums[r]; //把r位置数放到l位置

                //移动l
                while (nums[l] < base && l < r) { //现状l开始移动，如果l位置小于基准数，则不交换并移动l位置
                    l++;
                }
                nums[r] = nums[l]; //将l位置数放到r位置
            }
            //这时l==r了，退出循环，将基准数放在l位置上（l和r实际上是相同的数字，所以写哪个都无所谓）
            nums[l] = base;

            //一轮结束，开始递归
            //左边
            quickSort(nums,start,l);
            //右边
            quickSort(nums,l+1,end);
        }
    }
}