两种有关排序的经典问题

本文将会讲解两种通过交换元素来排序的最小步数问题

问题一

给定一个所含元素各不相同的序列,你可以交换任意相邻的一对元素,问将该序列排成有序(上升)序列至少要交换几次

问题转换

考虑与这个排序规则相同的排序算法:冒泡排序
冒泡排序相当于每次找到一个最大值,然后把它交换到最后,我们自然不能使用冒泡排序进行模拟,因为时间复杂度是 O(n^2) 的,所以继续思考优化:我们只需给出最小交换次数而不是求出具体数列,因此考虑冒泡排序中每个数找到自己的位置需要的最少次数,即原序列中在它后面比它小的数字的个数,问题转换为求逆序对个数

问题求解

我们可以使用归并或者树状数组统计来 O(nlogn) 解决这个问题
ans=\sum_{i=1}^{n}cnt_{num_{i}}

问题二

给定一个所含元素各不相同的序列,你可以交换任意一对元素,问将该序列排成有序(上升)序列至少要交换几次

问题转换

先将原序列每个元素按照它排序后的位置进行编号,我们要把每个元素移动到它的编号位置去,考虑如果它的位置被其他元素占据,如果它们恰好在彼此位置上,显然交换一次,继续思考3个元素互相在另一个元素位置上 如序列 3 2 4 1 中的 3 4 1,显然它们可以通过2次交换来完成个个元素归位,那么想到我们求出所有最大的这样的集体,然后对于每个大小为 size 的集体,需要交换size-1次即答案ans=\sum_{i=1}^{tot_{set}}(size_i-1)

发表评论

电子邮件地址不会被公开。 必填项已用*标注