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

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!
    }
}

现在您不再需要标志/孔，但更重要的是，您不再不必要地迭代已经排序的较小部分。

您在开始时使用 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从一开始(O(n log(n)) 平均运行时间)，heap-sort (具有最大 O(n log(n)) 运行时间，但常量比快速排序更差)或 intro-sort (前两者的混合，在大多数实现中是 C++ std::sort 的标准排序算法)。