sort在这里太慢了，O（rnlogn）会超时
by memseter @ 2023-08-16 15:32:25
用暴力+归并
by Dait_sat @ 2023-08-17 16:35:43
```sort```时间有点长，可以自己写```merge_sort```，归并排序时间还可以。
```cpp
void mergee(long long first,long long last,long long chart[],long long size){
long long *temp=new long long[size];
if(first>=last){
return;
};
long long middle=(first+last)/2;
long long lower=first,upper=middle+1,tot=first;
while(lower<=middle&&upper<=last){
if(chart[lower]<=chart[upper]){
temp[tot++]=chart[lower];
lower++;
}else{
temp[tot++]=chart[upper];
upper++;
};
};
while(lower<=middle){
temp[tot++]=chart[lower];
lower++;
};
while(upper<=last){
temp[tot++]=chart[upper];
upper++;
};
for(int it=first;it<=last;it++){
chart[it]=temp[it];
};
return;
};
void mergesort(long long first,long long last,long long chart[],long long size){
if(first<last){
int middle=(first+last)/2;
mergesort(first,middle,chart,size);
mergesort(middle+1,last,chart,size);
mergee(first,last,chart,size);
};
};
```
~~自己没试过自己写的归并，有些问题，现在还没找出来。~~
by Kapo_Hisy @ 2023-08-21 19:37:23
快速排序+归并排序：
```cpp
void merges_sort(int first,int last,int *list){
if(first==last){
return;
};
int middle=(first+last)/2;
merges_sort(first,middle,list);
merges_sort(middle+1,last,list);
int left=first;
int right=middle+1;
int *temp=new int[last+1];
for(int iter=first;iter<=last;++iter){
if((right>last)||(left<=middle&&list[left]<=list[right])){
temp[iter]=list[left];
++left;
}else{
temp[iter]=list[right];
++right;
};
};
for(int iter=first;iter<=last;iter++){
list[iter]=temp[iter];
};
};
void faster_sort(int first,int last,int *list){
int left=first;
int right=last;
int key=list[left];
while(left!=right){
while(left<right&&list[right]>=key){
--right;
};
list[left]=list[right];
while(left<right&&list[left]<=key){
++right;
};
list[right]=list[left];
};
list[left]=key;
};
```
by Kapo_Hisy @ 2023-08-21 20:06:08