归并排序
归并排序可以理解为快排的反向，采用分治的思想，先排两边在用O(n)的时间合并在一起
代码（感觉比快排实现容易些）
#include<bits/stdc++.h>
using namespace std;
void merge(int a[],int l,int r){
int b[r-l+1],mid=(l+r)>>1,l1=0,r1=mid+1-l;
for(int i=l;i<=r;i++) b[i-l]=a[i];
for(int i=l;i<=r;i++){
if(r1+l>r) a[i]=b[l1++];
else if(l1+l>mid) a[i]=b[r1++];
else if(b[l1]>b[r1]) a[i]=b[r1++];
else a[i]=b[l1++];
}
}
void merge_sort(int a[],int l,int r){
if(l>=r) return ;
int mid=(l+r)>>1;
merge_sort(a,mid+1,r);
merge_sort(a,l,mid);
merge(a,l,r);
}
int main(){
int n;
int a[19993];
srand(time(0));
n=rand()%1000+1;
for(int i=0;i<n;i++)a[i]=rand()%100+1;
merge_sort(a,0,n-1);
for(int i=0;i<n;i++)cout<<a[i]<<endl;
}
投递字节跳动等公司8个岗位