插入排序算法比较

Question

我最近遇到了排序技术，特别是“插入排序”。

虽然逻辑和方法是相当容易理解的，但实际的功能似乎有点复杂(如下所示)。

void InSort(int AR[], int size)
{
    int tmp,j; 
    AR[0]=INT_MIN;  //defined in limits.h , basically the smallest possible value 

     for(int i=1;i<size;i++)
     {  
       tmp=AR[i];
       j=i-1;

        while(tmp<AR[j])
         {
           AR[j+1]=AR[j];
           j--;
          }

       AR[j+1]=tmp;
     }

}

请注意，上述函数的元素是从AR1输入的。

然后，我尝试以一种更简单的方式执行这类操作，如下所示。(上升)

void iSort(int Arr[] , int size)
{
  Int temp;
  for(int i=1 ; i<size ; i++)
  {

    for(int j=0 ; j<i ; j++)
    {
       if(Arr[i]<Arr[j])
       {
        temp=Arr[i];
        Arr[i]=Arr[j];
        Arr[j]=temp;
        }
    }
  }
}

令我沮丧的是，有人告诉我，虽然这个方法会执行排序，但它不符合“插入排序”的条件，但我仍然认为它遵循同样的原则。

是这样吗？那么，我的尝试有什么特别的错误呢？更重要的是，第二个函数是否限定为插入排序？

--

我想提的是，我对编程一般来说还是比较新的，所以请原谅我看似原始的尝试，我想要做的就是学习！另外，这不是最近的C++版本，它实际上是石器时代的，所以提前道歉！

我会很高兴收到的任何投入，谢谢提前！

Answer 1

第二种算法称为气泡排序，而不是插入排序.

其思想是，在插入排序中，您在数组中获取一个元素，查找它在整个数组中的位置，然后在该位置“插入”它，将所有元素移一次。每个元素只进行一次此插入。

使用Bubble，您总是查看两个相邻的元素，并在需要时交换它们。这个名字来源于这样一种想法，即最高的元素会慢慢“气泡”到数组的顶部，因为它们一次只向上移动一步。

那么，我的尝试有什么特别的错误呢？

没什么。你碰巧意外地写了一个不同的算法。这两种算法都有O(n^2)最坏情况和平均情况时间复杂度(因为它们以不同的顺序进行或多或少的比较和赋值)，所以这并不会使情况变得更糟。

我同意Bubble排序通常是一种更简单的用代码读写的算法，所以如果性能没有问题(而且您的语言由于某种原因没有排序()函数)，那么可以随意使用它。但是，插入排序通常在大多数元素已经位于正确位置的数组上表现得更好。

当然，堆排序和合并是O(n log n)最坏的情况，而快速排序是O(n log n)的平均值，所以如果您关心排序性能，您可能应该考虑其中之一。