c++ - 立即在排序位置放置一个值

Question

我有一个关于 C++ 实验室作业的问题。任务是实现一些函数来添加值，从数组中删除值等等。我现在已经完成了大部分工作，但是我在插入功能方面遇到了一些问题。该作业要求我将浮点值插入到该数组中，而无需在每次插入后使用任何算法对其进行排序。我也可能不会使用任何来自 STL 的东西。它将假设我立即将每个值插入排序位置

所以我想知道是否有人可以告诉我如何解决这个问题？

编辑 我不打算用链表来实现这个任务。它将用于我的下一个作业。

我试过根据你的伪代码写一个插入函数。虽然我没有正确理解。无论如何，这是代码。

void array_insert(data_t list[], int& space_used, data_t value)
{

   if(space_used == 0)
   {
      list[space_used] = value;    
   }
   else
   {

      for(int i = space_used+1; i >= 0; i--)
      {
         if(value > list[i])
         {
            list[i+1] = value;
            break;
         }
         else
         {
            list[i+1] = list[i];
         }
         if(i == 0)
         {
            list[i] = value;
         }
      }
   }
   space_used++;
}

终于完成了，下面是完整的代码。感谢 Mark 和 Casablanca 的帮助

Answer 1

您必须移动所有元素以便为新元素腾出空间。这是一个 O(n) 操作。既然你不能比 O(n) 做得更好，我认为使用这个简单的 O(n) 算法是合理的:

• 将 i 设置为数组中最后一个元素的索引
• 如果要插入的元素大于 a[i]，则在索引 i+1 处插入元素并停止。
• 否则设置 a[i+1] = a[i] 然后减小 i 并重复上一步。
• 如果 i 达到 0，则在开头插入元素。

这假定您的数组有空间可以插入一个额外的元素。