算法基础班–第一章–2.归并排序模板
算法模板(和快排一起记)
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;
while(i <= mid && j <= r)
if (q[i] < q[j]) tmp[k++] = q[i++];
else tmp[k++] = q[j++];
while(i <= mid) tmp[k++] = q[i++];
while(j <= r) tmp[k++] = q[j++];
for(int i = l, j = 0; i <= r; i++, j++) q[i] = tmp[j];
}
本题完整代码
#include <iostream>
const int N=1000010;
int n;
int q[N], tmp[N];
void merge_sort(int q[], int l, int r){ // [l,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; //i 左半边起点,j右半边起点,k 临时数组起点
while(i <= mid && j <= r) { // 当左右都没有循环空时
if (q[i] <= q[j]) tmp[k++] = q[i++];
else tmp[k++] = q[j++];
}
while(i <= mid) tmp[k++] = q[i++];
while(j <= r) tmp[k++] = q[j++];
for(int i = l, j = 0; i <= r; i++, j++) q[i] = tmp[j]; // 把临时数组tmp[]序列存回q[]序列中
}
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]);
}