题目描述
blablabla
样例
#include<iostream>
using namespace std;
const int N = 100010;
int n;
int q[N], tmp[N]; //开一个这么大的数组
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 ++];//为了稳定,两边相同的时候,先选择 i,再选择 j
while(j <= r) tmp[k ++] = q[j ++];
for(i = l, j = 0; i <= r; i ++, j ++) q[i] = tmp[j]; //tmp的下标显然是从0开始的,但q我们有确定的边界,所以要这样写
}
int main(){
cin >> n;
for(int i = 0; i < n; i ++) cin >> q[i];
merge_sort(q, 0, n - 1);
for(int i = 0; i < n; i ++) cout << q[i] << " ";
return 0;
}
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla