是否存在这种特定排序算法不起作用的情况？

Question

基本上，我想知道在执行以下代码以执行插入排序时是否会出现任何可能的逻辑错误。我注意到一些示例使用带有逻辑 AND 运算符的 while 循环，但我认为我可以通过使用标志来监视排序列表中的任何值是否小于当前索引来实现相同的输出未排序列表的位置，并通过存储该较小值的位置。

#include<stdio.h>
void insertion(int size, int[*]);
int main()
{
  int size;
  printf("Size of Array: ");
  scanf("%d",&size);
  int ary[size];
  for(int i=0; i<size; i++)
  scanf("%d",&ary[i]);
  insertion(size, ary);
  return 0;
}
 void insertion(int size, int A[size])
 {
   int value;
   int hole;
   int flag;

   for(int i=1; i<size; i++)
     {
       value = A[i];//the value of the current index of the unsorted list 
                    //gets stored in variable named value
       flag = 0;
           for(int j=i-1; j>=0; j--)
              {
                 if(A[j]>value)
                    {
                       flag = 1;
                       hole = j; //index position where value will be 
                                 //inserted into
                       A[j+1] = A[j];
                    }
              }
          if(flag) //ensures that insertion occurs only when one of the 
                   //sorted elements is less than value
     A[hole] = value;
    }

  for(int i=0; i<size; i++)
  printf("%d ",A[i]);
}

`

以下方法是使用 while 循环而不是标志的替代变体：

void unshuffle( int size, int* A )
{
int value;
int position;

for( int i=1; i<size; i++ )
    {
    value = A[i];
    position = i;

    while( A[position-1]>value && position>0 )
        {
        A[position] = A[position-1];
        position--;
        }
    A[position] = value;
    }

}

就效率而言，这是编写插入排序的首选方法吗？

Answer 1

您的方法效率越来越低；考虑以下算法变体：

for(int j=i-1; j>=0; j--)
{
    if(A[j] > value)
    {
        A[j+1] = A[j];
    }
    else
    {
        A[j+1] = value; // worst that could happen: self asignment;
                        // still less costly than another `if`!

        break;          // you're in the sorted part of the array, so all other
                        // values are smaller or equal as well -> can exit!
    }
}

现在您不再需要 flag/hole，但更重要的是，您不再不必要地遍历已排序的较小部分。

您在开始时使用 while 循环中的双重条件实现的效果相同...

实际上有一个错误，如果当前元素小于所有已经排序的元素，则永远不会输入 else 子句，因此该元素不会插入到第一个位置。不过，修复起来很容易：

int j;
for(j = i-1; j >= 0; j--)
{
    if(A[j] > value)
    {
        A[j+1] = A[j];
    }
    else
    {
        break;
    }
}
A[j+1] = value; // (still self-assignment possible)
                // if j got -1: insert at 0, so fine

现在我们更接近原始的 while 循环...

你仍然在尝试优化一个以效率低下而闻名的算法（O(n²) 的平均（！）运行时间），我认为不值得关心这样的算法，更好切换到 quick-sort right from start (O(n log(n)) average runtime), heap-sort (with maximum O(n log(n)) runtime, but worse constants than quicksort) or intro-sort（前两个的混合，在大多数实现中是 C++ 的标准排序算法 std::sort）。

是否存在这种特定排序算法不起作用的情况？

Are there any cases where this particular sorting algorithm would not work?

c

logic

insertion-sort