按照输入值对数组进行排序

Question

我需要帮忙编写一个循环，如果新添加的值比现有值低，则将数组元素向右移动，因此在输入新值时对数组进行排序。

数组最初为空。

我尝试了几个循环，但它们似乎都不适用于我的情况，因为它们是针对已经填满的数组使用的循环。

以下是我目前拥有的代码。

if(index < 0)
    index = -(index + 1);

if(arr[index] > key)
    for(int i = 0; i < count -1; i++) {
        arr[index + i] = arr[index + i + 1];
    }

arr[index] = key;

这个索引是从二分查找中得出的。

例如，如果我首先输入80，它将占据arr[0]的位置。然后我输入45，它也将占据arr[0]的位置。

由于45（关键字）比现有的arr[0]（80）小，所以80要向上移动一个索引。

- FiftySentos

---

要理解您代码中的问题，我们需要了解您如何设置整个系统。索引/计数是如何获取它们的值的？！在某些情况下，看到索引可能小于0真的很令人困惑！ - GhostCat

Answer 1

您可能希望循环执行以下操作：

1. 移动索引大于index的元素，以便为新元素腾出空间，
2. 然后将该元素添加到给定的索引。

for (int  i = count; i > index; i--) {
    arr[i] = arr[i - 1]; // shifts the elements to the one place right
}
arr[index] = key; // add the key to the given index

注意：计数是数组中当前元素的数量，它小于arr.length。

- Moonstruck

---

谢谢。那个方法可行。从数组末尾向下操作绝对比我之前尝试的更有意义。 - FiftySentos

当然可以！很乐意帮忙。 - Moonstruck

@FiftySentos 请将此答案标记为“正确”，以便Jainul获得应有的荣誉，并且其他遇到相同问题的人可以轻松找到它。 - Thomas

如果数组达到当前长度，您可能希望添加重新创建更大的数组。顺便说一下，这就是“Arraylist”的工作原理，它在内部保持一个数组，并在达到当前容量时将其长度加倍。 - Squirrelkiller

Answer 2

你可以采用以下方法：

首先，你需要：

1. 一个计数器，告诉你还有多少个“未使用”的数组元素；如果最后发现你的数组“已满”，那么交换索引1到2、2到3等就没有意义了。 2. 注意索引，避免超出数组的长度。

然后就很简单了：

1. 迭代当前数组，找到第一个大于key的索引（我们称之为n）。 2. 然后转向最后一个“正在使用”的数组索引……从那里开始向右移动值。 3. 最后，在将arr[n]移动到arr[n+1]之后，将arr[n]赋值为key。

- GhostCat

Answer 3

看起来你试图将数组元素向错误的方向移动。

假设 index = 0 和 i = 0，你最终会得到：

arr[0] = arr[1];

当你可能想要反过来时。

- Joe C

---

arr[index + i + 1] = arr[index + i] 会使得 arr[1] = arr[0] 吗？ - FiftySentos