标签: insertion-sort

我看到无处不在,无论我找到什么算法(如果有任何lol)在c ++中的向量上进行插入排序,它都不会工作,所以我假设它与我的代码有关.任何人都可以帮我找到一种方法,我可以将一个向量作为参数传递给一个方法,然后对它进行插入排序吗？此刻它等待几秒钟并显示未分类的所有值:(

插入排序代码

void insertionSort (vector<int> data, int n) 
{
int i, j, tmp;

 for (i=1; i<n; i++)
 {
     j=i;
     tmp=data[i];
     while (j>0 && tmp<data[j-1])
     {
           data[j]=data[j-1];
           j--;
     }
     data[j]=tmp;
 }

代码的重要部分

        cout << "insertion sort" << endl;
        system("pause");
        insertionSort(numberVectors, i);

让我知道,如果你不认为那些代码有什么问题,你想让我告诉你更多,应该只是这一点,其他的东西是无关紧要的,我认为

谢谢

我正在尝试理解以下代码:

/**
   * Simple insertion sort.
   * @param a an array of Comparable items.
   */
  public static void insertionSort( Comparable [ ] a )
  {
      for( int p = 1; p < a.length; p++ )
      {
          Comparable tmp = a[ p ];
          int j = p;
          for( ; j > 0 && tmp.compareTo( a[j-1] ) < 0; j-- )
              a[ j ] = a[ j - 1 ];
          a[ j ] = tmp;
      }
  }

但我不确定是什么意思,for( ; ) 所以我需要你的帮助.对不起,如果它是重复的,但我在这里和谷歌搜索,但到目前为止没有.

while循环使用线性搜索向后扫描.但是,我们知道while循环中的数组已经排序.因此,我们可以用二进制搜索替换线性搜索,以便O(n)将变为O(lg n).但是,我对此的看法是它不会有助于减少总体时间,因为我们仍然需要将元素向前移动一个索引,这将始终采用(向后步骤数(n))次.总的来说,运行时间保持为O(n ^ 2),并且在这种情况下无法实现O(n lg n).如果我以错误的方式接近这个,请告诉我.

INSERTION-SORT(A)

 for j = 2 to length[A]
  do key = A[j]
     i = j - 1

  while i > 0 and A[i] > key
    A[i+1] = A[i]
    i = i - 1

  A[i+1] = key

对于家庭作业问题,我被告知插入排序运行在8n ^ 2,合并排序运行在64(n(lg n)).作为解决方案的一部分,我得到了,有人说,插入排序快于那种只要合并为N <= 43,但老师的回答并没有真正解释为什么或者他是如何得出43.任何人都可以解释一下吗？我找出运行时间并不是那么好,所以我想要更好地理解.是的,我试过问老师,但我还是很困惑.任何帮助都会很棒!谢谢!

对不起,如果是一个基本问题...

我只是想了解更多关于算法的知识......

我编写了一个简单的代码来按升序执行插入排序,但由于某种原因,我无法按降序执行排序.

我尝试更改比较键(while(i> 0 && a [i]>键)到(i> 0 && a [i] <键))..它似乎部分工作但第一个元素没有被排序,我得到以下结果..有人让我知道我哪里错了吗？

1 11 10 9 5 4 3 2

public class InsertionSort {
    public static void main(String args[]) {
        int[] a = { 1,10,11,5, 9, 3, 2, 4 };
        // Loop through the entire array length. Consider you already have one
        // element in array, start comparing with
        // first element
        for (int j = 1; j < a.length; j++) {
            // Get the key (The value that …

在CLRS第2章中,有一个练习,询问是否将插入类型的最坏情况运行时间改进为O(n lg n).我看到了这个问题,发现它无法完成.

最坏情况下的复杂性无法改善,但memmove与单独移动阵列元素相比,使用实际运行时间会更好吗？

单独移动元素的代码

void insertion_sort(int arr[], int length)
{
    /*
    Sorts into increasing order
    For decreasing order change the comparison in for-loop
    */
    for (int j = 1; j < length; j++)
    {
        int temp = arr[j];
        int k;
        for (k = j - 1; k >= 0 && arr[k] > temp; k--){
            arr[k + 1] = arr[k];
        }
        arr[k + 1] = temp;
    }
}

用于移动元素的代码 memmove

void insertion_sort(int arr[], int …

这是我的插入排序,与"算法简介"一书中的方式完全相同:

def insertion_sort():
    A = [5,2,4,6,1,3]
    for j in range(1, len(A)):
        print 'j:'+str(j)
        key = A[j]
        print 'key:'+str(key)
        i=j-1
        print 'i:'+str(i)
        while i > 0 and A[i] > key:
            A[i+1] = A[i]
            i=i-1
            print 'new i: '+str(i)
        print 'swapping value: '+str(A[i]) + ' with value: '+str(A[i+1])
        print ' '
        A[i+1] = key
    print A

这打印:

[5, 1, 2, 3, 4, 6]

如果让它们失灵,我做错了什么？

我只是在C中进行插入排序的教程,我很难理解它的方式!运算符用作do while循环的条件.

条件只是while (!done)但我不明白它是如何知道什么不应该等于变量完成.喜欢的东西while (done==0)会让我更有意义.

我只是开始编码,如果答案非常明显,那就很抱歉!我试过谷歌搜索但我发现很难表达问题...

代码如下:

void insertionSortArray (int arr[])
{
    for(int i = 1; i < SIZE; i++)
    {
        int value = arr[i];
        int j = i -1;
        int done = 0;
        do
        {
            if (arr[j]>value)
            {
                arr [j+1] = arr[j];
                j - -;
                if (j<0)
                done = 1;
            }

            else
                done = 1;

        } while (!done);

        arr [j+1] = value;
    }
}

谢谢!!

我仍然是正确的Lisp的新手,我正在尝试构建一个简单但至少有效的插入排序 - 我想切换元素到位,但仍然有能力随后附加到我的容器.我采用了旧的C++实现:

template<typename Iter>
void insertionSort(Iter begin, Iter end){
    for (auto i = begin; i != end; ++i){
        for (auto j = i; j != begin && *(std::prev(j)) > *(j); j--){
            std::iter_swap(j, std::prev(j));
        }
    }
}

并创建了以下代码(考虑到aref并rotatef具有相当的复杂性),但它似乎没有对输入产生任何影响(UPD:现在它只是不正确地工作),我的解决方案可能出错了什么？我正在返回测试目的,我应该创建一个宏来避免传值吗？

(defparameter testa (make-array 4 :initial-contents '(2 3 1 5)))
(defun insertion-sort (vect)
    (loop for i from 0 to (1- (length vect)) do
        (loop for j from i downto 0
            until (or (= (1- j) -1) (> (aref vect …

因此，此插入排序是用x86编写的，但嵌入在C中。它还具有一个标志，在对数组的一半进行排序后，我们将其设置为保留。有什么办法可以提高性能？

void asmInsSort(int *list, int arrayLen, int halfpoint) {
 _asm
 {

    mov ecx, arrayLen
    mov esi, list
    mov ebx, halfpoint
    mov eax, 0

    more:
        cmp ecx, 0              // Compare current arrayLen w/ 0
            je  done            // If it is equal, we are done
        mov edi, eax            //J = I
        push eax                //push eax (i) to free up register for key
        mov eax, [esi + edi]    //Key = Array[i] technically j
        sub edi, 4              //J - 1
        mov edx, arrayLen       //K …