Сортировка списка целых чисел переменной длины, разделенных десятичными точками

Question

Мне нужна помощь.

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

Типичная (альфа?) Сортировка:

1.1.32.22

11.2.4

2.1.3.4

2.11.23.1.2

2.3.7

3.12.3.5

Правильная (числовая) сортировка:

1.1.32.22

2.1.3.4

2.3.7

2.11.23.1.2

3.12.3.5

11.2.4

У меня проблемы с выяснением того, как настроить алгоритм для такой сортировки с n числом десятичных разделителей и m количеством целочисленных полей.

Есть идеи? Это должно было быть сделано раньше. Дайте мне знать, если вам нужна дополнительная информация.

Спасибо большое! -Daniel

Answer 1

Все, что вам действительно нужно сделать, это написать "compare ()", а затем вы можете подключить это к любому алгоритму сортировки.

Чтобы написать сравнение, сравните каждое поле слева направо, и, если какое-либо поле выше, верните, что этот аргумент выше. Если один аргумент короче, предположим, что остальные поля равны 0.

Answer 2

Выезд радикс сортировка .

Answer 3

versionsort делает именно то, что вы ищете.

Алгоритм сравнения: strverscmp, вот описание на странице руководства:

Эта функция выполняет следующий. Если обе строки равны, вернуть 0. В противном случае найти позицию между двумя байтами со свойством что перед ним обе строки равны, в то время как непосредственно после этого есть разница. Найти самый большой последовательные строки цифр, содержащие (или начиная с или заканчивая) этим позиция. Если один или оба из них пусто, затем вернуть то, что strcmp () будет вернулись (числовой порядок байтовые значения). В противном случае, сравните оба цифровая строка, где цифра строки с одним или несколькими ведущими нули интерпретируются как если бы они имели десятичная точка впереди (так что в конкретные строки цифр с более перед нулями идут первые нули строки с меньшим количеством ведущих нулей). Таким образом, заказ составляет 000, 00, 01, 010, 09, 0, 1, 9, 10.

Answer 4

Это называется натуральный сорт. См. Алгоритм естественной сортировки . Например, ответ Дария Бэкона на Python:

def sorted_nicely(strings): 
    "Sort strings the way humans are said to expect."
    return sorted(strings, key=natural_sort_key)

def natural_sort_key(key):
    import re
    return [int(t) if t.isdigit() else t for t in re.split(r'(\d+)', key)]

Answer 5

Общее решение - преобразовать эту строку в массив байтов, затем использовать qsort и указать функцию сравнения.