小数组采用插入排序可以提高性能，若不能理解可以把这段改成：

 if (r - l <= 0) return;  

非递归写法：

    public static void quickSortNonRecursion(int[] arr) {
        Deque<Integer> stack = new ArrayDeque<>();
        // r
        stack.push(arr.length - 1);
        // l
        stack.push(0);
        // 每次从栈中取出两个元素，这辆个元素就是待排序区间的l..r
        while (!stack.isEmpty()) {
            int l = stack.pop();
            int r = stack.pop();
            if (l >= r) {
                // 当前子数组已经处理完毕
                continue;
            }
            int p = partition(arr,l,r);
            // 继续入栈两个子区间
            stack.push(p - 1);
            stack.push(l);

            stack.push(r);
            stack.push(p + 1);
        }
    }

    private static int partition(int[] arr, int l, int r) {
        // 1.优化1.使用一个随机位置作为分区点，避免快排在近乎有序数组上的性能退化
        int randomIndex = random.nextInt(l,r);
        swap(arr,l,randomIndex);
        int v = arr[l];
        // arr[l + 1..j] < v
        // 最开始区间没有元素
        int j = l;
        // arr[j + 1..i) >= v
        // 最开始大于区间也没有元素
        for (int i = l + 1; i <= r; i++) {
            if (arr[i] < v) {
                swap(arr,i,j + 1);
                j ++;
            }
        }
        // 此时元素j就是最后一个 < v的元素，就把v换到j的位置
        swap(arr,l,j);
        return j;
    }

二、Hoare挖坑法

目前市面上和教科书上的常用分区方法。

2.1 算法思想

1. 先从序列中随机选一个pivot，默认从最左边元素

2. 将两个索引 i 和 j 分别从左右两边开始往中间遍历

3. 先让 j 从后往前找到第一个 < v 的元素停止，把这个元素直接赋值给i所对应得元素。

4. 再让 i 从前往后找到第一个 > v 的元素停止

5. 当 i 和 j 重合时，arr[i] = pivot 即可~

没有元素交换的时候都是直接赋值，理论上会减少因为交换带来的时间损耗

    private static void quickSortInternalHoare(int[] arr, int l, int r) {
        // 2.小区间上使用插入排序来优化，不用递归到底
        if (r - l <= 15) {
            insertionSort(arr,l,r);
            return;
        }
        int p = partitionHoare(arr,l,r);
        // 继续在左右两个子区间进行快速排序
        // 所有 < v的元素
        quickSortInternalHoare(arr,l,p - 1);
        // 所有 >= v的元素
        quickSortInternalHoare(arr,p + 1,r);
    }

    /**
     * 挖坑分区法
     * @param arr
     * @param l
     * @param r
     * @return
     */
    private static int partitionHoare(int[] arr, int l, int r) {
        int randomIndex = random.nextInt(l,r);
        swap(arr,l,randomIndex);
        int pivot = arr[l];
        int i = l;
        int j = r;
        while (i < j) {
            // 先让j从后向前扫描到第一个 < v的元素停止
            while (i < j && arr[j] >= pivot) {
                j --;
            }
            arr[i] = arr[j];
            // 再让i从前向后扫描到第一个 > v的元素停止
            while (i < j && arr[i] <= pivot) {
                i ++;
            }
            arr[j] = arr[i];
        }
        arr[i] = pivot;
        return i;
    }