Как отсортировать почти отсортированный массив в кратчайшие сроки? (Джава)
Java имеет пул строк, в котором Java управляет распределением памяти для объектов String. См. String Pools в Java
Когда вы проверяете (сравниваете) два объекта с помощью оператора ==, он сравнивает равенство адресов в пуле строк. Если два объекта String имеют одинаковые адреса, то он возвращает true, в противном случае false. Но если вы хотите сравнить содержимое двух объектов String, вы должны переопределить метод equals.
equals - фактически метод класса Object, но он переопределяется в класс String и дается новое определение, которое сравнивает содержимое объекта.
Example:
stringObjectOne.equals(stringObjectTwo);
Но помните, что это относится к случаю String. Если вы хотите сравнить регистр без учета регистра, вы должны пойти для метода equalsIgnoreCase класса String.
Давайте посмотрим:
String one = "HELLO";
String two = "HELLO";
String three = new String("HELLO");
String four = "hello";
one == two; // TRUE
one == three; // FALSE
one == four; // FALSE
one.equals(two); // TRUE
one.equals(three); // TRUE
one.equals(four); // FALSE
one.equalsIgnoreCase(four); // TRUE
8 ответов
На самом деле Википедия содержит реализацию на Java для сглаживания сортировки. Вы можете найти его здесь:
Сортировка коктейлей
Если вам нужен простой алгоритм, который легко реализовать, вы можете выполнить сортировку коктейлей . Он будет достаточно хорошо работать с почти отсортированным вводом.
Как заметил Botz3000, вы не можете выполнить такую операцию быстрее, чем O (N). Самым основным элементом любого алгоритма будет поиск тех записей в массиве, которые не соответствуют порядку. Для этого требуется O (N), даже до того, как вы поймете, что с ними делать.
Если действительно количество «неупорядоченных» элементов на несколько порядков меньше общего количества элементов, вы можете использовать следующее алгоритм (предполагая связанный список):
- Найти все неупорядоченные элементы и извлечь из исходного списка в отдельный список, O (N)
- Результатом являются два списка: отсортированный список и короткий извлеченный list
- Вставьте каждый из извлеченных элементов в отсортированный список. Это будет O (log (N)) для каждого, всего O (Xlog (N)), где X - количество извлеченных элементов. Если X очень мало относительно N, в итоге вы получите O (N).
[Sun] JDK7 имеет (или будет иметь) реализацию Tim sort (из Python). Это сортировка слиянием, которая использует порядок, уже существующий в массиве.
Просто чтобы положить его на стол, хорошо реализованная пузырьковая сортировка, безусловно, была бы здесь самым простым алгоритмом. В худшем случае O (n * m), где m - количество перемещений. Часть m сильно зависит от схемы смещений, обычно общая сложность будет O (n).
Реализуйте то, что мы в школе называли сортировкой Shell . Это пузырьковые подмассивы. Подмассив с шагом k - это массив элементов с указателями 0, k, 2k, 3k ...
Если вы выберете k = 3i + 1 и выполните несколько пузырьковых сортировок, начиная с более высокого до 0, раз будет меньше на почти отсортированном массиве.
Вы правы насчет невозможности достижения O (N), но, предполагая многоядерную машину (которая у меня есть), мы можем немного обмануть, используя алгоритм параллельной сортировки.
Smoothsort или Timsort - отличные алгоритмы, и их было бы разумно использовать.
Я бы добавил, что вы можете не осознавать, что скромная сортировка вставкой адаптивен. Действительно, для действительно почти отсортированных списков, как вы, кажется, понимаете (я не могу сделать резервную копию ссылками), это быстрее, чем более сложные алгоритмы. Проблема в том, что если ввод почти не отсортирован, он быстро деградирует до O (n ^ 2). Тем не менее, его очень просто реализовать правильно, поэтому, если вы точно знаете, что ваш ввод всегда почти отсортирован, это будет хорошим выбором.