如何按字母顺序插入值到数组?

Question

我需要insert函数接受一个参数，然后将其添加到列表中，但它不是简单地将其添加到末尾，而是找到字母顺序位置并将其添加到那里。所以，如果数组是{1,3,4}我们向数组中添加2，它会找到添加它的下标，也就是下标1，把所有的下标移到插入点之后。然而，我就是不知道怎么写它背后的逻辑。

假设数组未满，并且有额外的空间来向下移动数组中的项。

我不能使用另一个数组来复制值或类似的东西。我需要在数组中向下移动值，并在插入函数内的适当点插入值。

/*************************************
* insert()
*************************************/
bool people::insert(person arg)
{
person temp;
int i, value, insertionPoint;
// Check to see if array is full
cout << "Array size is " << len << endl;
if (len >= LIST_SIZE)
{
cout << "Array null" << endl;
return false;
}
// Adds item if array is empty.
if (len == 0)
{
cout << "FIRST VALUE ADDED which is: " << arg.firstName << endl;
map[0] = arg;
}
// Find Insertion Point
for (i = 0; i < len; i++)
{
if(arg < map[i])
{
insertionPoint = i;
}
else
{
insertionPoint = len;
}
}
for (i = insertionPoint; value > insertionPoint; value--)
{
map[value] = map[value - 1];
}
return true;
}

Answer 1

你必须从列表的尾部开始。它看起来像你有map[]作为你的数组和len作为当前元素的数量。

我们来看一些代码。你找到插入点的循环是有缺陷的。除了二进制搜索更快之外:

int insertionPoint = len;
for (int i = 0; i < len; i++)
{
if(arg < map[i])
{
insertionPoint = i;
break;
}
}

这样干净多了。一旦找到了插入点，就没有理由继续搜索了。

现在已经设置了insertionPoint，因此需要腾出空间。你想把从[insertionPoint]到[len-1]的所有指针向上移动一个点，但是如果你从[insertionPoint]开始，你就会遍历其余的指针。

所以你倒着做:

for (int index = len; index > insertionPoint; --index) {
map[index] = map[index - 1];
}

此时，您可以:

map[insertionPoint] = arg;
++len;

---

我添加这个，因为OP说他不允许使用break。我不知道这是为什么,但是好。

int insertionPoint = 0;
while (insertionPoint < len && arg < map[insertionPoint]) {
++insertionPoint;
}

这个循环不会超过结尾。如果我们在末端，insertionPoint就等于len，这是它需要的。但是循环会在应该停止的时候停止。