找一个基准值base，然后一趟排序后让base左边的数都小于base，base右边的数都大于等于base。再分为两个子数组的排序。如此递归下去。

在数组几乎有序时，快排性能不好（因为每趟排序后，左右两个子递归规模相差悬殊，大的那部分最后很可能会达到O(n^2)）。

解决：基准值随机地选取，而不是每次都取第一个数。这样就不会受“几乎有序的数组”的干扰了。但是对“几乎乱序的数组”的排序性能可能会稍微下降，至少多了排序前交换的那部分，乱序时这个交换没有意义...有很多“运气”成分..

快排是不断减小问题规模来解决子问题的，需要不断递归。但是递归到规模足够小时，如果继续采用这种 不稳定+递归 的方式执行下去，效率不见得会很好。

所以当问题规模较小时，近乎有序时，插入排序表现的很好。Java自带的Arrays.sort()里经常能看到这样的注释：“Use insertion sort on tiny arrays”，“Insertion sort on smallest arrays”

在最开始的普通快速排序说过，让基准值base左边的都比base小，而base右边的都大于等于base。等于base的这些会聚集到右侧(或者稍微改改大小关系就会聚集到左侧)。总之就会聚集到一边。这样在数组中重复数字很多的时候，就又会导致两边子递归规模差距悬殊的情况。这时想把等于base的那些数分派到base两边，而不是让他们聚集到一起。

（注：测试代码的时候，最好把插入排序那部分注视掉，向我下面代码中那样...不然数据量小于k=16的时候执行的是插入排序.....）

上面的两路在找到大于base的值和小于base的值时，用的是swap()方法来进行交换。两数交换涉及到第三个变量temp的操作，多了读写操作。接下来用直接赋值的方法，把小于的放到右边，大于的放到左边，当i和j相遇时，那个位置就是base该放的地方。至此一趟完成。递归即可。

把数组分为三路，第一路都比base小，第二路都等于base，第三路都大于base。

用指针从前到后扫描，如果：

1.cur指向的数小于base，那么：交换arr[cur]和arr[i]的值，然后i++,cur++。

2.cur指向的数等于base,  那么：cur++

3.cur指向的数大于base，那么：交换arr[cur]和arr[j]的值，然后j--。

当cur > j的时候说明三路都已经完成。