我得到了一个数组，并要求我找出使用冒泡排序对数组进行排序所需的交换次数
现在我们知道，我们可以通过n(n-1)/2找到比较，但我需要的是实际交换的数量
我的第一直觉是使用冒泡排序，并且对于每个 swap()，我都会增加一个 Swap 变量。但这的时间复杂度是一个非常缓慢的过程，我希望您帮助找到一种优化的方法来解决我的困境
P.S.:我还需要比较一下按升序排序还是按降序排序更快......排序两次会使时间增加一倍。
编辑:
抱歉，如果我不够清楚。我想在不使用冒泡排序的情况下找到交换。
最佳答案
关注已申请 swap()至a[i]和a[i+1]作为 a[i] 的冒泡 。
现在，询问将发生多少次互换就等于询问将发生多少次泡沫操作。好吧，我们有多少这样的？
每个a[i]每个位置都会冒泡 j > i ，其中a[j]<a[i] 。用文字来说a[i]将在右侧的每个位置冒泡，其中该位置的元素值小于 a[i]本身。满足此条件的一对元素称为 inversion的a[] 。
因此，我们可以重新表述您的问题:a[] 中的反转总数是多少？ ？ (又名 a[] 的反转数是多少？)
这是一个众所周知的问题，除了一些在 O(n^2) 中运行的明显方法之外，解决此问题的典型方法是稍微调整合并排序以找到该数字。由于合并排序的运行时间为 O(n*log(n))，因此您可以用相同的运行时间来查找 a[] 的反转数。 .
既然您知道可以调整合并排序，我建议您自己尝试一下如何准确地做到这一点。
提示:您必须回答的主要问题是:在两个数组的合并步骤中定位单个元素时，我修复了多少个反转？然后只需将所有这些相加即可。
如果您在深思熟虑后仍然遇到困难，您可以在这里查看一些完整的解决方案:
关于arrays - 冒泡排序对给定数组执行的交换次数，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/31903666/