воскресенье, 5 сентября 2010 г.

Сортировки


Квадратичные сортировки O(N*N):


Пузырьковая                (Bubble sort)     +
Шейкерная                  (Cocktail sort)   +
Вставками                  (Insert sort)     +
Гномья                     (Gnome sort)      +
Выбором                    (Selection sort)  +


Квазилинейные O(N*log(N)):

Слиянием                   (Merge sort)      +
С помощью двоичного дерева (Tree sort)       -
Сортировка Шелла           (Shell sort)      -
Пирамидальная              (Heap sort)       -
Плавная                    (Smooth sort)     -
Быстрая                    (Quick sort)      -
STL C++                    (Intro sort)      -
Python сортировка          (Tim sort)        +


Линейные O(N):

Подсчетом                  (Counting sort)   +
Карманная                  (Bucket sort)     +
Поразрядная                (Radix sort)      -




* Плюсом отмечены стабильные сортировки

4 комментария:

  1. С помощью двоичного дерева Tree_sort.
    Эта на базе сбалансированных деревьев?

    ОтветитьУдалить
  2. Сортировка Шелла Shell_sort
    Это не N*Log(N)

    ОтветитьУдалить
  3. 1) Digit_sort - Radix? Да
    2) Tree_sort.Эта на базе сбалансированных деревьев? Думаю да
    3) Шелл O(n*log(n)*log(n))

    ОтветитьУдалить