问题标签 [insertion-sort]

所以我正在研究一些常见的排序算法并写了这个：

代码：

结果：

从测试中可以看出，第一个值不受排序的影响。我的算法有什么问题？

在《算法简介》第 2 版中，我发现了插入排序伪代码

但我不明白交换在这里是如何工作的。

我认为它需要这样的交换操作

我有什么问题吗？请帮忙

您好我正在使用以下插入排序算法，我想记录正在比较的元素。基本上我希望将比较存储在两个数组列表中，arrList1 和 arrList2。如果一个元素在正确的位置，那么两个数组列表将具有相同的元素。如果不是，则 arrList1 将具有所选元素，而 arrayList2 将具有与其自身比较的元素。我目前正在努力做到这一点，所以我想知道是否有人可以提供帮助？谢谢

编辑：例如：如果我的数组有数字 1,3,2,4,6,5，那么在比较时，这就是我希望我的两个数组列表的外观：

排序数组：1、2、3、4、5、6

如您所见， arrList1 基本上是输入数组的顺序，而 arrList2 是它比较的元素（如果其位置不正确）。如果它的位置正确，那么 arrList 2 将是相同的值。

我一直在搜索互联网和书籍，但没有运气，所以希望有人能指出我正确的方向。

我基本上需要使用插入排序而不是内置方法按名称语句按字母顺序对对象进行排序。我尝试过使用数组和列表，但似乎无法让它工作。你会怎么做呢？

我有一类播放器，最新尝试填充列表对象：

等等...最多 6 个用户对象

为了对其进行排序，我尝试在另一个类 Form1 中使用以下代码：

//须藤代码

希望这是正确的：/

我想我了解 PublicJoe 是如何做到的，但是您如何获取和设置对象的索引？感谢您的关注。

while 循环使用线性搜索向后扫描。但是，我们知道 while 循环中的数组已经排序。所以我们可以用二分搜索代替线性搜索，这样 O(n) 将变为 O(lg n)。但是，我对此的看法是，它不会有助于减少总时间，因为我们仍然必须将元素向前移动一个索引，这将始终需要 (向后步数 (n)) 次。所以总的来说，运行时间保持 O(n^2) 并且在这种情况下没有办法实现 O(n lg n)。如果我以错误的方式处理此问题，请告诉我。

我正在审查一些基本数据结构的实现以及在它们上运行的算法。我猜插入排序的惯用 F# 代码很像：

验证结果：int list = [-6; -3; 0; 1个；2；3；3；4；5个；8]

当我试图用List.foldBack和只有一个递归函数来实现它时，如下所示，并且不能给我正确的结果？任何人都可以弄清楚问题出在哪里？

我正在自学 CLRS 第 3 版，这是我遇到的更棘手的问题之一，以及它作为对所有人的服务的答案。

7.4-5 我们可以在实践中利用插入排序在输入“接近”排序时的快速运行时间来提高快速排序的运行时间。在元素少于k元素的子数组上调用快速排序时，让它简单地返回而不对子数组进行排序。在对快速排序的顶级调用返回后，对整个数组运行插入排序以完成排序过程。认为这种排序算法在O(nk+nlg(n/k))预期时间内运行。我们应该如何选择k，无论是在理论上还是在实践中？

如果输入数组是 - 1,4,3,8,6,5,7，则输出应该是 - 4 8 6 1 3 5 7

我有一种插入排序的解决方案。

这个问题可以更好地解决吗？我的解决方案的复杂度是 o(n2)。请提供时间复杂度较低的解决方案。不允许有额外的空间。

我想在 clisp 中编写插入排序和合并排序。输入将是一个平面的数字列表。如何递归地编写这两种类型（最好不使用 lambda）？对于插入排序，我正在考虑创建一个函数，该函数将列表和整数（这意味着感兴趣的元素的当前索引）作为参数，并使用 setf 和 nth 来操作列表。我知道其中还应该有另一个递归函数，但是就像......我只是对这么多要存储的函数和变量感到困惑。

对于合并排序，我完全不知道。

引发堆栈溢出错误。我在这里做错了什么？