一个小问题

poppingW @ 2023-06-28 10:03:07

by RP_INT_MAX @ 2023-06-28 10:13:08

@S05251 似乎可以。开两倍空间就行。（？）

by RP_INT_MAX @ 2023-06-28 10:13:33

下标的处理比双数组稍麻烦。

by _Haoomff_ @ 2023-06-28 10:35:56

@S05251 @RP_INT_MAX 我就用的归并，数组不用开双倍

by _Haoomff_ @ 2023-06-28 10:37:21

不过跑得有点慢

by N_z_ @ 2023-06-28 10:51:17

@S05251 搜索原地归并排序即可

void reverse(int *arr,int n)
{
    int i=0,j=n-1;
    while(i<j)
    {
        std::swap(arr[i],arr[j]);
        i++;
        j--;
    }
}

void exchange(int *arr,int n,int i) 
{
    reverse(arr,i);
    reverse(arr+i,n-i);
    reverse(arr,n);
}

void merge(int *arr,int begin,int mid,int end)
{
    int i=begin,j=mid+1,k=end;
    while(i<j && j<=k)
    {
        int step=0;
        while(i<j && arr[i]<=arr[j])
            i++;
        while(i<j && arr[j]<=arr[i])
        {
            j++;
            step++;
        }

        exchange(arr+i,j-i,j-i-step);
        i+=step;
    }
}

by chen_z @ 2023-07-15 09:20:08

管理楼下祭