知识点练习

用归并排序统计逆序对，合并部分的核心代码为：

设有一个长度为 $n$ 的 $01$ 字符串，其中有 $k$ 个 $1$。每次操作可以交换相邻两个字符。在最坏情况下将这 $k$ 个 $1$ 移到字符串最右边所需要的交换次数是多少？

假设快速排序算法的输入是一个长度为n 的已排序数组，且该快速排序算法在分治过程总是选择第一个元素作为基准元素。以下哪个选项描述的是在这种情况下的快速排序行为?

考虑对 n 个数进行排序，以下最坏时间复杂度低于 $O(n^2)$ 的排序方法是（ ）。

假设在基数排序过程中，受宇宙射线的影响，某项数据异变为一个完全不同的值。请问排 序算法结束后，可能出现的最坏情况是（ ）。

以下排序方法中，（ ）是不稳定的。

定义一种字符串操作为交换相邻两个字符。将 $\texttt{DACFEB}$ 变为 $\texttt{ABCDEF}$ 最少需要 ( ) 次上述操作。

排序的算法很多，若按排序的稳定性和不稳定性分类，则（）是不稳定排序。

设 $A$ 和 $B$ 是两个长为 $n$ 的有序数组，现在需要将 $A$ 和 $B$ 合并成一个排好序的数组，问任何以元素比较作为基本运算的归并算法，在最坏情况下至少要做多少次比较？（）。