У меня есть пара вопросов относительно различных реализаций сортировки вставкой.
Реализация 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 () также использует второй подход (возможно, из-за повторного использования кода, потому что метод swap используется в разных местах, может быть, потому что его легче понять).
Реализация 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;
}
}
}
Является ли двоичная вставка своего рода практическим применением или это скорее теоретическая вещь? На небольших массивах другие подходы выполняются намного быстрее, а на больших массивах производительность слияния / быстрой сортировки намного выше.