Leetcode题库75. 颜色分类(二路归并 C实现)

• 思路
• 代码

二路归并直接莽 二路归并讲解

//有序数组调整
void Array_Merge(int* head,int low,int high,int* head1,int low1,int high1,int L,int Step_L,int Bool){

    int Temp[((high-low)/Step_L+1)+((high1-low1)/Step_L+1)];
    int i=0,j=low,k=low1;
    if(Bool){
        while(i<((high-low)/Step_L+1)+((high1-low1)/Step_L+1) && (j<=high || k<=high1)){
            if(k>high1){
                Temp[i]=head[j];
                j+=Step_L;
                i++;
                continue;
            }
            if(j>high){
                Temp[i]=head[k];
                k+=Step_L;
                i++;
                continue;
            }
            if(head[j]<=head1[k]){
                Temp[i]=head[j];
                j+=Step_L;
            }
            else{
                Temp[i]=head[k];
                k+=Step_L;
            }
            i++;
        }
    }
    else{
        while(i<((high-low)/Step_L+1)+((high1-low1)/Step_L+1)  && (j<=high || k<=high1)){
            if(k>high1){
                Temp[i]=head[j];
                j+=Step_L;
                i++;
                continue;
            }
            if(j>high){
                Temp[i]=head[k];
                k+=Step_L;
                i++;
                continue;
            }
            if(head[j]>=head1[k]){
                Temp[i]=head[j];
                j+=Step_L;
            }
            else{
                Temp[i]=head[k];
                k+=Step_L;
            }
            i++;
        }
    }
    
    i=0;
    while(i<((high-low)/Step_L+1))
    {
        head[low+i*Step_L]=Temp[i];i++;}
    
    while(i<((high-low)/Step_L+1)+((high1-low1)/Step_L+1))
    {
        head1[low1+(i-((high-low)/Step_L+1))*Step_L]=Temp[i];i++;}
}



//二路归并排序
void Mer_Sort(int* head,int low,int high,int Step_L,int Bool){
    int Shigh=low+(((high-low+1)/Step_L)-1+(((high-low+1)%Step_L)!=0))*Step_L;
    int L=(Shigh-low)/Step_L+1;
    if(L>2){
        Mer_Sort(head,low,low+((L+1)/2-1)*Step_L,Step_L,Bool);
        Mer_Sort(head,low+(((L+1)/2-1)+1)*Step_L,Shigh,Step_L,Bool);
    }
    if(L>1)Array_Merge(head,low,low+((L+1)/2-1)*Step_L,head,low+(((L+1)/2-1)+1)*Step_L,Shigh,L,Step_L,Bool);
}

void sortColors(int* nums, int numsSize){
    Mer_Sort(nums,0,numsSize-1,1,1);
    return nums;
}