递归插入排序列表

Question

假设整数已按升序排序，如何插入到已排序的数组中。有人告诉我使用二分搜索，但这只会返回元素的位置。

伪代码的一个例子是 grate。

Answer 1

1. 如果值相同，则使用二分搜索（如果这是一个链表，迭代可能会非常昂贵）来查找新项目所属的位置
2. - 不执行任何操作
3. 如果值不同，需要在此处插入，这意味着移动从这个位置到末尾的所有内容都加一（如果这是一个链表，则仅意味着在此时插入一个新节点，不必进行所有移位）
4. 在索引处插入新项目。

Answer 2

假设您使用静态数组，例如无链表

以下是一种处理字符串数组的方法，您可以根据您的要求进行自定义

// 创建具有有序项目列表的数组
String[]sortedArray = new String[]{"蚂蚁", "蝙蝠", "猫", "狗"};

// Search for a non-existent item and then insert it
int index = Arrays.binarySearch(sortedArray, "cow");
if (index < 0) {
    // Compute the insert index
    int insertIndex = -index-1;

    // Insert the new item into sortedArray. The example here creates
    // a new larger array to hold the new item.
    String[] newSortedArray = new String[sortedArray.length+1];
    System.arraycopy(sortedArray, 0, newSortedArray, 0, insertIndex);
    System.arraycopy(sortedArray, insertIndex,
                     newSortedArray, insertIndex+1,
                     sortedArray.length-insertIndex);
    newSortedArray[insertIndex] = "cow";
    sortedArray = newSortedArray;
}

请参阅http://www.exampledepot.com/egs/java.util/coll_InsertInArray。 html