快速排序的原理

partion原理图示

partion图示过程(这里 p 的位置默认是 0)

快速排序第一版

    public static <E extends Comparable<E>> void sort(E[] arr){
        //这个地方注意位置是arr.length-1
        sort(arr,0, arr.length-1);
    }
    private static <E extends Comparable<E>> void sort(E[] arr,int l,int r){
        if (l >= r) return;
        int p = partition(arr,l,r);
        sort(arr,l,p-1);
        sort(arr,p+1,r);
    }
    private static <E extends  Comparable<E>> int partition(E[] arr,int l , int r){
        //生成[l,r]之间的随机索引
        int p = l + (new Random()).nextInt(r-l+1);
        swap(arr,l,p);
        //arr[l+1,j] < v ;  arr[j+1,i-1] > v
        int j = l;
        for (int i = j+1; i <= r ; i++) {
            if (arr[i].compareTo(arr[l]) < 0){
                j++;
                swap(arr,i,j);
            }
        }
        //最后将第一个元素v,插入到<v和>v的位置中间
        swap(arr,l,j);
        return j;
    }

• 详细快速排序的过程:

第一版中的一系列问题

• 在完全有序的数组中，使用快速排序会栈溢出
  • 解决方案：为快速排序添加随机化
• 如果数组中的值全部相等，排序效率会大打折扣
  • 解决方案：重新设计partition函数(双路快速排序)

双路快速排序

• 引入原因：如果数组全部都有序，快速排序会退化成为一个O(n)的算法
• 原理：从两端出击，一直向中间挪
• 原理图示

三路快速排序算法

• 引入原因一样
• 原理图示

• 过程图示:

复杂度分析

作业

• 作业一：只new一次Random
• 作业二：不使用随机化来作为标定点，而直接取一半 swap(arr,l,(l+r)/2)。因此为ArrayGenerator添加一个方法，generateSpecialArray来为partition生成一个O(n2)级别的数组
• 作业3 : leetcode75、215、剑指Offer 40、面试题17.14