Кухня(); Второй сезон - 75/79

75. Сортировка вставками. Дана последовательность чисел а1, а2, ..., аn. Требуется переставить числа в порядке возрастания. Делается это следующим образом. Пусть а1, а2, ..., аi – упорядоченная последовательность, т.е. a1 ≤ a2 ≤ ... ≤ аi. Берется следующее число ai+1 и вставляется в последовательность так, чтобы новая последовательность была также возрастающей. Процесс производится до тех пор, пока все элементы от i+1 до n не будут перебраны. Кухня ПРАВИЛА

Комментарии (3)

ЧТОБЫ ПОСМОТРЕТЬ ВСЕ КОММЕНТАРИИ ИЛИ ОСТАВИТЬ КОММЕНТАРИЙ,
ПЕРЕЙДИТЕ В ПОЛНУЮ ВЕРСИЮ

terranum Уровень 28

29 января 2015

Мой вариант без магии binarySearch. Кстати круто, на больших массивах разница ощутима!

public static void insertionSort(@NotNull int[] arr) { int tmp; int j; for (int i = 1; i < arr.length; i++) // бежим пока не нарушится последовательнось if (arr[i - 1] > arr[i]) { j = i - 1; tmp = arr[i]; // запоминаем наш элемент while (j > 0 && arr[j] > arr[i]) // ищем индекс элемета не больше нашего числа j--; System.arraycopy(arr, j, arr, j + 1, i - j); // сдвигаем найденый блок массива вправо на одну ячейку if (arr[j] <= tmp) // вставляем на свое законное место arr[j + 1] = tmp; else // костыль на тот случай когда вставляем в начало массива arr[j] = tmp; } }

iZulrad Уровень 34

29 января 2015

public static void insertionSort(@NotNull int arr[]) {
        int current, dex, r;
        for (int i = 1; i < arr.length; i++) {
            current = arr[i];
            if ((dex = Arrays.binarySearch(arr, 0, i, current)) < 0) dex = -(dex + 1);

            if (dex != i) {
                if (i - dex > 9_999) {
                    System.arraycopy(arr, dex, arr, dex + 1, i - dex);
                } else {
                    r = i;
                    while (r != dex) arr[r] = arr[--r];
                }
                arr[dex] = current;
            }
        }
    }