算法图解中对快速排序的分析（Java）

快速排序的基本原理如下

对于这样一个数组，相对它进行快速排序

排序的基本原理如下图：任意选择一个元素作为基准值，对基准值进行如下情况的递归操作，这里以正序排序举例：即将小于基准值的数放在基准值左边，比基准值大的值放在其右边，再依次对左右两边的数组进行同理的操作，这里取基准值有以下五种方式，分别得到五种可能出现的左中右组合！

例如，假设你将3用作基准值，可对得到的子数组进行快速排序。

对于原本已经排好序的数组，如果用取第一个值作为基准值的方式来计算的话，会出现下面的情况

但是如果选择以中间的数作为基准数来计算的话就可以得到最优情况，这在排序算法里面也称为平均情况和最糟情况，下面展示一下最优情况；

其实，最佳情况也是平均情况。只要你每次都随机地选择一个数组元素作为基准值，快速排序的平均运行时间就将为O(n log n)。 下面是我使用Java实现的快速排序算法代码

    public static void main(String[] args) {
        List list = new ArrayList<>();
        for (int i = 0; i < 10000; i++) {
          list.add(new Random().nextInt(100000));
//            list.add(i);
        }
        StopWatch watch = new StopWatch();
        watch.start();
        System.out.println("开始执行.....");
        // 业务逻辑代码...
        System.out.println(quicklySort(list));
        watch.stop();
        System.out.println("Time Elapsed: " + watch.getTime() + "ms"); // 单位为毫秒
        System.out.println(time);
    }

    private static int time = 0;
    private static List quicklySort(List list) {
        if (list.size() < 1) {
            return list;
        }
        // 随机选择一个元素作为基准值
        int randomInt = new Random().nextInt(list.size());
//        int randomInt = list.size() / 2;
//        int randomInt = 0;
        Integer mid = list.get(randomInt);
        List leftElement = new linkedList<>();
        List rightElement = new linkedList<>();
        for (int i = 0; i < list.size(); i++) {
            if (i == randomInt){
                continue;
            }
            time++;
            if (list.get(i) < mid) {
                leftElement.add(list.get(i));
            }else{
                rightElement.add(list.get(i));
            }
        }
        List newList = new ArrayList<>(list.size());
        newList.addAll(quicklySort(leftElement));
        newList.add(mid);
        newList.addAll(quicklySort(rightElement));
        return newList;
    }

对于每次随机取元素作为基准值的时候，对一万个随机元素进行排序，执行14万次循环，通过平均情况可以计算出程序应当是执行10000 * Log2（10000）= 13万次左右，可见随机选择元素是无限接近于平均情况的，相对于每次都取中间的数作为基准值，其实也是接近于13万次，但是综合衡量，其实还是随机选取基准值更稳定，虽然相差不多，但心里还是觉得挺稳定的。