归并排序
又称合并排序，其核心是分治思想。分治法详细请看百度百科
《算导》p20：分治法中的递归式是基于基本模式中的三个步骤的。如先前一样，设T(n)为一个规模为n的问题的运行时间。如果问题的规模足够地小，如n≤c（c为一个常量），则得到它的直接解的时间为常量，写作Θ(1)。假设我们把原问题分解成a个子问题，每一个的大小是原问题的1/b。（对于合并排序，a和b都是2，但在许多分治法中，a≠b。）如果分解该问题和合并解的时间各为D(n)和C(n)，则得到递归式：
我们则知道，归并时间复杂度是Θ(n lg n)的了（具体看算导p20-p22）
上我自己的代码
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
#define WHI(i,a,n) for(i=(a);i<(n);++i)#define REP(i,a,n) for(int i=(a);i<(n);++i)const
int
MAXi = 1e5+10, oo = ~0u>>1;
int
L[MAXi], R[MAXi];
void
merge_sort(int* arr, int
f, int
l){
if(f < l-1){
int
m = (f+l) >> 1, i = 0, j = 0;
merge_sort(arr, f, m);
merge_sort(arr, m, l);
WHI(i, 0, m-f) L[i] = arr[f+i];
WHI(j, 0, l-m) R[j] = arr[m+j];
L[i] = R[j] = oo; i = j = 0;
while(f < l)
arr[f++] = L[i] < R[j] ? L[i++] : R[j++];
}
} |
霍纳规则（法则）
即“秦九韶方法” 用来计算多项式我们用D(i)来表示
可推出
顺推：
答案是D(n)
逆推： 答案是D(0)
很容易看出可以用滚动求值，即D = a(n-1) + x * D 或 D = a(i) + x * D
代码
|
1
2
3
4
5
6
|
//顺推for(int
i = 0, D = 0; i <= n; ++i)
D = a[n-i] + x * D;
//逆推for(int
i = n, D = 0; i >= 0; ++i)
D = a[i] + x * D;
|
统计逆序对
含义：对于一个包含N个非负整数的数组A[1..n]，如果有i < j，且A[ i ]>A[ j ]，则称(A[ i] ,A[ j] )为数组A中的一个逆序对。例如，数组（3，1，4，5，2）的逆序对有(3,1),(3,2),(4,2),(5,2)，共4个。
很快就能用插入排序来统计，但O(n^2)咱们不采用，咱们用O(n lg n)的归并啦 >_<
代码
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
#define WHI(i,a,n) for(i=(a);i<(n);++i)#define REP(i,a,n) for(int i=(a);i<(n);++i)const
int
MAXi = 1e5+10, oo = ~0u<<1;
typedef
unsigned long
long
ull;
ull cnt;int
L[MAXi], R[MAXi];
void
mi_cnt(int* arr, int
f, int
l){
if(f < l-1){
int
m = (f+l) >> 1, i = 0, j = 0;
mi_cnt(arr, f, m);
mi_cnt(arr, m, l);
WHI(i, 0, m-f) L[i] = arr[f+i];
WHI(j, 0, l-m) R[j] = arr[m+j];
L[i] = R[j] = oo; i = j = 0;
while(f < l)
if(L[i] > R[j]){
arr[f++] = L[i++];
cnt += l-m-j;
}
else
arr[f++] = R[j++];
}
} |
OK。写完文章了，欢迎大家指点~