вставка сортировка ... твики для улучшения?

Question

я знаю, что сортировка вставок не так уж хороша ... но даже все же ... какие еще два простых улучшения можно внести в сортировку ниже?

public static void insertion_sort_with_moves(int[] arr){
    for (int i = 1; i <= arr.length; i++){
        int v = arr[i-1];
        int j = i-1;
        for (/*declared j outside loop*/; j > 0; j--) {
            //compswap(a[j-1], a[j]);
            if (v < arr[j-1]) arr[j] = arr[j-1];
            else break;
        }
        arr[j] = v;
    }
}

Answer 1

Одна вещь, которая приходит на ум, - это то, что вы можете использовать бинарный поиск по отсортированной части массива, чтобы найти, где он принадлежит, и использовать System.arraycopy, чтобы переместить подрешетку на единицу более эффективно, чем итерацию. Вы по-прежнему O (n ^ 2), но для больших массивов это будет небольшое улучшение.

Другой способ - объявить любые переменные, которые не изменятся как окончательные, чтобы обеспечить оптимизацию компилятора (как я отметил в своем комментарии.)

Answer 2

Несколько микрооптимизаций:

1,2,3)

    int len = arr.length; 
...

    for (int i = 0; i < len; ++i){
            int v = arr[i];
            int j = i;

Два раза спасает вас от вычислений i-1, и ++ быстрее i ++. Не уверен насчет длины (может сохранить добавление смещения при доступе к члену класса).

4,5)

for (/*declared j outside loop*/; j != 0; --j) {

j! = 0 должно быть быстрее, чем j> 0 (на самом деле не ожидайте многого), а --j быстрее, чем j -.

Ну, большинство из них могут зависеть от платформы и вообще ничего не менять.

Answer 3

Обновлено на основе комментариев:

Некоторые улучшения для удобства чтения:

1. Не используйте подчеркивания в именах методов. Вместо этого используйте верблюжий футляр.
2. Рассмотрим фигурные скобки вокруг операторов if / else, чтобы их было легче читать или, по крайней мере, вводить больше новых строк.
3. Удалить код, который закомментирован, если он не нужен.
4. Подумайте об удалении комментариев, объясняющих «что» вместо «почему».
5. Старайтесь избегать односимвольных переменных, особенно если у вас несколько в одной области видимости.
6. Возможно, вы сможете использовать a для каждого цикла вместо того, чтобы объявлять и обращаться к переменной v. (По-прежнему нужен текущий индекс, но другие изменения могут это позволить)