数据结构与算法C语言——分治法(共9页).doc

精选优质文档-倾情为你奉上学号： 姓名：高梁上机XX 实验名称：分治法一、逆序对数问题1、 算法思想可以使用分治法-归并排序解决上述问题。具体如下：将n个元素分成个数大致相同的两半，且左边的各个元素和右边的各个元素各自有序：（1）如果左边的元素a0右边的元素an/2，则逆序对数加1，接着a0继续与an/2+1比较，直到碰见a0an/2+t（tn/2）为止或直到与an-1比较完结束。（2）接着比较a1、a2、an/2-1与右边的元素，与上述过程相同。2、 实现代码及运行结果程序源代码如下：#include #include#include#define LEN 10/*归并排序*/该函数实现，将ar