<< | к задаче | главная | печатать | обсудить(0 сообщений) >>
Задача: Сортировка Шелла, обший принцип
Исходник: Базовая сортировка Шелла с результирующей сортировкой вставками [C++, code #19, hits: 8242, рейтинг: 3/7,4.87(2852)] +
автор: this [добавлен: 30.01.2006] управление:
  1. template<class T>
  2. void swap(T* x, int i, int j) {
  3. T tmp;
  4. tmp = x[i]; x[i] = x[j]; x[j] = tmp;
  5. }
  6.  
  7. template<class T>
  8. void ShellSortBin(T* x) {
  9. int d = n;
  10. while (d > 1) {
  11. d /= 2;
  12. int i = 0, j = 0;
  13. /* делаем 1 "пузырьковый" проход
  14. для элементов каждой группы */
  15. while (j = i + d < n) {
  16. if (x[i] > x[j]) {
  17. swap(x, i, j);
  18. }
  19. i++;
  20. }
  21. }
  22. InsertSort(x);
  23. }
Приращение на каждом шаге - уменьшается вдвое.
В прелах каждой группы алгоритм выполняет 1 проход пузырьковой сортировки.
Результирующая сортировка - вставками.

Производительность: ~ O(n2)
Расход памяти: только на хранение счетчиков цикла и пары вспомогательных переменных

+добавить реализацию
 
каталог | задачи | паттерны | исходники | стат | форумы | карта сайта | контакты | ссылки 
© 2000-2018 CodeLAB Group
  Все права защищены
Страница сгенерирована за 0.005726 секунд
Количество запросов к БД: 9, gzip: 3.2kb/9.2kb(66%)