玖的数学&算法录

数列极限的几种计算方法

发表于 2022-01-31 更新于 2022-07-20
本文字数： 6k 阅读时长 ≈ 5 分钟

简单的介绍一下以下几种数列极限的计算方法：

1.Toeplitz定理
2.Stolz定理
3.Wallis公式
4.Stirling公式

阅读全文 »

算法笔记（01）：排序算法

发表于 2022-01-29 更新于 2022-11-28
本文字数： 2.3k 阅读时长 ≈ 2 分钟

更新：

删去了其他比较trivial的排序，留下了算法竞赛中用的略微多的排序思维。

删掉了useless的排序方法（希尔等等）。

修正了代码语言，Java语言由于当时第一版所写的错误过多，因而删除，再加上在运行速度上不及C++。

1.快速排序

是一种基于分治的排序方法。

思路

对需要排序的区间[l,r]进行下面的操作：

(1) 如果区间长度小于等于1直接退出，否则在区间中选择一个数字x作为比较元素。

(2) 将大于x的数字放右边，小于x的数字放左边，等于x的可左可右，将x放在两组数字中间。

**(3)**此时x的位置确认，对其左右两边的区间分别进行递归即可。

代码

void quicksort(int l,int r) {
	if(l >= r) return;
    std::swap(a[l], a[l + rand() % (r - l + 1)]);
    int x = a[l];
    int i = l,j = r;
    while(i < j) {
		while(i < j && a[i] > x) {
            j--;
            if(i < j) {
			 a[i++] = a[j];
            }
        }
        while(i < j && a[i] < x) {
            i++;
            if(i < j) {
                a[j--] = a[i];
            }
        }
    }
    a[i] = x;
    quicksort(l, i - 1);
    quicksort(i + 1, r);
}

2.归并排序

是一种基于分治的排序方法。

思路

对需要排序的区间[l,r]进行下面的操作：

(1) 如果区间长度小于等于1直接退出，否则将区间分为[l,m],[m + 1,r]两个部分，其中 m = (l + r) / 2。

(2) 递归对两个子区间进行归并排序。

(3) 将两个已经排好序的子区间进行合并。

代码

void mergesort(int l,int r) {
	if(l == r) return;
    int m = (l + r) / 2;
    mergesort(l,m);
    mergesort(m + 1, r);
    int p1 = l, p2 = m + 1,tot = 0;
    while(p1 <= m && p2 <= r) {
		if(a[p1] <= a[p2])
            c[++tot] = a[p1++];
         else
            c[++tot] = a[p2++];
    }
    while(p1 <= m)
        c[++tot] = a[p1++];
    while(p2 <= r)
        c[++tot] = a[p2++];
   	for(int i=1;i <= tot; i++) {
        a[i + l - 1] = c[i];
    }
}

3.计数排序

思路

计数排序适合于值域范围校的数字排序

(1) 统计每个数字出现了几次。

(2) 统计完每个元素的出现次数后，求一边前缀和，我们就知道了每个数字在排完序后的序列中出现位置的范围。

(3) 把数字填入对应的位置即可。

代码

#define endl "\n"
int n, m, a[N + 1], c[M + 1], r[N + 1];

inline void countingsort() {
	memset(c,0,sizeof(c));
	for(int i=1;i<=n;i++) {
		++c[a[i]];	
	}
    for(int i=1;i<=m;i++) 
		for(int j=1;j<=c[i];j++) 
			std::cout << i << " ";
   	std::cout << endl;
    
    for(int i=2;i<=m;i++) {
		c[i] += c[i - 1];
    }
    for(int i=n; i; --i) {
         r[i] = c[a[i]]--;
    }
    for(int i=1;i<=n;i++) {
		std::cout << r[i] << " ";
    }
    std::cout << endl;
}

4.基数排序

思路

将每个待排序的元素拆分成m个关键字，然后从后往前依次对这m个关键字进行排序。

特别的

（基数排序经常被用于进行字符串的排序，比如说后缀数组的核心就是基数排序）。

(1) 我们只要把数字按第 i 个及以后的关键字从小到大的顺序放到数组里，再做一次计数排序就好。

代码

int n, m, a[N + 1], sa[N + 1], v[N + 1], r[N + 1], c[10];

inline void countingsort() {
    memset(c,0,sizeof(c));
    for(int i=1;i<=n;i++)
        ++c[v[i]];
    for(int i=1;i<=9;i++)
        c[i] += c[i - 1];
    for(int i=n;i;--i)
        r[sa[i]] = c[v[sa[i]]]--;
    for(int i=1;i<=n;i++)
        sa[r[i]] = i;
}

inline void radixsort() {
    for(int i=1;i<=n;i++)
        sa[i] = i;
    int x = i;
    for(int i=1;i<=m;i++,x *= 10) {
        for(int j=i;j<=n;j++)
            v[j] = a[j] / x % 10;
    	countingsort();
    }
}