Сортировка вставками против.Сортировка вставками против.Двоичная сортировка вставкой
-
23-09-2019 - |
Вопрос
У меня есть пара вопросов относительно различных реализаций сортировки вставками.
Реализация 1:
public static void insertionSort(int[] a) {
for (int i = 1; i < a.length; ++i) {
int key = a[i];
int j = i - 1;
while (j >= 0 && a[j] > key) {
a[j + 1] = a[j];
--j;
}
a[j + 1] = key;
}
}
Реализация 2:
public static void insertionSort(int[] a) {
for (int i = 1; i < a.length; ++i) {
for (int j = i; j > 0 && a[j - 1] > a[j]; --j) {
swap(a, j, j - 1);
}
}
}
private static void swap(int[] a, int i, int j) {
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
Вот мой первый вопрос:Можно подумать, что первая версия должна быть немного быстрее второй (из-за меньших назначений), но это не так (или, по крайней мере, разница незначительна).Но почему?
Во-вторых, мне было интересно, что метод Java Arrays.sort() также использует второй подход (возможно, из-за повторного использования кода, поскольку метод подкачки используется в разных местах, возможно, потому, что его легче понять).
Реализация 3 (binaryInsertionSort):
public static void binaryInsertionSort(int[] a) {
for (int i = 1; i < a.length; ++i) {
int pos = Arrays.binarySearch(a, 0, i, a[i]);
int insertionPoint = (pos >= 0) ? pos : -pos - 1;
if (insertionPoint < i) {
int key = a[i];
// for (int j = i; i > insertionPoint; --i) {
// a[j] = a[j - 1];
// }
System.arraycopy(a, insertionPoint, a, insertionPoint + 1, i - insertionPoint);
a[insertionPoint] = key;
}
}
}
Имеет ли двоичная вставка какое-либо практическое применение или это скорее теоретическая вещь?На небольших массивах другие подходы работают намного быстрее, а на больших массивах сортировка слиянием/быстрая сортировка имеет гораздо лучшую производительность.
Решение
- удалить ложное утверждение
- Количество сравнений в первых двух составляет 1/2*n(n-1), не считая сравнений для внешних циклов.
- Ни одна из этих программ не имеет особого смысла для реальной работы в их нынешнем виде, поскольку они не используют имеющуюся в их распоряжении информацию.Например, во внутренний цикл легко добавить проверку, были ли сделаны какие-либо замены:если нет, то массив сортируется, и вы можете закончить, возможно, сохранив большую часть работы.На практике подобные соображения могут доминировать в среднем случае.
ПостскриптумПропустил вопрос про Java:Я понимаю, что сортировка Java — это довольно сложный алгоритм, который использует множество особых случаев, таких как специализированные случаи сортировки для небольших массивов и использование быстрой сортировки для выполнения тяжелой работы.