c - 将元素插入排序数组

Question

我有一个排序，我需要插入元素并将其排序到后续的binary-searches 调用。我应该使用什么算法？或者这可能是一个过早的优化，我应该只插入元素并调用 shell-sort（我将实现作为当前的替换）？

如果此信息有用：元素的数量可能真的很大。它确实是可变的，可以容纳 1 到 10 甚至 1 到 1000+ 个元素。如果你好奇为什么这个变量太多，我正在写一个解析。

Answer 1

如果数组的大小不能容纳更多条目，则需要分配另一个更大的数组，将所有条目移动到新条目所在的位置，将条目放在那里，最后将剩余条目移动一个位置比他们。之后，您可以释放旧的和现在太小的阵列并保留新的阵列。你可以使用memmove或memcpy去做。

这样做，当您需要分配一个新的更大的数组时，您应该分配比您立即需要的更大的数组（内存页面大小的倍数会很好），否则所有分配和释放的成本都会很高。

例子：

int *array[] = malloc(3*sizeof(int));
array[0] = 0;
array[1] = 2;
array[2] = 3;

// To insert 1 for example you will have to do...
int *new_array[] = malloc(4*sizeof(int)); // Just for the example I make a tight fit, on the code you should allocate it a bit bigger if you expect more inserts to avoid unnecessary mallocs and frees

memmove(new_array,array,sizeof(int)); // Moving the 0
new_array[1] = 1; // Inserting the new element
memmove(new_array[2],array[1],2*sizeof(int)); // Moving the 2 and 3

free(array); // Get rid of the old array
array = new_array;
new_array = NULL;