快排优化的三种思路：
选择的轴枢元素，是否可以挑选的更好一些？
递归调用排序的时候，是否可以少一些调用？
partion操作是否可以优化一些？
一、基准值选取优化
如果基准值选取的不合理，可能会导致快排的时间复杂度达到O(n2) 这个量级，只有当基准值的选择刚好将数据进行平分的时候，时间复杂度才是O(nlogn)。
因为我们很难在一个无序的数组中，使用O(1)的时间复杂度找到可以把数组均分的基准值，那么有没有什么方法可以大概率找到这个值呢？
这个方法就是三点取中法
即在一个数组中，取数组的第一个元素，中间一个元素，最后一个元素，然后排序后，将中间值作为基准元素，然后对数组进行partiton操作。
如下图所示： 取5，2，8然后排序后： 2，5，8，以5作为基准元素然后进行数据partion操作。
三点取中法
代码实现：
说明： 查看之前快排的代码中partition部分
int pivot = nums[left];是将nums[left]作为了基准值，所以要将计算得出的中间值，赋值给基准值
// 1. 基准值选择优化
public static void baseValueChooseOptimize(int[] nums, int left, int right){
int pivot;
if(left < right) {
pivot = baseValueChoosePartition(nums, left, right);
baseValueChooseOptimize(nums, left, pivot-1);
baseValueChooseOptimize(nums, pivot+1, right);
}
}
public static int baseValueChoosePartition(int[] nums, int left, int right) {
//计算并获得3个数中，轴枢元素的坐标
// 获取中间元素的下标
int m = left + (right - left)/2;
if(nums[left] > nums[right]) { //保证左边较小
swap(nums, left, right);
}
if(nums[m] > nums[right]) {
swap(nums, m, right); //保证中间较小
}
if(nums[m] > nums[left]) { //保证左端是中间值
swap(nums, left, m);
}
// 为啥这里要用的是nums[left]呢？
// 因为快排开始执行的时候是将第一个元素作为轴枢元素开始分割的，需要将三个元素中，中间的那个放到left的位置上。
int pivot = nums[left];
System.out.println("基准值为：" + pivot);
while(left < right) {
while (left < right && nums[right] >= pivot) {
right--;
}
nums[left] = nums[right];
while (left < right && nums[left] <= pivot) {
left++;
}
nums[right] = nums[left];
}
nums[left] = pivot;
return left;
}
二、单边递归优化
看下图代码，每次完成一次partition操作后，就会对基准值左右两侧进行了递归调用，从程序运行的过程来看，每递归调用一次方法，都会有耗时。
快排递归调用
则考虑减少函数调用的方式，来缩短程序运行时间。
解决方法： 在每次完成partition操作后，直接在本层直接完成基准值左边的partition操作（需要一个循环），而基准值右边的操作，放到下一轮partition操作来完成。
代码示例：
// 2、单边递归优化
public void singleRecursionOptimize(int[] nums, int left, int right) {
int middle = 0;
while(left < right) {
middle = partition(nums, left, right);
// 对分界值分隔的两个数组;
// middle左边的数组在一个循环里，继续执行partion操作
// middle右边的数组在下一次递归中再进行调用。
quickSort(nums, middle+1, right);
right = middle -1;
}
}
三、partition操作优化
暂时没太理解，待后续补充...
详细代码见：algorithm_java
