C++：在有序数组中插入一个数仍保持有序 |21xrx.com

C++：在有序数组中插入一个数仍保持有序

2023-06-30 14:32:11 深夜i -- --

C++ 有序数组插入保持有序

当我们在处理一个有序数组时，有些时候需要插入一个新数。但是如果我们不小心打乱了数组的有序性，那么这个数组就不再有用，我们需要重新排序。为了避免这种情况，我们要通过一个小技巧来确保插入新数的同时仍然保持有序。这里我们介绍的技巧是如何使用C++语言，在有序数组中插入一个数仍保持有序。

要实现这个技巧，我们首先需要预留出一个数的位置，然后将待插入的数与该位置进行比较。如果待插入数大于该位置的值，那么我们就向右侧移动该位置的值并将待插入数插入该位置。反之，如果待插入数小于该位置的值，那么我们就向左侧移动该位置并将待插入数插入该位置。通过这种方法，我们可以确保插入新数的同时仍然保持有序。

为了更好地理解这个过程，下面给出C++代码实现：


#include <iostream>
using namespace std;
void sortedInsert(int arr[], int& n, int x)
{
  int i;
  for (i = n -1; (i >= 0 && arr[i] > x); i--)
  {
    arr[i+1] = arr[i];
  }
  arr[i+1] = x;
  n++;
}
int main()
{
  int arr[] = 2;
  int n = sizeof(arr)/sizeof(arr[0]);
  int x = 9;
  sortedInsert(arr, n, x);
  for (int i=0; i<n; i++)
  {
    cout << arr[i] << " ";
  }
  return 0;
}

这里我们定义了一个sortedInsert函数来排序数组。函数传入三个参数：数组的名称、数组的长度以及待插入的数。sortedInsert函数使用for循环来遍历数组，如果待插入数大于当前位置的数，那么我们就向右侧移动该位置并将待插入数插入。反之，如果待插入数小于当前位置的数，那么我们就向左侧移动该位置并将待插入数插入。最后，该函数将数组的长度加1，因为我们已经插入了一个新的数。

在main函数中，我们定义了一个有序数组arr，并使用sizeof运算符计算数组长度。这里我们可以将待插入数x设为9。我们可以看到，当我们打印数组arr时，我们已经成功地将数值9插入到数组中，并且该数组仍然保持有序。

这样，我们就学会了如何使用C++语言在有序数组中插入一个数仍保持有序。这个小技巧可以帮助我们在处理排序数组时更加高效，并保持数组的有序性，避免无谓的重新排序。

上一篇: idea打包java可执行jar包

下一篇: C++实现十进制转二进制函数

评论区

()

相似文章