68
Более детально:
–
рассматриваем первый элемент списка как отсортированный подсписок
(то есть первый элемент списка);
–
вставим второй элемент в отсортированный подсписок, сдвигая первый
элемент по
мере необходимости, чтобы освободить место для вставки нового
элемента;
–
вставим третий элемент в отсортированный подсписок (из двух
элементов), сдвигая элементы по мере необходимости;
–
повторяем до
тех пор, пока все значения не будут вставлены на свои
соответствующие позиции.
//
вставками
public static void insertionSort (Comparable[] list) {
for (int index = 1; index < list.length; index++)
{
Comparable key = list[index];
int position = index;
// Shift
larger values to the right
while (position > 0 &&
key.compareTo(list[position-1]) < 0) {
list[position] = list[position-1];
position--;
}
list[position] = key;
}
}
}
Пример сортировки вставками на рисунке 5.5:
Рисунок 5.5 – Алгоритм сортировки вставками
