![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Сортировка вставками — простой алгоритм сортировки. Хотя этот алгоритм сортировки уступает в эффективности более сложным (таким как быстрая сортировка), у него есть ряд преимуществ:
§ эффективен на небольших наборах данных, на наборах данных до десятков элементов может оказаться лучшим;
§ эффективен на наборах данных, которые уже частично отсортированы;
§ это устойчивый алгоритм сортировки (не меняет порядок элементов, которые уже отсортированы);
§ может сортировать список по мере его получения;
§ использует O(1) временной памяти, включая стек.
Минусом же является высокая сложность алгоритма: O(n ²).
Принцип действия:
Массив разделяется на две части: отсортированную и неотсортированную. Элементы из неотсортированной части поочередно выбираются и вставляются в отсортированную часть так, чтобы не нарушить в ней упорядоченность элементов. В начале работы алгоритма в качестве отсортированной части массива принимают только один первый элемент, а в качестве неотсортированной части – все остальные.
Пример
К 503 087 512 061 908 170 897 275 653 426 154 509 612 677 765 703
i=1 503
i=2 087 503
i=3 087 503 512
i=4 061 087 503 512
И.т.д.
Фрагмент программы:
for (int i = 0; i < size - 1; ++i) {
/* устанавливаем начальное значение минимального индекса */
int min_i = i;
/* находим минимальный индекс элемента */
for (int j = i + 1; j < size; ++j) {
if (array[j] < array[min_i]) {
min_i = j;
}
}
/* меняем значения местами */
int temp = array[i];
array[i] = array[min_i];
array[min_i] = temp;
}
Дата публикования: 2015-02-03; Прочитано: 253 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!