#! https://zhuanlan.zhihu.com/p/583746015

数据结构与算法第八章内排序书面作业

1.

设 ${s_1,\ldots,s_m}$ 为字母表 ${a,b,\ldots,z}$ 上的$m$组字符串，并且记$l_i$为字符串$s_i$的长度。尝试通过修改基数排序，对这些字符串按字典序排序，并且使得算法的时间复杂度为 $O(\sum_{i=1}^{m}l_i)$（简述思路并且给出算法时间复杂度的分析）

因为字母表大小$\vert\Sigma\vert = 26$恒定，在这些字符串上建立一棵字典树（trie），再DFS即可。

建立字典树与DFS的时间复杂度都是 $O(\left\vert\Sigma\right\vert\sum l) = O(\sum l)$的，空间复杂度是 $O(\vert\Sigma\vert\sum_i l_i) = O(\sum l)$ 的。

2.

给定整数数组A[1, …, n]，现在需要求其前k大的元素。

(1)

基于最大堆、最小堆作为辅助数据结构，设计算法，并分析其平均时间复杂度。在流数据上（元素随时间依次传入，长度未知），应选用何种算法更为合适？

用最小堆可以做到一个元素 $O(\log k)$ 的处理速度。

具体来说，每有一个新元素 $x$：

把 $x$ 加到堆里去。
若堆的大小$>k$，把堆中的最小数弹出。

最后，堆中剩下的 $k$ 个元素即为“前k大的元素”。

(2)

更进一步，请设计一种平均时间复杂度为 $O(n)$ 的算法，并简要说明你的算法如何保证该复杂度（Hint：参考快速排序)。

实现函数 solve(A, l, r, k) ，输出在 $A[i], i\in [l,r]$ 中前 $k$ 大的数（保证 $1 \le k\le r-l+1$ ）：

随机划分的方式与快速排序相同，假设划分为了 $[l,m-1]$ 与 $[m+1, r]$两段。

若 $k > m-l+1$，则输出 $A[i], i\in [l, m]$，并递归执行 solve(A, m+1, r, k - (m-l+1))。
若 $k = m-l+1$，则输出 $A[i], i\in [l,m]$，并返回。
若 $k < m-l+1$，则递归执行 solve(A, l, m-1, k)，并返回。

复杂度证明：若 $T(n) = \frac{1}{n}\sum_{i=0}^{n-1}T(i)$ 容易看出，取 $F(n) = nT(0)$ 即有 $F(n) = nT(0) \ge \frac{1}{n}\sum_{i=0}^{n-1}F(i) = \frac{n-1}{2}T(0), \forall n\in\mathbb N^*$ 故而，$T(n) = O(F(n)) = O(n)$。

3.

给定如下排序算法:
sort(A,i,j)
	If A[i]>A[j] then
		Swap(A[i],A[j])
	If (j-i+1)≥3 then
		t=(j-i+1)/3
		sort(A,i,j-t)
		sort(A,i+t,j)
		sort(A,i,j-t)
	Return A
尝试给出算法的正确性证明，并且求出其时间复杂度（Hint：写出递推公式可求解）。

正确性：数学归纳法。令 $l = j-i+1$：

$l = 0,1$ 时：返回时显然有序。
$l = 2$ 时：只在 A[i]>A[j] 时执行 Swap(A[i],A[j]) ，返回时 A[i..j] 有序。
$l\ge 3$ 时：由数学归纳法， sort(A,i,j) 调用的所有 sort(...) 均等效于排序。此外，因为正整数除法向下取整，故 3*t <= l。

因为 sort(A,i,j-t) 使 A[i..j-t] 有序了，故而，要证明函数结束时有序，只需证明此时 A[j-t+1..j] 中从小到大排列着 A[i..j] 中的 t 个最大的元素。

而要证明 sort(A,i+t,j) 后， A[j-t+1..j] 中从小到大排列着 A[i..j] 中的 t 个最大的数，相当于证明 sort(A,i,j-t) 之后，A[i..j] 中 t 个最大的数都在 A[j-t+1..j] 中。证明如下：

假设 A[i..j] 中的 t 个最大元在初始时在 A[i..j-t] 中有 s 个，则在 sort(A,i,j-t) 之后，这 s 个最大元在 A[j-t-s+1, j] 中，因为 s <= t，故 j-t-s+1 >= j-2*t+1 >= j+1-l+t = i+t。

因此，这 s 个最大元在 A[i+t, j] ，结合本来就在 A[j-t+1..j] 中的 t-s 个最大元，知在第一次 sort(A,i,j-t) 之后，所有的最大元都在 A[i+1..j] 中，得证。$\blacksquare$

复杂度：$T(0)=T(1)=T(2)=1$，

\[T(n) = 3T\left(\left\lceil\frac{2n}{3}\right\rceil\right) + 1\]

由主定理，因为 $\log_{\frac{3}{2}}{3} > 2$，故 $1 = O(n^{\log_{\frac{3}{2}}{3} - \epsilon})$。

因此，$T(n) = \Theta(n^{\log_{\frac{3}{2}}{3}})$。

4.

有一张n个方格子的纸条，格子上无序地写着1到n这n个数字。每个格子一个数字。现在沿着格子的边线折纸，可以将纸条折成一个小方块（正面只有一个格子）。这样n个数字的方格就竖直地排列起来。

请编写算法使这些方格上的数字从上到下的排列正好是1到n（无论正反）。例如上图就是一个7个格子的纸条和一种可行的折叠方案。

方案：

找到 $1$。
若 $1$ 在最左边，则倒序折叠 $1$ 右侧的纸条。最后使得 $1$ 旁边有一叠方块，而 $2$ 这叠方块在最下面。最后把这叠方块折叠到 $1$ 的下面即可。若 $1$ 在最右边则同理。若中途折叠失败则这个纸条不可被折叠排序。
若 $1$ 不在最左边或最右边，则分别倒序折叠 $1$ 左右两边的纸条，若中途折叠失败则这个纸条不可被折叠排序。考虑合并这两个纸条：
1. 考虑两个纸条靠 $1$ 的一侧的开口，分别依次把含有 $2, 3, \ldots, n$ 的纸条的最小部分折到 $1$ 的下面，若最后没有完全有序，则这个纸条不可被折叠排序。

5.

给定n个数a0, a1 … an-1

如果存在存在ai > aj且i < j，则称这样的元素对<ai, aj>为一个逆序对。请编写算法统计这n个数中逆序对的总数。

在归并排序的时候统计即可。代码附上，详见我在洛谷上的提交记录#10284784。

#include <cstdio>
#include <map>
#include <algorithm>
using namespace std;
const int maxn=500010,inf=1e9+1;
int n,i,a[maxn],tmp[2][maxn];
long long ans=0;
void mergesort(int l,int r,int k){
	if(l==r){
		tmp[k][l]=a[l];
		return;
	}
	int m=(l+r)>>1,*t1=tmp[k],*t2=tmp[k^1];
	mergesort(l,m,k^1);
	mergesort(m+1,r,k^1);
	for(int i=l,s=l,t=m+1;i<=r;i++){
		if(t>r\vert\vert(s<=m&&t2[s]<=t2[t]))
			t1[i]=t2[s++];
		else{
			ans+=m+1-s;
			t1[i]=t2[t++];
		}
	}
}
int main(){
    scanf("%d",&n);
    for(i=0;i<n;i++)
        scanf("%d",a+i);
    mergesort(0,n-1,0);
    printf("%lld\n",ans);
}

数据结构与算法 第八章 内排序书面作业

1.

2.

(1)

(2)

3.

4.

5.

数据结构与算法第八章内排序书面作业