快速排序算法实现，实质是采用了递归算法（调用栈），对于数组排序，主要在于找到基线条件即数组剩余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);
};
}
}
