看快速排序的时候就猜我们会考一下双轴快排，所以了解一下原理，手动敲了一遍，用leetcode排序数组验证了一下。
除了时间很长，空间占用还很大，估计没啥别的问题（可是我还优化了QAQ）
下面👇开始讲思路：
对比单轴快速排序， 每次找到一个枢轴，大的放后边，小的放前边，直到left和right相遇，再将枢轴与中间值（就是代指枢轴那个数字应该呆的位置）的位置交换。
而双轴快排，我们相当于用两个轴，将大小分成三部分，类似于数轴，（-∞ ，privot1），（privot1，privot2），（privot，+∞）
显而易见我们的轴就是privot1，privot2
1⃣️选轴：对于一个数组，我们选取首尾两个数(nums[start],nums[end])分别为两轴，保证左轴小于右轴(nums[start]<nums[end])，（优化，对于一开始选取的两轴，如果相等，可以从第一个数往后寻找，到一个与末尾的数不相等的与第一个数交换，并且记得保持左轴小于右轴）
这里对于java里面选择是中间在向前向后走1/7个步长来选取两轴的优化，本篇文章不作解释
2⃣️划初始区间：我们分成3个区间，这时先将第一个数，中间的数，最后一个数看作三个区间。
设置left right 划定区间
int left = start; int right = end;
（nums[start],nums[left]),(nums[start+1]~nums[end-1]),(nums[right],nums[end])
有时间再来补图解，等我再次忘记咋写的时候 ahhhh
3⃣️优化初始区间：移动left 直到左边的数字不小于privot1，移动right直到右边的数字不大于privot2.
4⃣️k值移动：我们将k代表中间区间需要判断的数据起始位置。遍历过程中与我们两轴不断对比，进行适当交换。直到k大于等于right时停止。
重点：
对于nums[k]小于privot1时，将左区间扩充，先left++。将数据交换过去，对于left交换过来的会满足中间区间的条件，所以k随之加一；
对于nums[k]大于privot1并且小于privot2时，k++；即可；
对于nums[k]大于privot2时，将右区间扩充，这里将right—；将数据交换过去，对于当前交换到k位置的数据应继续判断，此时k不应该向后移动。
5⃣️结束k循环：k=right时，将privot1放到对应的left位置，将privot2放到对应的right位置。
6⃣️递归：对于划分好的三个区间，继续进行递归排序即可。
sort(nums,start,left-1); sort(nums,left+1,right-1); sort(nums,right+1,end);
完结！🎉，代码附下面：
//双轴快排 /** * Note: The returned array must be malloced, assume caller calls free(). */ int* sortArray(int* nums, int numsSize, int* returnSize){ int start,end,k,left,right; *returnSize = numsSize; start = 0; end = numsSize - 1; sort(nums,start,end); return nums; } void sort(int *nums,int start,int end) { if(start > end) return; int left = start; int right = end; if(nums[start] == nums[end]) { if(start == end) //这里当区间范围为1时要注意一下，我当时卡了好久，当时一个while死循环…… { // } else { for(int i = start;i < end;i++) { if(nums[i] != nums[end]) { swap(&nums[i],&nums[start]); break; //这里交换就应该跳出循环 } } } } if(nums[start] > nums[end]) { swap(&nums[start],&nums[end]); } int privot1 = nums[start]; int privot2 = nums[end]; while(left+1 <= end && nums[left+1] < privot1) { left++; } while(right-1 >= start && nums[right-1] > privot2) { right--; } //两步优化，但是这道题并没有提高什么效率 int k = left+1; while(k < right) { if(nums[k] < privot1) { left++; swap(&nums[left],&nums[k]); k++; } else if(nums[k] <= privot2) { k++; } else { right--; /* 由于一开始right就在end位置，不用再判断right是否要移动一下再交换，可能你看不懂我在说啥，但是我的确要在这里注释一下。 nums[right] = nums[end] */ swap(&nums[right],&nums[k]); } } swap(&nums[left],&nums[start]); swap(&nums[right],&nums[end]); sort(nums,start,left-1); sort(nums,left+1,right-1); sort(nums,right+1,end); // return nums; } void swap(int *a,int *b) { int t = *a; *a = *b; *b = t; }
