标签: insertion-sort

我正在解决一个问题,它涉及非常快速地排序10个数字(int32).我的应用程序需要尽可能快地对10个数字进行数百万次排序.我正在对数十亿个元素的数据集进行采样,每次我需要从中挑选10个数字(简化)并对它们进行排序(并从排序的10个元素列表中得出结论).

目前我正在使用插入排序,但我想我可以实现一个非常快速的自定义排序算法,针对10个数字的特定问题,这将超过插入排序.

有没有人知道如何处理这个问题？

我试图理解插入排序和选择排序之间的差异.

它们似乎都有两个组件:未排序列表和排序列表.它们似乎都从未排序的列表中取出一个元素并将其放入适当位置的排序列表中.我已经看到一些网站/书籍说选择排序是通过一次交换一个而插入排序只是找到正确的位置并插入它.但是,我看到其他文章说了些什么,说插入排序也交换了.因此,我很困惑.有没有规范来源？

所有,

这个问题的延续这一个.我认为STL错过了这个功能,但它只是我的恕我直言.

现在,问题.

考虑以下代码:

class Foo
{
public:
    Foo();
    int paramA, paramB;
    std::string name;
};

struct Sorter
{
    bool operator()(const Foo &foo1, const Foo &foo2) const
    {
         switch( paramSorter )
         {
             case 1:
                 return foo1.paramA < foo2.paramA;
             case 2:
                 return foo1.paramB < foo2.paramB;
             default:
                 return foo1.name < foo2.name;
         }
    }

    int paramSorter;
};

int main()
{
    std::vector<Foo> foo;
    Sorter sorter;
    sorter.paramSorter = 0;
        // fill the vector
    std::sort( foo.begin(), foo.end(), sorter );
}

在任何给定的时刻,矢量都可以重新排序.该类还具有在分类器结构中使用的getter方法.

在向量中插入新元素的最有效方法是什么？

我的情况是:

我有一个网格(电子表格),它使用类的排序向量.在任何给定时间,可以重新排序向量,并且网格将相应地显示排序的数据.

现在我需要在向量/网格中插入一个新元素.我可以插入,然后重新排序然后重新显示整个网格,但这对于大网格来说效率非常低. …

不插入排序O(n ^ 2)>快速排序O(nlogn)...所以对于小n,关系是否相同？

插入排序的运行时间为Ω(n)(当输入已排序时)和O(n ²)(当输入反向排序时).平均而言,它在Θ(n ²)时间内运行.

为什么是这样？例如,为什么平均情况不接近O(n log n)？

我正在努力找出一个有效的quicksort算法.它工作正常,但是当元素数量巨大时,需要很长时间才能运行,并且数组的某些部分是预先排序的.我正在查阅维基百科的文章,在quicksort那里我找到了这样写的:

为了确保最多使用O(log N)空间,首先递归到数组的较小一半,然后使用尾调用递归到另一个.

对于这种小阵列上的调用(即长度小于实验确定的阈值t),使用插入排序,其具有较小的常数因子并因此在小阵列上更快.这可以通过将这些数组保持未排序并在末尾运行单个插入排序传递来实现,因为插入排序有效地处理几乎排序的数组.在识别每个小段时单独插入排序会增加启动和停止许多小排序的开销,但避免浪费在多个段边界上比较密钥的工作量,由于快速排序过程的工作原因,这些密钥将按顺序排列.它还改善了缓存的使用.

我目前正在递归两个分区.知道如何实现第一个提示吗？何谓递归先入阵的小一半,并使用尾部调用递归到其他？其次,我如何insertion-sort在快速排序中实施？它是否总能提高效率,或者只有在阵列的某些部分进行预先排序时？如果是第二种情况,那么当然我无法知道何时会发生这种情况.那我insertion-sort什么时候应该包括？

在实现插入排序时,可以使用二进制搜索来定位要插入元素i的数组的第一个i-1元素内的位置.

这将如何影响所需的比较次数？如何使用这样的二进制搜索影响Insertion Sort的渐近运行时间？

我很确定这会减少比较次数,但我不确定为什么.

在"算法简介"(Corman)一书中,练习1.2-2询问了有关比较插入排序和合并排序实现的以下问题.对于大小为n的输入,插入排序以8n ^ 2步进行,而合并排序以64n lg n步进行; n的值是插入排序节拍合并排序？

虽然我对答案感兴趣,但我更感兴趣的是如何逐步找到答案(这样我就可以重复这个过程来比较任何两个给定的算法,如果可能的话).

乍一看,这个问题看起来类似于找到商业微积分中的收支平衡点,这是我5年多前的一个课程,但我不确定所以任何帮助都会受到赞赏.

谢谢

P/S如果我的标签不正确,这个问题被错误分类,或者其他一些惯例被滥用,请将惩罚限制在最低限度,因为这是我第一次发帖提问.

我正在通过"算法入门"第3版.解释的第一件事就是插入排序.在页18上有一些伪代码:

A = {5,2,4,6,1,3};

INSERTION-SORT(A)
1 for j = 2 to A.length
2   key = A[j]
4   i = j - 1

5   while (i > 0 and A[i] > key)
6     A[i + 1] = A[i]
7     i = i - 1

8   A[i + 1] = key

它说使用伪代码可以很容易地将它翻译成任何一种语言(C,C++,Java,他们没有提到,但我猜C#也是如此).由于我使用C#编程,我将其翻译为LinqPad.

int[] a = { 5, 2, 4, 6, 1, 3 };

for (var j = 1; j < a.Length; j++)
{
    var key = a[j];

    var i = j - …

我目前正在学习数据结构课程,正如您所料,我们要做的一件事就是编写一些常见的排序.在编写我的插入排序算法时,我发现它的运行速度明显快于我的教师的速度(对于400000个数据点,我的算法需要大约30秒,而他的大约需要90秒).我通过电子邮件向他发送了我的代码,当他们在同一台机器上运行时,会发生相同的结果.我们设法浪费了40多分钟,慢慢地将他的排序方法改为我的,直到它完全相同,一字不差,除了一个看似随意的事情.首先,这是我的插入排序代码:

public static int[] insertionSort(int[] A){

    //Check for illegal cases
    if (A == null || A.length == 0){

        throw new IllegalArgumentException("A is not populated");

    }

    for(int i = 0; i < A.length; i++){

        int j = i;

        while(j > 0 && A[j - 1] > A[j]){

            int temp = A[j];
            A[j] = A[j - 1];
            A[j - 1] = temp;

            j--;

        }

    }

    return A;

}

现在,此时他的代码与我的代码完全相同,除了我们交换的行A[j]和A[j - 1].他的代码执行了以下操作:

int temp = A[j - 1];
A[j …