统计逆序对：算法设计与C++实现

实验一的主题是“统计逆序对”，这是《算法分析与设计》课程中的第一个实验。该实验的目标是让学生理解和应用分治算法，以及熟练运用C/C++编程语言。实验的核心任务是设计一个算法来计算给定排列中逆序对的数量，并输出这些逆序对的具体组合。 逆序对是指在一个数组或序列中，存在两个元素，使得前者大于后者。例如，对于数组23, 13, 35, 6, 19, 50, 28, 38, 26, 17, 45，逆序对有(23, 6), (23, 13), (35, 6), (35, 13), ...等。实验要求学生利用归并排序的思想，通过分治策略将原数组分为两半，分别进行升序排序，然后合并这两个有序部分时，统计在合并过程中形成的逆序对。 算法设计的关键步骤如下： 1. 初始化逆序对个数 `ans` 为0，用于累计结果。 2. 当待排序区间的长度为1时，直接结束，因为单个元素没有逆序对。 3. 计算划分的中点 `mid`，并将数组分为两部分。 4. 对左右两个子序列分别进行升序排序。 5. 合并两个已排序的子序列： - 定义两个指针 `l` 和 `r` 分别指向左右子序列的起始位置。 - 当指针均未越界时，比较当前元素： - 如果左侧元素大于右侧，说明形成了一个逆序对，`ans` 增加 `mid - i + 1`，其中 `i` 是左侧子序列的当前元素位置。 - 将较小的元素放入临时数组，并移动对应指针。 6. 最后返回逆序对的数量 `ans` 和具体的逆序对组合。 实验中提供的代码示例展示了如何用C/C++实现这一算法。学生需要根据这个框架编写自己的代码，并测试给定的数据集，如23, 13, 35, 6, 19, 50, 28, 38, 26, 17, 45，以验证算法的正确性。实验报告应包括算法的详细描述、代码实现、以及正确答案的验证过程，可能还包括执行时间和空间复杂度的分析。 通过这个实验，学生不仅锻炼了解决实际问题的能力，还加深了对分治策略和C/C++编程的理解，同时提升了算法分析和设计的技能。