c++ - 将随机数插入具有排序顺序 C++ 的数组中

Question

您好，我正在尝试创建一个插入随机数的数组，但是当它插入时，数组保持在一个维护的顺序中。例如，如果数组包含 10 20 30 并且随机数是 11，则函数会将其放在 10 之后，并将 20 和 30 移到列表的下方。以下是该功能的要求。

• insertNumber 将给定的随机数插入数组并保持顺序。
• 数据数组包含从索引 0 到大小 - 2 的排序顺序的整数。
• randomNum 是要插入的整数
• data 是包含排序整数的数组
• size 是数组可以容纳的元素总数

到目前为止，这是我的代码。我的输出什么也没得到。

#include"utils.h" 

void insertNumber(int randomNum, int data[], int size)
{
    for(int i = 0; i < 10; i++)
    {
        randomNum = data[i];
        if (randomNum > data[i] && i < size - 2)
        {
            for ( int j = 0; j < 10; j--)
            {
                data[i+1] = data [i];
                i--;
            } 
        }
        data[i] = randomNum;
    }
}

void display(int data[],  int size)
{
    for (int i = 0; size < 10; i++)
    {
        cout << " " << data[i];
    }

}

Answer 1

您可以使用算法std::lower_bound来获得插入位置，并使用std::vector容器来移动元素insert

Answer 2

您可以使用 BinarySearch 搜索您的数组并查看随机数是否存在。如果它确实存在，那么您可以在现有的附近插入。

void binary_search(int A[], int key, int imin, int imax)
{
  if (imax < imin):
    // Insert key as the next element after imax
  else
    {
      // calculate midpoint to cut set in half
      int imid = midpoint(imin, imax);

      // three-way comparison
      if (A[imid] > key)
        // key is in lower subset
        binary_search(A, key, imin, imid-1);
      else if (A[imid] < key)
        // key is in upper subset
        binary_search(A, key, imid+1, imax);
      else
        // key has been found so insert it after imax
    }
}

• 代码取自维基百科http://en.wikipedia.org/wiki/Binary_search_algorithm *

Answer 3

这不是更好的实现方式吗？

#include <iostream>
#include <vector>
#include <algorithm>
#include <ctime>
#include <cstdlib>

int main() {
    std::vector<int> randomInts;
    srand(time(0));
    for(int i = 0; i < 10; i++)
        randomInts.push_back((rand()%30)+1); //Inserts random numbers 1-30.

    std::sort(randomInts.begin(),randomInts.end());
    for(auto i : randomInts)
        std::cout << i << " ";
}

输出：3 6 9 13 14 16 19 20 25 30

Answer 4

在你的函数中找到大于它的元素后插入你的随机数

for( i =0; i<size ;i++)
{
    if(data[i] > randomNumber)
    {
         valueToPush = data[i];
         data[i] = randomNumber;
         randomNumber = valueToPush;
    }
}
data[size] = randomNumber