算法基础课

基础算法

1.快速排序

1. 确定分界点：q[1]、q[(r)/2]、q[r]、随机
2. 调整区间
3. 递归处理左右两端

#include <iostream>
using namespace std;

const int N = 1e6 + 10;

int n;
int q[N];

void quick_sort(int q[], int l, int r)  //l代表左位置，r代表右位置
{
    if (l >= r)	return; //当左位置大于右位置时返回

    int x = q[l], i = l - 1, j = r + 1; //以该分区的第一个值为基准，由于后面写法是每次都是先移动再做判断，所有i、j要往两边有一个偏移量
    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);
}


int main()
{
    scanf_s("%d", &n);
    for (int i = 0; i < n; i++)	scanf_s("%d", &q[i]);

    quick_sort(q, 0, n - 1);

    for (int i = 0; i < n; i++)	printf("%d", q[i]);
}

2.归并排序

#include <iostream>
using namespace std;

const int N = 1e6 + 10;

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;	//左右边界相加，右移一位相当于除以2，得到中间位置

	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++];

	//将临时数组放回q[]
	for (i = l, j = 0; i <= r; i++, j++) q[i] = tmp[j];

}


int main()
{
	scanf_s("%d", &n);
	for (int i = 0; i < n; i++)	scanf_s("%d", &q[i]);

	merge_sort(q, 0, n - 1);

	for (int i = 0; i < n; i++)	printf("%d", q[i]);

	return 0;
}

整数二分模板

//区间[l,r]被划分为[l,mid-1]和[mid,r]时使用
int bsearch_1(int l,int r)
{
    while(l<r)
    {
        int mid=(l+r+1)>>1; 
        //不加1的话会死循环
        //相当于/2，但是>>是向下取整,/2是向0取整
        if (check(mid)) l=mid;
        else r=mid+1;
    }
    return l;
}
//区间[l,r]划分为[l,mid]和[mid+1,r]时使用
int bsearch(int l,int r)
{
    while(l<r)
    {
        int mid=(l+r)>>1;
        //相当于/2，但是>>是向下取整,/2是向0取整
        if(check(mid)) r=mid;
        else l=mid+1;
    }
    return l;
}