冒泡排序对给定数组执行的交换次数
Number of swaps performed by Bubble-Sort on a given array
我得到了一个数组，我被要求找出使用 冒泡排序
对数组进行排序所需的交换次数
现在我们知道了，我们可以通过n(n-1)/2找到比较，但我需要的是actual swaps
的数量
我的第一直觉是使用冒泡排序，并且在每次 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 of a[]。
因此重新表述您的问题我们可以问：a[] 中的反转总数是多少？ (a.k.a.a[]的倒数是多少?)
这是一个众所周知的问题，除了 O(n^2) 中的一些明显方法 运行 之外，解决此问题的典型方法是稍微调整合并排序以找到该数字。并且由于合并排序在 O(n*log(n)) 中运行，您获得相同的 运行 时间来查找 a[].
的倒置数
既然您知道可以调整合并排序，我建议您自己尝试一下如何正确地进行。
提示：你要回答的主要问题是：在两个数组的合并步骤中定位单个元素时，我修复了多少次反转？然后简单地把所有这些加起来。
如果你在考虑之后仍然卡住了，你可以在这里看看一些成熟的解决方案：
- http://www.geeksforgeeks.org/counting-inversions/
- Counting inversions in an array
我得到了一个数组，我被要求找出使用 冒泡排序
对数组进行排序所需的交换次数现在我们知道了，我们可以通过n(n-1)/2找到比较，但我需要的是actual swaps
我的第一直觉是使用冒泡排序，并且在每次 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 of a[]。
因此重新表述您的问题我们可以问：a[] 中的反转总数是多少？ (a.k.a.a[]的倒数是多少?)
这是一个众所周知的问题，除了 O(n^2) 中的一些明显方法 运行 之外，解决此问题的典型方法是稍微调整合并排序以找到该数字。并且由于合并排序在 O(n*log(n)) 中运行，您获得相同的 运行 时间来查找 a[].
既然您知道可以调整合并排序，我建议您自己尝试一下如何正确地进行。
提示：你要回答的主要问题是：在两个数组的合并步骤中定位单个元素时，我修复了多少次反转？然后简单地把所有这些加起来。
如果你在考虑之后仍然卡住了，你可以在这里看看一些成熟的解决方案：
- http://www.geeksforgeeks.org/counting-inversions/
- Counting inversions in an array