algorithm
Вставка Сортировка
Поиск…
замечания
Когда мы анализируем производительность алгоритма сортировки, мы в основном интересуемся количеством сравнения и обмена.
Средняя биржа
Пусть E n - общее среднее число обменов для сортировки массива из элемента N. E 1 = 0 (нам не нужен обмен для массива с одним элементом). Среднее количество обменов для сортировки массива элементов N представляет собой сумму среднего числа номеров для сортировки массива элементов N-1 со средним обменом для вставки последнего элемента в массив элементов N-1.
Упрощение суммирования (арифметическая серия)
Расширяет термин
Упростите суммирование снова (арифметическая серия)
Среднее сравнение
Пусть C n - общее среднее число сравнения для сортировки массива из элемента N. C 1 = 0 (нам не нужно сравнивать ни один массив элементов). Среднее количество сравнений для сортировки массива элементов N представляет собой сумму среднего числа сравнения для сортировки массива элементов N-1 со средним сравнением для вставки последнего элемента в массив элементов N-1. Если последний элемент является самым большим элементом, нам нужно только одно сравнение, если последний элемент является вторым наименьшим элементом, нам нужно сравнение N-1. Однако, если последний элемент является наименьшим элементом, нам не нужно сравнивать N. Нам все еще нужно только сравнение N-1. Вот почему мы удаляем 1 / N в следующем уравнении.
Упрощение суммирования (арифметическая серия)
Развернуть термин
Упростите суммирование снова (арифметические ряды и гармоническое число)
Основы алгоритма
Сортировка вставки - очень простой, стабильный алгоритм сортировки на месте. Он хорошо работает на небольших последовательностях, но он намного менее эффективен для больших списков. На каждом шаге алгоритмы рассматривают i-й элемент данной последовательности, перемещая ее влево, пока она не окажется в правильном положении.
Графическая иллюстрация
ПСЕВДОКОД
for j = 1 to length(A)
n = A[j]
i = j - 1
while j > 0 and A[i] > n
A[i + 1] = A[i]
i = i - 1
A[i + 1] = n
пример
Рассмотрим следующий список целых чисел:
[5, 2, 4, 6, 1, 3]
Алгоритм выполнит следующие шаги:
-
[5, 2, 4, 6, 1, 3] -
[2, 5, 4, 6, 1, 3] -
[2, 4, 5, 6, 1, 3] -
[2, 4, 5, 6, 1, 3] -
[1, 2, 4, 5, 6, 3] -
[1, 2, 3, 4, 5, 6]
Реализация C #
public class InsertionSort
{
public static void SortInsertion(int[] input, int n)
{
for (int i = 0; i < n; i++)
{
int x = input[i];
int j = i - 1;
while (j >= 0 && input[j] > x)
{
input[j + 1] = input[j];
j = j - 1;
}
input[j + 1] = x;
}
}
public static int[] Main(int[] input)
{
SortInsertion(input, input.Length);
return input;
}
}
Вспомогательное пространство: O(1)
Сложность времени: O(n)
Реализация Haskell
insertSort :: Ord a => [a] -> [a]
insertSort [] = []
insertSort (x:xs) = insert x (insertSort xs)
insert :: Ord a => a-> [a] -> [a]
insert n [] = [n]
insert n (x:xs) | n <= x = (n:x:xs)
| otherwise = x:insert n xs
