归并排序+快速排序（可直接复制）
2023-07-25 16:03:09
发布于：广东
9阅读
0回复
0点赞
归并排序
// 将a数组的 [L1,R1] 和 [L2,R2] 区间元素进行归并
void merge(int a[],int L1,int R1,int L2,int R2){
int i=L1,j=L2,cnt=0;
// 两个范围都没有越界
while(i<=R1&&j<=R2){
if(a[i] <= a[j]) tmp[cnt++] = a[i++];
else tmp[cnt++] = a[j++];
}
// 前半段还有元素
while(i<=R1) tmp[cnt++] = a[i++];
// 后半段还有元素
while(j<=R2) tmp[cnt++] = a[j++];
// 将数组 tmp(0~cnt-1) 复制到数组 a(L1,R2)
for(int i=0;i<cnt;i++){
a[L1+i] = tmp[i];
}
}
// 将数组 a 区间 [l,r] 的元素进行升序排列
void MergeSort(int a[],int l,int r){
// 只有一个元素，无法再划分，返回
if(l>=r){
return;
}
// 求中间元素位置
int mid = (l+r)/2;
// 对前半段 [l,mid] 继续递归划分
MergeSort(a,l,mid);
// 对后半段 [mid+1,r] 继续递归划分
MergeSort(a,mid+1,r);
// 归并区间 [l,mid] 和 [mid+1,r] 的元素
merge(a,l,mid,mid+1,r);
}
快速排序
void QuickSort(int a[],int l,int r){
if(l>=r){
return;
}
int key=a[(l+r)/2],i=l,j=r; // key选中间元素 i指向第一个位置 j指向最后一个位置
// 通过这样一个while就可以将<=key的放在l~i-1 >=key的放在i~r
while(i<=j){
while(a[j]>key) j--; // 从右向左找到第一个<=key的
while(a[i]<key) i++; // 从左向右找到第一个>=key的
if(i<=j){
swap(a[i],a[j]);
i++;j--;
}
QuickSort(a,l,i-1);
QuickSort(a,i,r);
}
}
这里空空如也
有帮助，赞一个