为什么插入排序的 O(n) nlogn 运行 时间是最理想的？
Why is O(n) nlogn run time for an insertion sort the ideal?
我们在 class 中了解到，插入排序是 omega 线性 运行 时间（如果传递的是一个已经排序的数组），对于所有其他情况则为 Big-O O(n^2)。然后我们的教授开始讨论具有 "merge sort" 方法的插入排序的理想选择，并且理想的是使用合并排序并具有 O (nlogn) 运行 时间？他不是一个很清楚的人……根本不是。请你解释一下他的意思！
我可能对你教授的意思有所了解。对于非常小的订单数组，（或简单地查看数组是否已排序），它可能对 运行 insertion sort 有意义，因为它不消耗辅助 space 和 运行s 在线性时间内。 Post 那，你会 运行 合并排序，无论条件如何，它都会平均 nlog(n) （除非你使用 自然合并排序 ，在这种情况下，您最好的情况归结为 O(n)，使用 运行 插入排序算法更没有意义），并且消耗和辅助 space O(n)。
尽管如此，可能值得注意的是像 Java 这样的语言使用双枢轴快速排序算法而不是合并排序（最坏情况下的快速排序是 O(n^2)） .我对此并不完全确定，但这可能是因为快速排序使用较少的辅助 space，但更多，因为数组遇到最坏情况的情况并不常见。
O(N) 被认为是快的，O(N Log(N)) 是公平的，O(N²) 是慢的。
对于少数元素，你可能不关心。但是想一想对一百万个元素进行排序：时间将与 1000000（比如 1 毫秒）、20000000（20 毫秒）和... 1000000000000（11 周）成正比。
这就是为什么 O(N²) 排序算法经常被避免的原因，因为知道 O(N Log(N)) 在所有情况下都是可能的，而 O(N) 对于某些配置。
让我们看看。
Insertion sort has O(n^2) run time
很明显，插入排序 运行 的复杂度为 O(n^2)。您可以阅读更多相关信息 here.
Our prof then began trailing on about the ideal for an insertion sort having a "merge sort" approach
我想你想说的是 idea 而不是 ideal。让我们看看这个 idea 关于具有“合并排序”方法的插入排序。归并排序的基础来自于分治范式。所以让我们假设我有这个数组
6 5 4 3 2 1
使用“合并排序”方法进行插入排序将使该数组基于分而治之范式分为两个区域（或更多）。
6 5 4 | 3 2 1
之后，我们可以在区域的每一边进行插入排序，然后使用conquer将它们连接起来。
4 5 6 | 1 2 3
1 2 3 4 5 6
好吧，现在让我们来看看 IF 我们对数组的每个元素应用除法。
6 | 5 | 4 | 3 | 2 | 1
等一下，这不是归并排序吗？ 是的，这就是你老师说的原因
that the ideal would be to use merge sort and have an O (n log n) run time
实际上，当某些 threshold 被激活时（比如只有 7 个元素），某些合并排序的实现使用了插入排序。你可以阅读here.
我们在 class 中了解到，插入排序是 omega 线性 运行 时间（如果传递的是一个已经排序的数组），对于所有其他情况则为 Big-O O(n^2)。然后我们的教授开始讨论具有 "merge sort" 方法的插入排序的理想选择，并且理想的是使用合并排序并具有 O (nlogn) 运行 时间？他不是一个很清楚的人……根本不是。请你解释一下他的意思！
我可能对你教授的意思有所了解。对于非常小的订单数组，（或简单地查看数组是否已排序），它可能对 运行 insertion sort 有意义，因为它不消耗辅助 space 和 运行s 在线性时间内。 Post 那，你会 运行 合并排序，无论条件如何，它都会平均 nlog(n) （除非你使用 自然合并排序 ，在这种情况下，您最好的情况归结为 O(n)，使用 运行 插入排序算法更没有意义），并且消耗和辅助 space O(n)。
尽管如此，可能值得注意的是像 Java 这样的语言使用双枢轴快速排序算法而不是合并排序（最坏情况下的快速排序是 O(n^2)） .我对此并不完全确定，但这可能是因为快速排序使用较少的辅助 space，但更多，因为数组遇到最坏情况的情况并不常见。
O(N) 被认为是快的，O(N Log(N)) 是公平的，O(N²) 是慢的。
对于少数元素，你可能不关心。但是想一想对一百万个元素进行排序：时间将与 1000000（比如 1 毫秒）、20000000（20 毫秒）和... 1000000000000（11 周）成正比。
这就是为什么 O(N²) 排序算法经常被避免的原因，因为知道 O(N Log(N)) 在所有情况下都是可能的，而 O(N) 对于某些配置。
让我们看看。
Insertion sort has O(n^2) run time
很明显，插入排序 运行 的复杂度为 O(n^2)。您可以阅读更多相关信息 here.
Our prof then began trailing on about the ideal for an insertion sort having a "merge sort" approach
我想你想说的是 idea 而不是 ideal。让我们看看这个 idea 关于具有“合并排序”方法的插入排序。归并排序的基础来自于分治范式。所以让我们假设我有这个数组
6 5 4 3 2 1
使用“合并排序”方法进行插入排序将使该数组基于分而治之范式分为两个区域（或更多）。
6 5 4 | 3 2 1
之后，我们可以在区域的每一边进行插入排序，然后使用conquer将它们连接起来。
4 5 6 | 1 2 3
1 2 3 4 5 6
好吧，现在让我们来看看 IF 我们对数组的每个元素应用除法。
6 | 5 | 4 | 3 | 2 | 1
等一下，这不是归并排序吗？ 是的，这就是你老师说的原因
that the ideal would be to use merge sort and have an O (n log n) run time
实际上，当某些 threshold 被激活时（比如只有 7 个元素），某些合并排序的实现使用了插入排序。你可以阅读here.