1. Пузырьком О(n^2). Два вложенных цикла, во внутреннем сравниваются пары соседних элементов, начиная с нижних. Таким образом за один проход внутреннего цикла получаем один отсортированный элемент на своем месте.
2. Выбором О(n^2). В исходном массиве ищем наименьший элемент и меняем его с первым. Далее повторяем эти шаги с подмассивом исходного, куда не входит уже отсортированный первый элемент.
3. Вставками O(n^2). Все элементы условно разделяются на готовую последовательность a1 ... ai-1 и входную ai ... an. Hа каждом шаге, начиная с i = 2 и увеличивая i на 1, берем i-й элемент входной последовательности и вставляем его на нужное место в готовую.
4. Шелла O(n log^2 n). Некая модификация сортировки вставками: здесь сначала сортируется не весь массив, а группы элементов, отстоящих друг от груга на некоторое расстояние d. Это расстояние постепенно уменьшаем и доходим до того, что сортируем опять же весь массив. Например, для массива 16 элементов разумно выбрать начальное d = 8, а потом уменьшать его в два раза. Сначала будет сортироваться 8 групп по 2 элемента, потом 4 группы по 4 и так далее.
5. Пирамидальная O(n log n). Из исходного массива сначала строится пирамида. Она является так же сбалансированным деревом и обладает свойством, что каждый элемент меньше либо равен родителю. Это дерево легко вписывается в массив, если вписывать элементы по порядку - слева направо и сверху вниз. Далее первый элемент (максимальный) меняем с последним (минимальным) и забываем его, т.е. не учитываем в пирамиде. Перестраиваем пирамиду согласно свойству, т.е. просеиваем первый элемент вниз. Повторяем шаги пока пирамида не иссякнет.
6. Быстрая O(n log n). Из массива выбирается некоторый опорный элемент a[i]. Запускается процедура разделения массива, которая перемещает все ключи, меньшие, либо равные a[i], влево от него, а все ключи, большие, либо равные a[i] - вправо.
Теперь массив состоит из двух подмножеств, причем левое меньше, либо равно правого. Для обоих подмассивов: если в подмассиве более двух элементов, рекурсивно запускаем для него ту же процедуру.
7. Поразрядная O(nk). Итак, в этом алгоритме у нас есть некие вспомогательные списки, называемые карманами. Их количество равно разрядности данных, например, для человеческих чисел = 10. Вначале они пустые и в них добавляются элементы нашего массива согласно значению первого разряда. Далее полученные списки склеиваются, и операция повторяется над полученным массивом, но только со 2 разрядом. И далее вплоть до максимального разряда самого длинного числа.
2. Выбором О(n^2). В исходном массиве ищем наименьший элемент и меняем его с первым. Далее повторяем эти шаги с подмассивом исходного, куда не входит уже отсортированный первый элемент.
3. Вставками O(n^2). Все элементы условно разделяются на готовую последовательность a1 ... ai-1 и входную ai ... an. Hа каждом шаге, начиная с i = 2 и увеличивая i на 1, берем i-й элемент входной последовательности и вставляем его на нужное место в готовую.
4. Шелла O(n log^2 n). Некая модификация сортировки вставками: здесь сначала сортируется не весь массив, а группы элементов, отстоящих друг от груга на некоторое расстояние d. Это расстояние постепенно уменьшаем и доходим до того, что сортируем опять же весь массив. Например, для массива 16 элементов разумно выбрать начальное d = 8, а потом уменьшать его в два раза. Сначала будет сортироваться 8 групп по 2 элемента, потом 4 группы по 4 и так далее.
5. Пирамидальная O(n log n). Из исходного массива сначала строится пирамида. Она является так же сбалансированным деревом и обладает свойством, что каждый элемент меньше либо равен родителю. Это дерево легко вписывается в массив, если вписывать элементы по порядку - слева направо и сверху вниз. Далее первый элемент (максимальный) меняем с последним (минимальным) и забываем его, т.е. не учитываем в пирамиде. Перестраиваем пирамиду согласно свойству, т.е. просеиваем первый элемент вниз. Повторяем шаги пока пирамида не иссякнет.
6. Быстрая O(n log n). Из массива выбирается некоторый опорный элемент a[i]. Запускается процедура разделения массива, которая перемещает все ключи, меньшие, либо равные a[i], влево от него, а все ключи, большие, либо равные a[i] - вправо.
Теперь массив состоит из двух подмножеств, причем левое меньше, либо равно правого. Для обоих подмассивов: если в подмассиве более двух элементов, рекурсивно запускаем для него ту же процедуру.
7. Поразрядная O(nk). Итак, в этом алгоритме у нас есть некие вспомогательные списки, называемые карманами. Их количество равно разрядности данных, например, для человеческих чисел = 10. Вначале они пустые и в них добавляются элементы нашего массива согласно значению первого разряда. Далее полученные списки склеиваются, и операция повторяется над полученным массивом, но только со 2 разрядом. И далее вплоть до максимального разряда самого длинного числа.