时间戳

首页 > 解决方案 > 是否存在这种特定排序算法不起作用的情况？

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

问题描述

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

#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;
    }

}

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

标签： clogicinsertion-sort

解决方案

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

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²)），我认为不值得关心这样的算法，最好从一开始就切换到快速排序（O(n log(n))平均运行时），堆排序（具有最大O(n log(n))运行时间，但比快速排序更差的常量）或介绍排序（前两者的混合，std::sort大多数实现中的 C++ 标准排序算法）。

推荐阅读