Двоичная сортировка вставками аналогично обычной сортировке вставками

Итак, я пытаюсь понять, как правильно использовать двоичную сортировку вставками без необходимости метода подкачки или чего-то подобного. Мой друг дал мне грубую интерпретацию необходимого кода, но я не могу заставить его работать так, как я хочу.

private static int binaryInsertionSort(int[] b)
{
    int left, right, middle, i, m;
    int compareCount = 0;
    for (int j = 1; j < b.length; j++)
    {
        left = b[j - 1];
        right = b[j + 1];
        if (b[j] < b[left])
        {
            i = left;
        }
        else
        {
            i = left + 1;
        }
        m = b[j];
        for(int k = 0; k < (j - i - 1); k++)
        {
            b[j - k] = b[j - k - 1];
            compareCount++;
        }
        b[i] = m;
    }
    return compareCount;
}

Int compareCount предназначен просто для того, чтобы увидеть, сколько сравнений выполняется в ходе выполнения метода. Теперь то, что я пытаюсь сделать, это упорядочить массив целых чисел обычным образом, в частности, как b[0] = 1, b[1] = 2,...... b[63] = 64. В моей основной метод я создаю массив и присваиваю значения в обратном порядке: b[0] = 64, b[1] = 63 и т. д. Как я могу получить этот код, чтобы переставить их в обычном порядке, который я ищу? Я смог сделать это очень просто с помощью обычной сортировки вставками, но это немного сложнее... для меня.


java sorting insertion-sort
person TechnicallySarcastic    schedule 01.03.2016    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Не берите в голову. После долгих возни и выяснения конкретных деталей с другим другом нам удалось выяснить, как именно это сделать.

public static int binaryInsertionSort(int[] b)
{
    int lo, mid, hi, temp;
    int compareCount = 0;
    for (int i = 1; i < b.length; i++) 
    {
        lo = 0; 
        hi = i;
        mid = i / 2;
        do 
        {
            if (b[i] > b[mid]) 
            {
                lo = mid + 1;
                compareCount++;
            } 
            else if (b[i] < b[mid]) 
            {
                hi = mid;
                compareCount++;
            } 
            else
            {
                compareCount++;
                break;
            }
            mid = lo + ((hi - lo) / 2);
        } while (lo < hi);
        if (mid < i) 
        {
            temp = b[i];
            for (int j = i - 1; j >= mid; j--)
            {
                b[j + 1] = b[j];
                compareCount++;
            }
            b[mid] = temp;
        }
    }
    return compareCount;
}

Действительно очень сложно, но с усилиями приходит награда. Несмотря на то, что никто не ответил, я все равно благодарю тех, кто просматривал мой вопрос.

person TechnicallySarcastic    schedule 01.03.2016