本文内容:本文重要学习和掌握归并排序的思想以及实现
#include "iostream"
#include "algorithm"
using namespace std;
const int N = 1e6+10;
int q[N];
int tmp[N];
void mergeSort(int l,int r){
if(l >= r) return;
int mid = (l + r) / 2;
mergeSort(l,mid);
mergeSort(mid+1,r);
int i = l,j = mid + 1;
int cnt = 0;
while(i <= mid && j <= r){
if(q[i] < q[j]){
tmp[cnt++] = q[i++];
}else{
tmp[cnt++] = q[j++];
}
}
while(i <= mid){
tmp[cnt++] = q[i++];
}
while(j <= r){
tmp[cnt++] = q[j++];
}
for(int i = l,j = 0; i <= r; i++,j++){
q[i] = tmp[j];
}
}
int main(){
int n;cin >> n;
for(int i = 0; i < n; i++){
cin >> q[i];
}
mergeSort(0,n-1);
for(int i = 0; i < n; i++){
cout << q[i] << ' ';
}
return 0;
}
通过上面的图,将归并排序的整个流程走了一遍,归并的实质在于先分割到不能分割为止再合并,
合并的过程就是,将两个区间中的元素按照一定的规则放到另一个容器中,最后再将这个容器中的值复制到对应的结果集中。
易错的点在于归并的时候,将结果复制到结果集时,要按照对应的顺序进行复制,这是为什么?
在归并的时候实际上位置并没有发生改变,只是你需要把位置上的数重排序在放回到原来的位置