我想要切换到插入排序对较小的数组和快速排序的较大数组。切换到插入排序可以减少递归的次数。我想知道数组的最大大小，在那里我可以切换到插入排序.
以下是快速排序和插入排序的实现。对于数组长度<9，使用插入排序。
即使我们知道双枢轴快速排序使用插入排序数组较小的数组长度< 27
PS - Java使用双枢轴快速排序来排序原语类型。
浏览 3提问于2017-03-22得票数 1
从插入排序的wiki页面：
一些分治算法，如快速排序和合并排序，递归地将列表划分为较小的子列表，然后排序。在实践中，这些算法的一个有用的优化是使用插入排序来排序小的子列表，其中插入排序优于这些更复杂的算法。插入排序具有优势的列表的大小因环境和实现的不同而不同，但通常在8-20个元素之间。
wiki的引用有一个原因，那就是合并排序中的小列表并不是插入排序的更糟糕的情况。
我只想忽略这个原因。
我知道，如果数组大小很小，插入排序O(n^2)就有可能击败合并排序O(n log )。
我认为(不确定)这与T(n)中的常数有关。
插入排序: T(n) = c1n^2 +c2n+c3
合并排序: T(n
浏览 3提问于2011-11-30得票数 0
回答已采纳
所以我知道线性的O(N)是n，插入是n**2，二进制是log(n)，合并是nlogn
因此，合并排序是大型列表的最佳搜索。上面的哪一个是最适合小列表的，比如有多小？谢谢
浏览 1提问于2014-02-19得票数 0
1回答
插入排序算法
、、
我对数据结构和算法很陌生。我刚刚实现了一个插入排序算法。我只想确定我的代码是否正常。
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
int[] test = {40, 1, 5, 0, 9};
for (int i = 0; i < test.length; i++) {
for (int j = i - 1; j >= 0; j--) {
if (t
浏览 0提问于2022-02-05得票数 1
回答已采纳
2回答
我刚刚开始学习排序算法，并在网上找到了一个。起初我认为它是shell排序，但它缺少"k“的明显间隔和数组的一半，所以我不确定它是否是。我的第二个猜测是插入排序，但我只是在这里仔细检查：
for(n = 1; n < num; n++)
{
key = A[n];
k = n;
while((k > 0) && (A[k-1] > key))
{
A[k] = A[k-1];
k = k-1;
}
A[k] = key;
}
另外，如果你能解释为什么这也是有帮助的
浏览 2提问于2011-11-04得票数 4
我见过很多地方，它谈到插入排序对小数据集有什么好处。不过，我找不到“小”的数字。我的猜测是，没有绝对答案，这取决于运行代码的机器的类型。
然而，当插入排序是一个好主意时，哪些因素会决定什么是阈值？“小”的大概数字是多少? 5? 10? 50? 100？
谢谢!
站点说插入排序对小数据集很好：
浏览 0提问于2018-12-16得票数 0
回答已采纳
1回答
在递归排序中使用Helper方法
、、、、
我正在尝试用Java语言编写一个版本的timSort，它使用array.length < 10之后的插入，否则使用合并排序。假设我对insertionSort和merge的调用是正确的，是什么使下面的代码不会命中插入、排序和正确的timSorting？ /**
* timSort is a generic sorting method that sorts an array of Comparable data
* using the TimSort algorithm. Make sure this method is public so that we can
* test
浏览 28提问于2019-03-11得票数 0
有人可以一步一步地解释一下，当我们找到插入排序的最坏情况分析时，我们是如何得到O(N^2)的吗？我目前正在阅读科尔门算法入门一书中对它的解释，但解释有点令人困惑。
浏览 1提问于2014-01-19得票数 0
3回答
这些排序算法在实际应用中有什么用处吗？
还是仅仅是n^2复杂度排序算法的一个基本例子？
有人能举个例子说明一下它的用法吗？
浏览 6提问于2016-02-05得票数 2
回答已采纳
1回答
我一直在比较选择和插入排序。据我所知，插入排序作用于倒置计数，而不是依赖于它。但在最坏的情况下，总的反转计数将是最大的，并且在插入排序中，交换的数目将是最大/大于选择排序，因为在选择排序中，总交换总是输入大小'n‘的顺序，并且不大于该顺序，并且它将比插入排序中小得多。
在最坏的情况下，时间复杂度将取决于比较的数量(在选择排序的情况下等于或更少)和交换的数量(在插入排序中更多)。因此，如果交换/写入更快，我可以使用插入排序，但如果与比较相比写入成本较高，则我将使用选择排序。那么，哪种排序算法在最坏的情况下会更好，如果我使用数组作为数据结构，如何决定比较速度更快或复制速度更快。
浏览 0提问于2018-01-03得票数 0
4回答
3-快速排序，问题
、、、
我正在尝试理解3向基数快速排序，我不明白为什么那里有截断变量？那插入的方法呢？
public class Quick3string {
private static final int CUTOFF = 15; // cutoff to insertion sort
// sort the array a[] of strings
public static void sort(String[] a) {
// StdRandom.shuffle(a);
sort(a, 0, a.length-1, 0);
as
浏览 1提问于2010-06-11得票数 4
回答已采纳
2回答
我试图在Java中实现一种高效的排序算法。出于这个原因，我还实现了快速排序，并使用了以下代码：
public class Sorting {
private static Random prng;
private static Random getPrng() {
if (prng == null) {
prng = new Random();
}
return prng;
}
public static void sort(int[] array) {
sortInte
浏览 1提问于2016-04-04得票数 1
回答已采纳
我必须回答以下问题:你能想出一个场景，在这个场景中，SelectionSort (就结果的发展而言)比InsertionSort更好吗？
我的想法是，如果你只需要一个非常大的列表中的前10名，你可以在第10步之后结束排序。这是这个问题的有效答案吗？你能想出其他的场景吗？
浏览 0提问于2011-11-06得票数 0
回答已采纳
1回答
问题；
您必须按日期对一系列银行交易进行排序。他们中的大多数人(到目前为止)都井井有条，只有少数人出了问题。
您将在插入排序、选择排序和合并排序之间使用哪种排序算法来利用数组几乎已排序的事实？
我的回答(不确定是否正确)
假设N >= 5，我将从它的avg开始使用合并排序。时间复杂度为O(n * log n)，比插入排序O(n^2)更有效。但是，由于多个事务在相同的日期上，插入排序将是一种很好的稳定排序方法。
在这种情况下哪一种更好？合并还是插入排序？我朝正确的方向走了吗？
浏览 3提问于2016-10-09得票数 0
回答已采纳
通过理解插入排序算法，我编写了这段代码。我的老师说它是冒泡排序，但我的朋友说它是插入的。有没有人可以检查一下并向我简要介绍一下。
#include <stdio.h>
void sort(int n) {
int i, j;
float arr[n], k;
for (i = 0; i <= n - 1; i++) {
printf("Enter the number");
scanf("%f", &arr[i]);
}
for (i = 1; i <= n - 1; i++) {
j
浏览 0提问于2017-08-16得票数 3
1回答
根据
在小型阵列上使用插入sort...for调用(即长度小于实验确定的阈值k)。这可以通过简单地在只剩下小于k个元素时停止递归来实现，使整个数组k排序:每个元素最多只在k个位置远离其最终位置。然后，一个插入排序传递在O(k×n)时间内完成排序。
我不确定我的理解是否正确。一种包括多次调用插入排序的方法是
quicksort(A, i, k):
if i+threshold < k:
p := partition(A, i, k)
quicksort(A, i, p - 1)
quicksort(A, p + 1, k)
else
inse
浏览 1提问于2014-08-27得票数 0
我想知道有没有人能帮我？我有一个简单的2/3行代码，可以通过Python调用另一个函数，但似乎无法理解。原始的quicksort2工作，插入排序工作，但是--对函数的调用不起作用(它们位于同一个目录中)--有人知道该怎么做吗？谢谢。我会把这两个代码都贴在下面。
赋值明确规定：，当n个≤16时，Quicksort2将不对列表进行分区，而是调用插入排序。这意味着我需要一个简单的if-elif语句在我的快速排序2函数中，但是无法确定该做什么。
# insertion sort function for an array
def insertion_sort(array_values):
浏览 4提问于2019-10-01得票数 0
1回答
假设您必须使用n = 1,000,000元素对数组进行排序。假设每一个基本步骤都需要100秒，那么插入排序和堆排序大概需要多长时间？
我知道插入排序在最坏的情况下采取n^2步骤，而堆排序在最坏的情况下采取n log n步骤。
所以1,000,000 ^ 2用于插入排序= 1*10^12毫秒
1,000,000 * log(1,000,000)表示堆排序？6,000,000 milli-秒
是这样吗？
浏览 5提问于2011-05-24得票数 1
1回答
下面是插入排序的原始伪码：
function INSERTIONSORT(A[0..n−1])
for i←1 to n−1 do
j←i−1
while j≥0 and A[j+1]<A[j] do
SWAP(A[j+1],A[j])
j←j−1
一家公司在他们的产品中使用插入排序。您是该公司聘请的网络安全专家，负责评估其代码的任何安全缺陷。经过几次尝试，您成功地攻击了它们的插入排序代码，并以下列方式修改了它们：
function INSERTIONSORT(A[0..n−1])
for i←1 to n
浏览 0提问于2021-05-22得票数 0
回答已采纳
我正在比较插入排序和快速排序。我已经弄明白了为什么在几乎已排序的数组上qsort更慢，但我不明白为什么插入排序要快得多，当然它仍然需要比较数组中几乎相同数量的元素。
浏览 2提问于2012-04-22得票数 4
1回答
这是使用数组和使用链表的插入排序的结构的区别。
为了实现列表的插入排序，我们是否使用了数组的算法，只需更改命令A(k)=A(k+1)？
还有更多不同之处吗？
浏览 1提问于2014-10-27得票数 0
因此，对于拆分时的合并排序，我将使用
HGFEDCBA
HG FE DC BA
H G F E D C B A
用于合并，而不是
GH EF DC AB
EFGH ABCD
ABCDEFGH
好呀
H G F E D C B A
GH F E D C B A
FGH E D C B A
EFGH D C B A
DEFGH C B A
CDEFGH B A
CBDEFGH A
ABCDEFGH
我能想到的唯一一件事是，合并排序通常是递归实现的，如果使用递归进行拆分，使用第一种方法合并会更容易。
浏览 1提问于2020-01-15得票数 1
V8对长度超过10个元素的数组使用快速排序，对于小于该长度的数组使用插入排序。这是
function InnerArraySort(array, length, comparefn) {
// In-place QuickSort algorithm.
// For short (length <= 10) arrays, insertion sort is used for efficiency.
我想知道为什么不使用shell排序而不是插入排序？我知道，对于一个由10个元素组成的数组来说，这可能没有什么区别，但仍然如此。有什么想法吗？
浏览 2提问于2017-05-18得票数 1
回答已采纳
选择排序
插入排序
气泡分类
什么名字的意思？我知道select排序是如何工作的，但我不明白为什么select排序是select排序。(插入排序，气泡排序一样)请告诉我！
浏览 3提问于2017-08-11得票数 0
回答已采纳
1回答
import sys 首先创建一个函数，并将arr和n作为参数进行传递。 def recursiveinsertionsort(arr,n): 基本情况:当为n=0或n=1时。 if n<=1:
return 现在调用该序列，直到剩余的n-1项。 recursiveinsertionsort(arr,n-1)
temp=arr[n-1]
j=n-2
while j>=0 and arr[j+1] < arr[j]:
arr[j+1]=arr[j]
j-=1
浏览 15提问于2020-04-04得票数 0
回答已采纳
下面的代码可以称为插入排序吗？我试着执行根据我的秘密..。
#include<iostream>
void insertionSort(int* array,int length){
for(int unsortedIndex=1; unsortedIndex<length;unsortedIndex++){
for(int sortedIndex=0; sortedIndex<unsortedIndex; sortedIndex++){
if(array[unsortedIndex] < array[s
浏览 0提问于2019-01-16得票数 0
回答已采纳
1回答
排序算法命名
、、
以下排序算法的名称是什么？
for i in range(1, len(a)):
for j in range (0,i):
if(a[j] > a[i]):
a[i], a[j] = a[j], a[i]
浏览 1提问于2018-06-19得票数 0
回答已采纳
对于几乎排序的列表，哪种是最好的排序方法?为什么？对于许多元素的列表，我发现快速排序是helpful.But，当排序已经被排序时，哪个排序有更好的运行时间？
浏览 3提问于2015-06-02得票数 2
回答已采纳
1回答
我有一个问题：
与1/(2^n)相比，我们知道n!*(1/(2^n))是n!*(1/(2^n))，但是插入排序为什么与2^n相比呢？
我的意思是，与插入排序的示例不同，为什么使用了2^n的反向排序？
浏览 1提问于2020-12-13得票数 0
回答已采纳
如果数组长度小于某个阈值，Java6在Arrays.java中的合并排序实现将使用插入排序。这个值被硬编码为7。由于算法是递归的，对于大型数组，这种情况最终会发生很多次。规范的并不这样做，只是一直使用merge-sort，直到列表中只有1个元素。
这是一种优化吗？如果是这样，它应该有什么帮助呢？为什么是7？插入排序(甚至是<=7排序)大大增加了对大型数组进行排序所需的比较次数-因此会增加compareTo()调用速度较慢的排序的开销。
(对于不同的INSERTIONSORT_THRESHOLD值，x轴为size of array，y轴为# of comparisons )
浏览 0提问于2011-07-11得票数 22
回答已采纳
1回答
来自维基百科，
在图中，假设我们考虑中间一行的数字(如果有人可以在这里张贴图片，这将有所帮助)。如果我将算法修改为：
合并38和27，然后按升序排序数字。(27、38)
将上述结果与43合并，然后按升序排序。(27、38、43)
将以上结果与3合并，然后按升序排序。(3、27、38、43)。
...And等，直到我有一个完整的排序列表。
这是一种极其低效的排序方法(我可以直观地看出--在最坏的情况下，所添加的数字将与列表中的每个数字交换)，尽管我不太确定它如何将排序的O(n log n)时间(从我的分析的合理性方面)与合并排序的O(N Log N)时间进行比较。
有什么
浏览 0提问于2017-09-27得票数 1
1回答
对于任何长度大于10的数组，是否可以安全地说合并排序在数组元素之间的比较比在同一个数组上的插入排序要少，因为合并排序的运行时间最好是O(N log N)，而插入排序则是O(N)？
浏览 2提问于2017-07-24得票数 0
2回答
我的问题是关于理论和实践的问题。
例如，我想对一个数字列表进行排序。Mergesort的复杂度为O(n*logn)，而bubblesort的复杂度为O(n^2)。这意味着合并更快。但复杂性并没有考虑到发生在电脑上的所有事情。我的意思是，例如，合并是一种分而治之的算法，它所需的空间比短的要大。那么，创建这个额外的空间和使用资源(传输数据、填充代码指令等)比不使用任何额外空间的bubblesort花费更多的时间，难道不可能吗？对于一定长度的输入(可能很小)，使用复杂度更差(“更大”)的算法不可能比另一种算法更有效吗？
浏览 2提问于2020-01-22得票数 0
回答已采纳
1回答
我试着用python实现插入排序。我试图理解它背后的逻辑，并实现了它，它最终证明了我是一个排序列表，但我怀疑它是否严格地使用了插入排序。有人能确认这真的是插入排序吗？如果我听起来很傻，很抱歉。
u = [1,43,2,312,3,124,6,6]
for i in range(len(u)):
for j in range(i,0,-1):
if u[j] < u[j-1]:
u[j-1],u[j] = u[j],u[j-1]
print(u)
我得到的答案是1，2，3，6，6，43,124,312
浏览 8提问于2020-11-15得票数 0
1回答
Θ(n)复杂度排序数组
、、、、
证明了当n为O(n)时，大小为n的数组可以在Θ(n)中排序。
我不知道这个问题到底在问什么。我最好的猜测是，我们在预先设定的输入上使用插入排序，这样我们就可以通过排序实现Θ(n)的复杂性。这就是问题在问我吗？
浏览 2提问于2013-10-29得票数 2
回答已采纳
1回答
这种排序是插入排序吗？
、、、、
因此，我尝试用迭代器对双链接列表进行插入排序。它返回一个排序列表，其中“键”从小到大排序。尽管我的代码没有对实际列表进行排序，我也不确定它是否是插入排序。有人能帮忙吗？
public static List sort(List list) {
List sortedList = new List(); // sortedList
List.Iter curIndex = List.Iter.last(sortedList); // terminated forward iterator
浏览 7提问于2022-11-27得票数 0
回答已采纳
4回答
假设我们使用二次排序算法对一个由十个整数组成的数组排序。在对算法的主循环进行四次迭代之后，排列数组元素如下所示：
1 2 3 4 5 0 6 7 8 9
哪条语句是正确的？(注意:我们的选择排序首先选择最大的项目。)
A.算法可以是选择排序，也可以是插入排序。
B。算法可能是选择排序，但不能是插入排序。
C.算法可能是插入排序，但不能选择排序。
D算法既不是选择排序，也不是插入排序。
我认为答案应该是A(插入排序和选择排序)？但我在一些网站上发现正确答案是C。我不知道原因。谁能解释一下。
如果我错了，请纠正我。
来源：
浏览 7提问于2015-05-09得票数 0
回答已采纳
不是插入排序 O(n^2) > Quicksort O(n log n)...so对于一个小n，关系不是相同吗？
浏览 0提问于2011-11-12得票数 34
我正忙着准备考试，只是做了一些旧的试卷。下面的问题是我唯一不能回答的问题(我真的不知道从哪里开始)。任何帮助都将不胜感激。
使用Ω(nlogn)比较排序界、自底向上堆构造的theta(n)界和插入排序的顺序复杂性来显示堆中倒置的最坏情况数是Ω(nlogn)。
浏览 4提问于2010-06-09得票数 3
回答已采纳
LinkedHashMap将所有调用委托给其父HashMap。它还支持基于accessOrder值的访问排序和插入排序。如果accessOrder : true，则使用访问顺序，否则使用accessOrder :false插入顺序
公共LinkedHashMap(整型initialCapacity，浮点型loadFactor，布尔型accessOrder)
但是LinkedHashMap如何在内部支持对象的访问排序和插入排序呢？
浏览 4提问于2013-09-30得票数 1
1回答
二进制合并排序&自然合并排序
、、、、
我知道作业问题不是这里最受欢迎的问题，但我完全不知所措。我正在做一项作业，要求我们做多个排序算法。不过，其中一个让我发疯了。我在网上任何地方都找不到它的例子，他在课堂上也没有把它看完。我们必须做一个合并排序，如下所示：
void mergeSort(int * a, int s, bool n = false)
其中a是数组，s是所述数组的大小，n对于二进制合并排序为false，对于自然合并排序为true。问题是，我找不到什么自然合并排序和二进制合并排序。我只是找到了合并。他们都要求更多的变量。
我只是问，是否有人知道我在哪里可以找到一个很好的解释这两种不同类型的合并。
浏览 2提问于2015-04-05得票数 4
3回答
在Cormen定理3.1中说
例如，Big-oh(n^2).是插入排序的最佳情况运行时间，而最坏情况下插入排序的运行时间<E29</code>是大-omega(N)。因此，插入排序的运行时间介于big-omega(n)和Bigoh(n^2)之间。
现在，如果我们看练习3.1-6，它会问
证明了算法的运行时间为Big-theta(g(n))当且仅当它的最坏情况运行时间为Big-oh(g(n))而最佳情况运行时间为big-omega(g(n))
我是这里唯一一个看到矛盾的人吗？
我的意思是，如果我们遵守必须证明的问题，我们得出结论:对于渐近更紧的界( Big-oh
浏览 7提问于2013-07-03得票数 1
回答已采纳
3回答
我最近读了一篇关于算法计算复杂性的文章。作者提到了“为什么插入排序在小型情况下比快速排序和冒泡排序更快”。有人能对此做出解释吗？
有人知道我上面提到的每种排序算法的实际复杂度吗？
浏览 0提问于2011-10-04得票数 6
回答已采纳
/**
* Sorts the specified sub-array of bytes into ascending order.
*/
private static void sort1(byte x[], int off, int len) {
// Insertion sort on smallest arrays
if (len < 7) {
for (int i=off; i<len+off; i++)
for (int j=i; j>off && x[j-1]>x[j]; j--)
swap(x, j,
浏览 6提问于2011-05-16得票数 11
回答已采纳
2回答
理解运行时间的重现性
、、、
我正在做CLRS算法导论的练习。这不是分级作业什么的，我只是想了解问题。
问题如下：
我们可以将插入排序表示为递归过程，如下所示。为了对A1.n进行排序，我们递归地对A1.n-1进行排序，然后将其插入排序数组A1.n-1中。为此插入排序的递归版本的运行时间编写一个递归。
解决问题的办法：
因为在最坏的情况下，插入排序数组A1需要O(n)时间。.n−1，当n=1时，我们得到了递推T(n) = O(1)，T(n−1)+ O(n)当n>1时.这个递推的解是T(n) = O(n^2)。
因此，如果是n=1，那么它已经被排序了，因此它需要O(1)时间。但我不明白重复的第二部分: O
浏览 4提问于2013-09-15得票数 9
回答已采纳
我最近对排序算法做了一次修改。在恢复时，我设想了一些代码，根据数组的大小，从两个可用的排序算法中选择最优的排序算法来排序数组。例如，它必须在insertion sort和quicksort之间进行选择。
众所周知，quicksort被广泛用于对大型数组进行排序，并且实现了其平均案例时间，即O(nlogn)，尽管最坏的时间是O(n^2)。另一方面，insertion sort不是递归的，因此当它对一个小型数组进行排序时，它可能会占用较少的CPU时间。那么，为了选择这些算法中最有效的算法，上述代码的阈值大小应该是多少呢？
其他的性能因素，比如“一个给定的序列与其排序排列的距离有多近”，现在与我无关
浏览 0提问于2015-03-28得票数 3
回答已采纳
6回答
对于通用排序，答案似乎是否定的，因为快速排序、合并排序和堆排序在平均和最坏情况下往往执行得更好。但是，插入排序似乎更擅长增量排序，即在保持列表排序的同时，在较长的一段时间内一次向列表中添加一个元素，特别是当插入排序实现为链表时(O(log )平均大小写与O( n) )。然而，堆似乎也能够执行增量排序(在堆中添加或删除单个元素的最坏情况是O(log ))。那么，与其他基于比较的排序算法或堆相比，插入排序到底提供了什么呢？
浏览 1提问于2009-04-10得票数 48
回答已采纳
我已经搜索了很长一段时间了，但是我找不到visual c++对std::sort函数使用的算法，我知道GNU C++库使用Intro排序，但是似乎没有任何消息来源说明微软的可视c++使用哪一个！
浏览 9提问于2014-04-05得票数 5
回答已采纳
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
对象存储
腾讯会议
实时音视频活动推荐
腾讯云开发者
