Задача: Сортировка вставкой
Исходник: Сортировка вставкой, версия #3, язык: C++ [code #17, hits: 14465]
автор: this [добавлен: 29.01.2006]
  1. template<class T>
  2. void InsertSort(T* x) {
  3. T t;
  4. int i, j;
  5. for (i = 1; i < n; i++) {
  6. t = x[i];
  7. for (j = i; j > 0 && x[j-1] > t; j--) {
  8. x[j] = x[j-1];
  9. }
  10. x[j] = t;
  11. }
  12. }
Производительность: ~ O(n2/2)
В наихудшем варианте(обратный порядок сортировки исходной последовательности), производительность: ~ O(n2)
Расход памяти: - (только лишь для элементов t, i, j в единичном экземпляре)
Тестировалось на: MS Visual Studio 2005, .NET Framework 2.0

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