一：前言
快速排序是冒泡排序的一种改进，在快速排序里是通过将待排序的list的第一个元素作为pivot，此时分为两块，一个是pivot变量，一个是挖空了第一个元素的list，然后对list进行排序时有点像数字华容道的玩法，只不过快速排序里是先从右边比较然后可以远程移动
元素到挖空区（已开始挖空区就是pivot元素在list中的位置）
二：原理
1.先将第一个元素作为pivot元素（最后一个也可以；中间的也可以但是需要将空位移动到最左或最右）；
2.假设是第一个元素为pivot元素，那么此时可以认为是list[0]里已经没有元素了，list[0]是一个缓冲区（根数字华容道的空块一样，再次强调此时记住就可以认为list[0]没有元素了，它是一个空位）；
3.假设是从小到大排列，先从list最右边开始取元素和pivot比较，如果该元素>=pivot那么说明它的顺序是不需要移动的，因此通过right--再继续往左取元素和pivot判断，直到list[right]<pivot或left<right（移动就是依靠left++和right--，且已经判断过的位置不需要再次判断，即left只能加，right只能减，最多left==right时要停下来这个是pivot的位置）
4.接3从右往左逐个判断的符合了left<right且list[right] < pivot，那么说明这个元素应该要放到左边的 空位/缓冲区，因此将此元素通过list[left] = list[right]来设置，且left++防止重复判断，注意，此时list[right]已经没有元素了，即list[right]会是新的缓冲区/空位（不要被代码误导，这个过程应该称为元素的移动）；
5.此时由于空位交换/移动到了右侧，因此需要从左侧开始判断了，此时经过了上面的left++已经来到了index=1的位置（即上一次移动到左边的元素不参与判断，即不重复判断），判断list[left]是否<=pivot，是则说明不需要移动它本来就是在pivot左边，然后循环left++直到left==right或list[left]>pivot；
6.此时list[left]>pivot，然后将list[left]移动到右边的空位，即上一次的list[right]的位置；
7.判断left==right，如果是则说明此躺根据pivot将list[left-right]分取结束，将pivot放入list[left]里（left==right）并return pivot的下标否则循环3-6；
8，外层根据返回的下标根据递归又对left - pivotIdx -1和pivotIdx + 1 - right进行同样的操作，直到最后pivot左右两边只有0或1个元素，即left<right不成立那么就对所有的子区间都进行了二分法的sort；
三：代码实现
package me.silentdoer.quicksort.tool; import java.util.List; /** * @author silentdoer * @version 1.0 * @description 快速排序的工具类，对外提供sort方法来实现对List的排序 * @date 4/25/18 8:26 PM */ public final class QuickSort { public static <E> void sort(List<Comparable> list){ qSort(list, 0, list.size() - 1); } private static <E> void qSort(List<Comparable> list, int left, int right){ if(left < right){ // 递归结束的条件 int pivotIdx = partition(list, left, right); // TODO 对切割后的两个区间再次进行binarySort/partition qSort(list, left, pivotIdx - 1); qSort(list, pivotIdx + 1, right); } } // 8 3 9 12 4 7 5 // TODO 这个有点像数字华容道，不过它是规定每个位置的元素最多只能移动一次（移动一次已经满足pivot左右分割了） // 1, 2, 3, 5, pivot is 1（注意left不一定就是0，二是根据qSort传入的值决定的） private static int partition(final List<Comparable> list, int left, int right){ // 将第一个元素摘出来作为枢轴元素（然后list[left]就已经空了，成为一个交换区/缓冲区） Comparable pivot = list.get(left); // TODO 此时list[left]元素值已经无关紧要，这时候不要把pivot理解为list[left]就看成是一把外来的尺子 while(true){ // TODO 防止最终left == right时还right--（left==right表示一趟binarySort完毕） while(left < right && list.get(right).compareTo(pivot) >= 0){ right--; } if(left < right){ // TODO 右边找到了right元素应该放到左边来 // TODO 说明存在list[right]的元素应该移动到左边的缓冲区里，此时list[right]就变成了缓冲区 list.set(left, list.get(right)); left++; // 防止重复判断（注意一次partition只需要将以pivot元素为界线将left-right区间的list分到两边即可，而不需要pivot两边的子表在此躺partition里就排好序 } while(left < right && list.get(left).compareTo(pivot) <= 0){ // 左边的元素比pivot要小，一直从左往右找到不符合pivot分隔规律的元素 left++; } if(left < right){ // 说明存在list[left]应该移动到右边的缓冲区里 list.set(right, list.get(left)); // 此时list[left]又变成了缓冲区 right--; // 防止重复判断 } // TODO 注意，这里用下面两种方式都可以，但是如果是set只是数组上的赋值那么用list[left] = pivot要更快，但是考虑到它是一个方法因此这种方式会快些 if(left == right){ list.set(left, pivot); break; } //list.set(left, pivot); // 最顶层while就要换成left<right } return left; } }
四：测试
package me.silentdoer.quicksort; import me.silentdoer.quicksort.tool.QuickSort; import java.util.Arrays; import java.util.List; /** * @author silentdoer * @version 1.0 * @description the description * @date 4/25/18 8:25 PM */ public class Entrance { public static void main(String[] args){ List list = Arrays.asList(1L, 8L, 22L, 4L, 90L, 36L, 1002L, 3L); System.out.println(list); System.out.println("<!-------------------------------------->"); QuickSort.sort(list); System.out.println(list); /* 输出 [1, 8, 22, 4, 90, 36, 1002, 3] <!--------------------------------------> [1, 3, 4, 8, 22, 36, 90, 1002] */ } }