Java - двоичная вставка сортировка, устранение неполадок

У меня есть задача, когда мне нужно отсортировать массив, используя двоичную сортировку вставки. Это решение, которое я придумал, но это слишком медленно:Java - двоичная вставка сортировка, устранение неполадок

public static void binaryInsertionSort(int[] a) { 
    int ins, i, j; 
    int tmp; 
    for (i = 1; i < a.length; i++) { 
     ins = BinarySearch (a, 0, i, a[i]); 
      if(ins < i) { 
       tmp = a[i]; 
       for (j = i - 1; j >= ins; j--) 
        a[j+1] = a[j]; 
       a[ins] = tmp; 
      } 
    } 
} 

private static int BinarySearch(int[] a, int low, int high, int key) { 

    int mid; 
    if (low == high) 
     return low; 
    mid = low + ((high - low)/2); 
    if (key > a[mid]) 
     return BinarySearch (a, mid + 1, high, key); 
    else if (key < a[mid]) 
     return BinarySearch (a, low, mid, key); 
    return mid; 

}

я рекомендовал использовать метод System.arraycopy, который я пытался, но я не понимаю, почему он не работает:

public static void binaryInsertionSort(int[] a) { 
    int ins, i; 
    int tmp = a[i]; 
    for (i = 1; i < a.length; i++) { 
     ins = binarySearch (a, 0, i, a[i]); 
      if(ins < i){ 
       System.arraycopy(a, ins, a, ins + 1, i - ins); 
       a[ins] = tmp; 
      } 
    } 
} 

private static int binarySearch(int[] a, int low, int high, int key) { 
    int mid; 
    if (low == high) 
     return low; 
    mid = low + ((high - low)/2); 
    if (key > a[mid]) 
     return binarySearch (a, mid + 1, high, key); 
    else if (key < a[mid]) 
     return binarySearch (a, low, mid, key); 
    return mid; 
}

Любая помощь полезна.

источник

2017-02-19 elMatador

Опишите, что происходит, когда вы ** ** запустить ваш код Повесьте ** полный. ** [mcve], который показывает нам, с какими данными вы работаете, и как выглядят ожидаемые/фактические результаты. – GhostCat

Оригинальный код, который вы написали в первый раз, выглядит хорошо для меня. Я не уверен, что вы имели ввиду слишком медленно. Сортировка двоичной вставки делает окончательную сложность O (n^2) в конце. Возникает ли ваш вопрос о том, чтобы сделать это быстро или сделать вас r вторая реализация? Даже если вы выполняете вторую работу по внедрению с использованием system.arraycopy, я вряд ли верю, что ваша программа будет работать очень быстро. Для быстрого алгоритма сортировки используйте один из алгоритмов O (nlogn). –

Мой вопрос был о том, чтобы сделать второй код работы. Да, хотя исходный код работает, метод System.arraycopy примерно в 4 раза быстрее исходного)) – elMatador

Хорошо, тем временем ответ был проще, чем я думал. Я инициализировал локальную переменную в неправильном месте. Вместо того, чтобы:

Правильный путь заключается в следующем:

public static void binaryInsertionSort(int[] a) { 
    int ins, i; 
     for (i = 1; i < a.length; i++) { 
      **int tmp = a[i];** 
      ins = binarySearch (a, 0, i, a[i]); 
       if(ins < i){ 
        System.arraycopy(a, ins, a, ins + 1, i - ins); 
        a[ins] = tmp; 
       } 
    } 
}

И это работает (:

источник

2017-02-19 11:46:21 elMatador

Java - двоичная вставка сортировка, устранение неполадок

ответ

Смежные вопросы