Задача: Сортировка Шелла, обший принцип
Исходник: Базовая сортировка Шелла, результирующая сортировка - вставками, язык: C++ [code #19, hits: 12296]
автор: 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)
Расход памяти: только на хранение счетчиков цикла и пары вспомогательных переменных
Тестировалось на: MS Visual Studio 2005, .NET Framework 2.0

+добавить реализацию