标签: insertion-sort

我目前正在学习数据结构课程,正如您所料,我们要做的一件事就是编写一些常见的排序.在编写我的插入排序算法时,我发现它的运行速度明显快于我的教师的速度(对于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 …

这个名字说的都是真的.我怀疑插入排序是最好的,因为它是一般的大多数排序数据的最佳排序.但是,由于我对数据有了更多了解,因此有可能还有其他种类可供选择.所以其他相关的信息是:

1)这是时间数据,这意味着我可以推测可以为数据排序创建有效的哈希值.2)数据不会同时存在.相反,我将阅读可能包含单个向量,或十几个或数百个向量的记录.我想在5秒钟内输出所有时间.因此,在插入数据时进行排序的排序可能是更好的选择.3)内存不是一个大问题,但CPU速度是因为这可能是系统的瓶颈.

鉴于这些条件,任何人都可以提出一个除了插入排序之外可能值得考虑的算法吗？另外,如何定义"主要排序"以确定什么是良好的排序选项？我的意思是我如何查看我的数据并决定'这不像我想象的那样排序,也许插入排序不再是最好的选择'？任何与文章相关的链接都可以理解,该文章考虑了流程复杂性,这些文章更好地定义了相对于学位数据的复杂性.

谢谢

编辑:谢谢大家的信息.我现在将进行简单的插入或合并排序(无论我已经预先编写).但是,一旦接近优化阶段,我将尝试其他一些方法(因为他们需要付出更多努力才能实现).我很感激帮助

我有一个NSMutableArray排序对象,它们显示在UITableView中.

我想在数组中插入一个新对象并更新表视图 - 这需要新插入对象的索引.

我找不到任何系统消息告诉我正确的插入索引到数组,我需要更新表视图.

我能找到的最好的是:

• 添加新对象
• 分类
• 使用旧的数组副本,找到新对象的位置(需要搜索)

要么

• 写我自己的插入位置搜索

当然,必须有一条消息来找到排序数组中的插入位置？或者我错过了一些明显的东西？

美好的一天SO社区,

我是一名CS学生,目前正在进行一项结合MergeSort和InsertionSort的实验.可以理解,对于某个阈值,S,InsertionSort将比MergeSort具有更快的执行时间.因此,通过合并两种排序算法,将优化总运行时间.

然而,在多次运行实验后,使用1000的样本大小和不同大小的S,实验结果每次都没有给出确定的答案.这是获得更好结果的图片(请注意,结果的一半时间不是确定的):

现在,尝试使用样本大小为3500的相同算法代码:

最后,尝试相同的算法代码,样本大小为500,000(请注意,y轴以毫秒为单位:

虽然逻辑上,当S <= 10时,Hybrid MergeSort会更快,因为InsertionSort没有递归开销时间.但是,我的迷你实验的结果却说不然.

目前,这些是教给我的时间复杂性:

MergeSort:O(n log n)

插入排序:

• 最佳案例:θ(n)
• 最坏情况:θ(n ^ 2)

最后,我找到了一个在线资源:https://cs.stackexchange.com/questions/68179/combining-merge-sort-and-insertion-sort,其中说明:

Hybrid MergeInsertionSort:

• 最佳案例:θ(n + n log(n/x))
• 最坏情况:θ(nx + n log(n/x))

我想问一下CS社区中是否有结果显示混合MergeSort算法比低于某个阈值S的普通MergeSort算法更有效,如果是,为什么？

非常感谢SO社区,这可能是一个微不足道的问题,但它确实会澄清我目前关于时间复杂性和东西的许多问题:)

注意:我使用Java来编写算法,运行时可能会受到java在内存中存储数据的方式的影响.

Java中的代码:

 public static int mergeSort2(int n, int m, int s, int[] arr){
        int mid = (n+m)/2, right=0, left=0;
        if(m-n<=s)
            return insertSort(arr,n,m);
        else
        {
            right = mergeSort2(n, mid,s, arr);
            left = mergeSort2(mid+1,m,s, arr);
            return right+left+merge(n,m,s,arr);
        }      
    }

    public static int insertSort(int[] arr, int …

我有一个几乎排序的链表,其中至少包含两个元素,仅仅是不同的,只有1元素不在它的位置.一些例子:

28 (144) 44 52 60
60 68 76 84 (65) 100

结构看起来像这样:

struct node {node * next; int val;}

这是我的分离功能(并不总是有效):

node *detach(node *&l)
{
    if(l->val>l->next->val)
    {
        node *removed=l;
        l=l->next;

        return removed;
    }

    node *first=l->next->next;
    node *prev=l;

    while(first!=NULL)
    {
        if(prev->next->val>first->val)
        {
            node *removed=prev->next;
            prev->next=removed->next;

            return removed;
        }

        prev=prev->next;
        first=first->next;
    }

    return NULL;
}

我应该改变它才能正常工作？

我正在阅读一些关于Python,数据结构以及算法分析和设计的书籍.我想真正理解编码的内部和外部,并成为一个有效的程序员.要求本书澄清是很困难的,因此我对stackoverflow的问题.我真的觉得算法和递归具有挑战性...我在下面发布了一些代码(插入排序),我正在试图理解究竟发生了什么.一般来说,我明白应该发生什么,但我并没有真正了解方法和原因.

从尝试分析Python Idle上的代码片段,我知道:

key (holds variables) = 8, 2, 4, 9, 3, 6

然后:

i (holds the length) = 7 ( 1, 2, 3, 4, 5, 6, 7)

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

mylist = [8, 2, 4, 9, 3, 6]

for j in range(1,len(mylist)):
    key = mylist[j]
    i = j
    while i > 0 and mylist[i-1] > key:
        mylist[i] = mylist[i - 1]
        i -= 1
        mylist[i] = key

我最近读了一篇文章,讨论了算法的计算复杂性.作者提到"为什么插入排序比小型案例的快速排序和冒泡排序更快".有人可以为此做出一些解释吗？

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

所以我有一个任务,我给出一个随机的数字列表,我需要使用插入排序对它们进行排序.我必须使用单链表.我环顾四周其他帖子但似乎没有任何帮助.我得到什么插入排序但我只是不知道如何在代码中写它.

Node* insertion_sort(Node* head) {
  Node* temp = head_ptr;
  while((head->n < temp->n) && (temp != NULL))
    temp = temp->next;
  head->next = temp->next;
  temp->next  = head;
  head->prev = temp;
}

我不知道这是对的还是现在要做什么

所以我有一个向量,我希望元素始终排序.我应该如何将元素插入到该向量中,并在弹出它们时保持元素排序.std::lower_bound然而,我调查了与我想要的相反的东西.

例如,这就是我想要的:当我弹出向量中的所有元素时,它应该是:1 2 3 4 5.这意味着向量必须将它们存储为5 4 3 2 1.如果使用下限,则向量将它们存储为1 2 3 4 5,并将其弹出为5 4 3 2 1.此外,将传入一个比较仿函数,以便该lower_bound函数使用比较仿函数.有没有办法与比较仿函数相反？

所以我正在经历不同的排序算法.但几乎所有的排序算法都需要2个循环来对数组进行排序.冒泡排序和插入排序的时间复杂度对于最佳情况是O(n),但是O(n ^ 2)是最坏情况,其再次需要2个循环.有没有办法在单个循环中对数组进行排序？