algorithm => Вставка Сортировка

замечания

Когда мы анализируем производительность алгоритма сортировки, мы в основном интересуемся количеством сравнения и обмена.

Средняя биржа

Пусть E _n - общее среднее число обменов для сортировки массива из элемента N. E ₁ = 0 (нам не нужен обмен для массива с одним элементом). Среднее количество обменов для сортировки массива элементов N представляет собой сумму среднего числа номеров для сортировки массива элементов N-1 со средним обменом для вставки последнего элемента в массив элементов N-1.

Упрощение суммирования (арифметическая серия)

Расширяет термин

Упростите суммирование снова (арифметическая серия)

Среднее сравнение

Пусть C _n - общее среднее число сравнения для сортировки массива из элемента N. C ₁ = 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

Modified text is an extract of the original Stack Overflow Documentation

Лицензировано согласно CC BY-SA 3.0

Не связан с Stack Overflow

algorithm
Вставка Сортировка

Поиск…