csp-j基础算法模板

void quick_sort(int q[], int l, int r)
{
    if (l >= r) return;

    int i = l - 1, j = r + 1, x = q[l + r >> 1];
    while (i < j)
    {
        do i ++ ; while (q[i] < x);
        do j -- ; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
    }
    quick_sort(q, l, j), quick_sort(q, j + 1, r);
}

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 (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}

//把数组a中的数字二路合并到tmp中，最后又赋值给a 
int i = l, j = mid+1, k = 1;
while (i <= mid and j <= r)
{
    if (a[i] <= a[j]) tmp[k++] = a[i++];
       else tmp[k++] = a[j++];
}
while (i <= mid) tmp[k++] = a[i++];
while (j <= r) tmp[k++] = a[j++];
for (i = l, j = 1; i <= r; i ++, j ++ )
    a[i] = tmp[j];

//利用标记数组a[i] 表示 i是否为质数， a[i] = 0是质数，a[i] = 1不是质数。 
for (int i = 2; i <= n; i ++ )
{
	if(a[i] == 0)   
		for (int j =2*i; j <= n; j += i)  //质数的倍数都是合数 
		 	a[j] = 1;
}

//前缀和就是每一个数字之前的和,常常用来快速求出[l,r]区间内的和。 
for (int i = 1; i <= n; i ++ ) 
	s[i] = s[i-1] + a[i] ; // s[0] 必须为零。
	
//变式 ， 求质数的前缀和（不是质数就不加！） 
for (int i = 2; i <= n; i ++ ) 
	if(a[i] == 0) s[i] = s[i-1] + 1 ; // a[i]=0表示a[i] 是质数
	else s[i] = s[i-1];