вставка в отсортированный список рекурсивно

Как бы вы вставили в отсортированный массив, предполагая, что целые числа были отсортированы в порядке возрастания. Мне сказали использовать бинарный поиск, но это вернет только позицию элемента.

Примером псевдокода может быть grate.


java sorting binary-search
person Raju Kumar    schedule 09.02.2012    source источник
comment
это домашнее задание, а затем добавить тег домашнего задания?   -  person Hemant Metalia    schedule 09.02.2012

Ответы (2)


arrow_upward
2
arrow_downward

  1. используйте бинарный поиск (если это связанный список, повторение может быть довольно дорогим), чтобы найти место, которому принадлежат новые элементы
  2. если значение одинаковое - ничего не делать
  3. Если значение отличается, нужно вставить сюда, что означает перемещение всего назад с этой позиции в конец на единицу (если это связанный список, просто означает вставку нового узла в этой точке, не нужно делать все смещение)
  4. вставьте новый элемент в индекс.
person Nim    schedule 09.02.2012

arrow_upward
1
arrow_downward

Предполагая, что вы используете статический массив, например. нет связанного списка

Ниже приведен способ работы с массивом строк, который вы можете настроить в соответствии с вашими требованиями.

// Создать массив с упорядоченным списком элементов String[] sortedArray = new String[]{"ant", "bat", "cat", "dog"};

// 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

person Hemant Metalia    schedule 09.02.2012