Если эта близость формирует линейный спектр (такой, что близость к чему-либо подразумевает близость к другим вещам, которые находятся рядом с ним, а отсутствие близости подразумевает, что она не близка к этим близким), тогда вы можете просто выполнить двоичную или интерполяционную сортировку при вставке для близости обрабатывает одну дополнительную сложность: в каждой точке вы должны видеть, увеличивается или уменьшается близость ниже или выше.
Например, если мы рассмотрим буквы - A близко к B, но далеко от Z - тогда уже существующие элементы можно отсортировать, скажем: A, B, E, G, K, M, Q, Z. Чтобы вставить, скажем, «F», вы начинаете со сравнения со средним элементом, [3] G, и следующим, что: [4] K. Вы устанавливаете, что F ближе к G, чем K, поэтому лучшее совпадение либо в G или налево, и мы двигаемся на полпути в неисследованную область слева ... 3/2 = [1] B, а затем E, и мы находим E ближе к F, поэтому совпадение либо в E, либо в это верно. Делим пополам пространство между нашими более ранними проверками в [3] и [1], мы проверяем в [2] и находим его одинаково удаленным, поэтому вставляем его между ними.
РЕДАКТИРОВАТЬ: он может работать лучше в вероятностных ситуациях и требовать меньшего количества сравнений, чтобы начинать с концов спектра и прокладывать себе дорогу (например, сравните F с A и Z, решите, что он ближе к A, посмотрите, ближе ли A или на полпути [3] G). Кроме того, было бы неплохо закончить сравнением с несколькими ближайшими точками по обе стороны от того места, куда вас привел двоичный код / интерполяция.