QuickSort算法实现Java版

快速排序算法实现，实质是采用了递归算法（调用栈），对于数组排序，主要在于找到基线条件即数组剩余0或1个元素，这也是“分而治之“（D&W）的思想，早晨坐地铁看的颇有收获，总是尝试找到基线条件以及如何将问题规模缩小。几点总结如下：
1、D&C将问题逐步分解。使用D&C处理列表时，基线条件很可能是空数组或只包含一个元素的数组。
2、实现快速排序时，请随机地选择用作基准值的元素。快速排序的平均运行时间为O(n log n)。
3、大O表示法中的常量有时候事关重大，这就是快速排序比合并排序快的原因所在。
4、比较简单查找和二分查找时， 常量几乎无关紧要， 因为列表很长时， O(log n)的速度比O(n)快得多。

QuickSort代码实现如下：

/**
 * 快速排序
 * Kavin
 */
package com.algorithm.kavin;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import java.util.stream.Collectors;

public class QuickSort {

    public static List<Integer> quickSort(List<Integer> arr){
        if(arr.size() < 2){
            return arr;
        }else{
            int pivot = arr.get(0);
            List<Integer> result = new ArrayList<>();
            List<Integer> less = arr.stream().filter(x -> x < pivot ).collect(Collectors.toList());
            List<Integer> greater = arr.stream().filter(x -> x > pivot).collect(Collectors.toList());
            result.addAll(quickSort(less));
            result.add(pivot);
            result.addAll(quickSort(greater));
            return result;
        }
    }
    
    public static void main(String[] args) {
        List<Integer> test = new ArrayList<>();
        for(int i = 0; i < 50; i++){
            Integer num = new Random().nextInt(100);
            System.out.println("排序前");
            System.out.println(num);
            test.add(num);
        }
        
        for(int j : quickSort(test)){
            System.out.println("排序后");
            System.out.println(j);
        };
    }
}