c - 如何在给定的数组中按顺序插入元素？

Question

假设数组中有以下数字:1、3、6、15如果用户输入某个整数，例如数字 5，那么如何将其以正确的顺序插入到上面的数组中，以便打印以下新数组:1, 3, 5, 6, 15。要使用的数组是一个变长数组，我们假设用户以已排序且非递减的顺序输入数组的数字，因此不需要排序，但只是为了在正确的位置插入一个元素(也由用户输入)。下面我有关于我走了多远的代码，因为我不知道使用什么命令将 x 插入数组，而且我是 C 编程的新手。

#include <stdio.h>

int insertion_array (int n, int ary[*]); 

int main (void)
{

    int n; // size    
    int x; // The element to be inserted in the array    
    int i, j;
    printf("Enter size of array: ");

    scanf("%d", &n);
    printf("Enter the value of x: ");

    scanf("%d", &x);

    int ary[n];    
    for(i = 0; i < n; i++)
    {
        printf("Enter number %d: ", i + 1);
        scanf("%d", &ary[i]);
    } // for

    return 0;
} // main

Answer 1

我可以想出一个简单的 O(n) 算法:

1. 使用二分查找来找到插入的位置，比如位置 5
2. 将第 5 位之后的所有数字右移
3. 将位置 5 赋给新整数

但是也有O(lgn)的插入算法，比如AVL树、RB树等，但是要复杂得多。

#include <stdio.h>
#include <stdlib.h>

int binsearch(int *arr, int size, int key)
{
  int low = 0, high = size - 1;

  if (key > arr[high]) return size;

  while (high > low) {
    int mid = (low + high) / 2;
    if (arr[mid] > key) high = mid;
    else low = mid + 1;
  }

  return low;
}

int main()
{
  int size = 10;
  int *arr = (int *)malloc(size * sizeof(int));

  int elem, len = 0;
  arr[len++] = 0;

  while (scanf("%d", &elem) != EOF) {

    int pos = binsearch(arr, len, elem);

    printf("%d\n", pos);

    int i;
    for (i = len-1; i >= pos; --i)
      arr[i+1] = arr[i];
    arr[pos] = elem;

    ++len;

    for (i = 0; i < len; ++i)
      printf("%d ", arr[i]);
    printf("\n");
  }

  free(arr);

  return 0;
}