Блог

Я новичок в алгоритмах, поэтому, пожалуйста, простите меня, если это звучит банально или глупо.

Я хочу знать вот что: вместо добавления данных в какой-то список, а затем выполнения сортировки в списке, существует ли метод (структура данных алгоритм), который позволяет мне сортировать данные во время добавления, или, другими словами, вставляет данные в надлежащее место?

например: если я хочу добавить ‘3’ к {1,5,6}, вместо того, чтобы добавлять его в начале или конце и затем сортировать список, я хочу, чтобы ‘3’ шло после ‘1’ «напрямую».

Спасибо

Если вы используете двоичное дерево поиска вместо массива, сортировка будет происходить «автоматически», потому что это уже сделано методом вставки узлов. Таким образом, двоичное дерево всегда сортируется, и его легко просматривать. Единственная проблема заключается в том, что когда у вас уже есть (более или менее) отсортированные данные, дерево становится несбалансированным (вот где вступают в игру красно-черные деревья и другие вариации).

Вы хотите постоянно поддерживать отсортированный массив, поэтому вы должны найти правильное место в последовательности для каждого нового элемента, который вы хотите добавить в массив. Это можно сделать эффективно ( O(logn) по сложности), используя модифицированный алгоритм бинарного поиска.

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

• Используйте двоичный поиск, чтобы найти, куда следует вставить значение, и вставьте значение туда.

• Выполните цикл с конца списка, переместив все более высокие значения на один шаг вверх, и поместите значение в пробел перед наименьшим более высоким значением.

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

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

При бинарном поиске вам не нужно просматривать каждый элемент, но даже тогда вам часто нужно получить больше элементов из списка, как при последующей сортировке.

Итак, с точки зрения производительности сортировка insert уступает сортировке post.

Вот код golang, который сортирует входные данные на лету

Что я здесь делаю, так это то, что я определяю позицию, в которую, возможно, будут помещаться входные данные, с помощью двоичного поиска, а затем разбиваю уже отсортированный массив на разделы, чтобы он соответствовал элементу, добавляю к первой части, а затем соединяю две части.

временная сложность = Log N (для определения позиции) 3N (для создания фрагментов и добавления для каждого ввода)

 package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
    "strings"
)

func main() {
    reader := bufio.NewReader(os.Stdin)
    var a []int
    for {
        fmt.Print("Please enter a value:")
        text := readLine(reader)
        key, _ := strconv.ParseInt(text, 10, 0)
        pos := binarySearch(a, 0, len(a)-1, int(key))
        p1 := append([]int{}, a[:pos]...)
        p2 := a[pos:]
        p1 = append(p1, int(key))
        p1 = append(p1, p2...)
        a = p1
        fmt.Println(a)
    }
}

func binarySearch(a []int, low int, high int, key int) int {
    var result int
    if high == -1 {
        return 0
    } else if key >= a[high] {
        return high   1
    } else if key <= a[low] {
        return low
    }
    mid := (high   low) / 2
    if a[mid] == key {
        result = mid
    } else if key < a[mid] {
        return binarySearch(a, low, mid-1, key)
    } else if key > a[mid] {
        return binarySearch(a, mid 1, high, key)
    }
    return result
}

func readLine(reader *bufio.Reader) string {
    text, err := reader.ReadString('n')
    if err != nil {
        fmt.Println(err)
    }
    text = strings.TrimRight(text, "n")
    return text
}