c语言实现双轴快排—例题leetcode912

~~之前拿冒泡插入写的时候忘记复杂度很高了，白写了~~
~~后来用希尔/快速排序等又实现了一遍，上一篇博客里附两种代码~~

看快速排序的时候就猜我们会考一下双轴快排，所以了解一下原理，手动敲了一遍，用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;
}