问题标签 [bubble-sort]

我目前正在研究一个计算机器人移动成本的作业问题（位置 x，y）。

我们得到了一个带有多个障碍物（符号）的二维网格（二维数组）的维度##。下面是一个示例网格。我们还得到了机器人的起始位置。在当前位置，它的“成本”为00（固定）。

.................................................. ........................................##........ ........................................##........ ........................................##........ ..........######################################.. ........................................##........ ........................................##........ ........................................##........ ....################..........00........##........ ....################....................##........ ....################....................##........ ....################....................##........ ........................................##........ .................................................. ..................................................

作业中需要计算每个未知网格的成本..（

水平移动 +2 到前一个网格的成本。
对角线移动 +3 上一个网格的成本。
机器人不能穿越和障碍，必须绕过它。
每个值都必须具有最低成本（例如：对角线行驶的成本低于水平和垂直行驶的成本）。

下面是我们应该得到的结果（仅显示成本的最后两位数，省略了一些值，因此更具可读性）：

http://i.stack.imgur.com/JiDl1.png

现在我无法想象/解决这个问题。我们被告知它“在道德上就像冒泡排序算法”，每次找到新的最小成本时，都会重新计算一切。

抱歉，如果这非常令人困惑，任何建议（代码或伪代码将非常受欢迎）

它似乎只遍历数组一次，大部分未排序。

修复正整数n和k.

让A是一个长度n数组A[i]，k其中每个条目都是长度数组n-i。例如，使用n=5and k=1，这只是

对于n=5和k=2，这是

目标是通过交换相邻数组中的数字（例如A[i][j1]与交换A[i+1][j2]）来对这个数组数组进行冒泡排序，直到 的每个条目A[i]都i+1对应于i。

问题是：需要多少次交换，什么是最佳算法？

注意： 有很多很多更好的排序算法可供使用。但是，对于这个问题，我只对应用上述冒泡排序感兴趣。我只能交换来自相邻数组的条目，并且我只对必要的最小交换次数感兴趣。我很欣赏其他排序算法的所有建议，但这是我试图理解的问题。

例子：

对于k=1，这是众所周知的。交换次数是A被视为排列的倒数，因此最小交换次数是二项式系数(n choose 2) = n(n-1)/2，这可以通过交换任何乱序对来获得：A[i] > A[j]。对于第一个示例，这是一个最佳冒泡排序：

对于k=2，使用相同的策略将给出2 (n choose 2)所需的交换范围。对于上面的示例，这意味着20交换。但是有一个只使用15交换的解决方案：

n=5该解决方案对于and是最佳的k=2（通过蛮力证明找到所有解决方案）。对于n=6，最好的解决方案需要22交换，但解决方案看起来不如 for 的解决方案n=5（跟随 5 右，然后 1 左，然后 5 右等），所以我仍然不知道最佳策略，更不用说交换次数的公式或更好的界限。

这几天我一直在思考这个问题，但没有提出任何启发性的想法。如果有人对此问题有任何想法，请分享。我会很高兴了解更多有关k=2此案的信息。对于一般情况下的任何想法都更好。

编辑：如果我不能按照您的喜好激发这个问题，我深表歉意，但这里有一个尝试：对排列进行排序所需的冒泡排序数是组合学和数论中非常重要的统计数据，称为排列的反转数。您可以使用更好的算法对无序排列进行排序，但这是为您提供代数含义的算法。如果这没有帮助，也许这个相关的 SO 帖子可能会：冒泡排序有什么用？

更新：下面最古老的答案给出了交换次数的下限（和上限）。第二古老的答案给出了一个非常接近这个下限的算法（通常达到它）。如果有人可以改进界限，或者更好地证明下面给出的算法是最优的，那就太好了。

我的任务是询问用户他想输入的字符串数量。然后我会提示他纠正琴弦。然后我应该按字母顺序打印刺痛。我完成了大部分任务，只需要一个排序算法，比如冒泡排序来完成它。这是我的代码。

在我的程序中发生了一件很奇怪的事情。这是简化的代码。

我的 Sorts.MergeSort 函数有问题。当我正常使用它时（看看函数中的第一个 if 条件 - 一切正常。但是当我希望它切换到具有较小输入的冒泡排序时（函数中的第二个 if 条件）它抛出了我一个 SystemInvalidOperationException。我不知道问题出在哪里。你看到了吗？谢谢。:) 备注：bubblesort 本身可以工作 - 所以这种类型不应该有问题......

我写了这个冒泡排序并在一个测试程序中使用它，该程序根据用户输入的数量在列表中给出随机数。然后给它一个包含 10,000 个随机整数的列表，并在第 55 行“if (swaps != 0){sort();}”返回堆栈溢出，这是为什么。有时它也有效，但返回的 myCompares 和 mySwaps 值为负。你能帮我吗？

我一直在研究一个对 n 个整数进行冒泡排序的程序。我碰壁了，因为我不知道在我的汇编操作完成后刷新数组。任何建议都会很棒。

我在 C 中制作了这个冒泡排序算法。它在 DM 中运行良好，但在 gcc 中执行时，输出不正确。

输入：

DM输出：

海合会输出：

这是如何以及为什么会发生的？

请你能告诉我在 JavaScript 中这种冒泡排序算法的实现有什么问题吗？

我最近读了一篇关于算法计算复杂性的文章。作者提到了“为什么插入排序比小情况下的快速排序和冒泡排序更快”。有人可以对此做出一些解释吗？

有人知道我上面提到的每种排序算法的实际复杂性吗？