Алгоритм сортировки массивов в пакете Java.util

Question

 /**
 * Sorts the specified sub-array of bytes into ascending order.
 */
private static void sort1(byte x[], int off, int len) {
// Insertion sort on smallest arrays
if (len < 7) {
    for (int i=off; i<len+off; i++)
    for (int j=i; j>off && x[j-1]>x[j]; j--)
        swap(x, j, j-1);
    return;
}

Из линии Arrays.java 804-814

Как указано выше, он требует использования сортировки вставками. Тем не менее, я принимаю это как Bubble Sort? Какой это на самом деле и почему?

Answer 1

Указанный код - это сортировка вставки. Пузырьковая сортировка многократно проходит через весь массив, тогда как сортировка вставкой сортирует первый элемент, затем первые два элемента, затем первые три элемента и т. Д. Вы можете сказать, потому что код имеет два индексированных цикла, тогда как внешний цикл на Bubble sort просто проверяет, в порядке ли весь массив.

Answer 2

Весь этот алгоритм сортировки представляет собой оптимизированную быструю сортировку, которая использует медиану из 3 проиндексированных элементов для получения сводного элемента, а код, который вы показали, является оптимизацией, когда входной массив (или из рекурсии) небольшой. *

Хотя цитируемая часть является вставной сортировкой, без сомнения.

Но это неправильно, просто посмотрите на эту часть алгоритма, поэтому , используя эту ссылку :

• Строки 573-577 делают сортировку вставкой для небольших входных массивов.
• Линии 581-593 выбирают элемент поворота, используя медиану 3.
• Строки 596-611 выполняют сортировку с использованием элемента pivot.
• Строки 614-616 помещают элементы элемента разделения обратно в середину (быстрая сортировка).
• Строки 619-622 рекурсии двух половин входного массива.

Хорошее объяснение о быстрой сортировке можно найти на http://en.wikipedia.org/wiki/Quicksort.

Answer 3

Bubble sort только меняет элементы, расположенные в последовательных индексах.

Обновление: комментарий в исходном коде может быть неправильным: -)

Answer 4

Для уже отсортированного массива внешний цикл пузырьковой сортировки выполняется только один раз, но внешний цикл вставки выполняется n раз (хотя для каждого внешнего цикла выполняется только 1 сравнение).

Я думаю, очевидно, что это сортировка вставки.