原题链接

https://www.acwing.com/problem/content/description/789/

2021/4/19 21:10

思路

• 先分开，分成俩个组
• 用双指针遍历，小的放入tmp数组
• 如果有剩余，把剩余放入tmp数组
• 把tmp的数据替换到q数组中

后续会更新

#include <iostream>

using namespace std;

const int N = 1000010;

int n;
int q[N],tmp[N];

void merge_sort(int *q,int l ,int r)
{
  if(l >= r) return ;

  int mid = l + r >> 1;

  merge_sort(q, l, mid),merge_sort(q, mid+1, r);      // 分左边右边，俩组数据

  int k = 0,i = l,j = mid + 1;        // k表示，tmp当前放入的第几个数

  while(i <= mid&&j <= r)   // 俩组数据比较大小，双指针算法，小的放入tmp
    if(q[i] <= q[j]) tmp[k ++ ]=q[ i ++];
    else tmp[k ++] = q[j ++];

  while(i <= mid) tmp[k ++] = q[i ++];      //把剩余的数据放进tmp，从tmp[k]开始放
  while(j <= r) tmp[k ++] = q[j ++];

  for(int i=l,j=0;i<=r;i++,j++) q[i]=tmp[j];  //把q的数据换成tmp的数据

}
int main()
{
  scanf("%d",&n);
  for(int i=0;i<n;i++)
    scanf("%d",&q[i]);

  merge_sort(q,0,n-1);

  for(int i=0;i<n;i++)
    printf("%d ",q[i]);

    return 0;
}