问题标签 [insertion-sort]

我正在阅读一些关于 Python、数据结构以及算法分析和设计的书籍。我想真正了解编码的来龙去脉，成为一名高效的程序员。很难要求这本书澄清，因此我对stackoverflow的问题。我真的发现算法和递归具有挑战性......我在下面发布了一些代码（插入排序），我试图准确地理解正在发生的事情。一般来说，我理解应该发生的事情，但我并没有真正了解如何以及为什么。

通过尝试分析 Python Idle 上的代码片段，我知道：

然后：

我不知道为什么在第一行使用 1：range(1, len(mylist))。任何帮助表示赞赏。

这是我在java中为双向链表实现的插入排序。我检查了许多值，它给了我正确的输出。我的问题是：

1. 我不知道如何计算这个算法时间我的意思是 O(n)
2. 这可以优化吗？谁能指出更优化的代码？

注意：代码使用哨兵节点指向链表的开始，即哨兵节点。next 指向链表的起始节点和哨兵节点。PREV 指向链表的最后一个节点，head 指向哨兵节点。

我无法弄清楚它出了什么问题。

如果输入：4,56,5,2，则显示的输出为：2,4,0,1304。

如果输入：27,54,43,26,2 那么输出显示为：2,26,0,1304,0

如果输入：34,87,54,4,34 那么输出显示为：4,34,0,1304,0

基本上，只有前两个排序的 no 显示在输出中，而在其他地方，任何输入集都显示 1304 或 0。

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

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

是否可以在堆排序中使用插入排序来替换其交换或交换方法？

通常交换至少需要 3 个步骤：

我的一个朋友说可以使用插入排序将交换减少到一个操作而不是三个。是吗？

在插入排序中，

• 我们如何将一个新整数插入一个整数数组？
• 数组的内存会在编译的时候被分配，所以我们不能增加数组的大小，即使我们分配了一些额外的空间，如果需要的内存超过了分配的内存怎么办？
• 我们应该为每个整数的插入创建一个新数组吗？
• 如果我们想在有序数组中插入更多的整数，我们应该怎么做？
• 我们可以用指针来做到这一点吗？

我试图理解下面的代码：

但我不确定是什么意思for( ; ) ，所以我需要你们的帮助。抱歉，如果它重复了，但我在这里和谷歌中搜索，但到目前为止没有。

我在试图弄清楚如何使用扫描仪将整数插入 ArrayList 时遇到了一些问题。我在java方面不是那么好（实际上甚至不是很好），但我只是想弄清楚一些事情，任何帮助都会很棒。

它还没有完全完成，但所有这一切背后的想法是尝试和改进 MergeSort。基本上，一旦元素被分解到某个点切入 InsertionSort，因为它通常在非常小的（非常小的相对）数据集上更好。

我正在进行交流插入排序，它工作正常，除了排序后第一个数字总是一个奇怪的负数并且程序出错。

这是我最初为输入随机数而编写的代码，然后使用插入排序方法对它们进行排序。

老实说，我有一个项目，它要求运行算法以获得最佳、最差和随机输入，并计算关键比较的数量（我相信在这段代码中是“compcount”）

现在随机输入对此有意义。当我用“一个已经排序的”数字数组（最好的情况）编写另一个代码时，键比较的数量为 0。有人可以阐明最坏的情况是否与此完全相反？如果是这种情况，我尝试这样做，但我只得到了 32 次比较，而数组的大小为 32。

对不起，很长的问题。最坏情况输入应该有 (n^2-n)/2 比较次数对吗？最好的情况应该是 n-1 因为只有第一个元素会遍历整个列表并确认它正在排序。我如何在代码中得到这个？