Блог

Я пытаюсь реализовать сортировку по вставке.

 public int[] insertionSort(int[] a) {

    for(int i=0; i<a.length;i  ) {
        int j=i 1;

        while(a[j] < a[i] amp;amp; j < a.length) {
            swap(a[j],a[i]);
            j--;
            i--;
        }
    }
    return a;
}

public void swap(int a, int b) {
    int temp;
    temp = a;
    a = b;
    b = temp;
}
  

Не является ли это — технически — тем же самым (с точки зрения выходного результата), как если бы я должен был сказать j = i-1 и заменить условие в цикле while из j < a.length на j > = 0?

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

Вероятно, вам лучше просто не использовать отдельный метод для подкачки, подобный этому (также пришлось увеличивать вместо уменьшения значения i и j ):

 public int[] insertionSort(int[] a) {
    int temp;

    for(int i=0; i<a.length;i  ) {
        int j=i;

        while(j > 0 amp;amp; a[j-1] > a[j]) {
            temp = a[j];
            a[j] = a[j-1];
            a[j-1] = temp;
            j--;
        }
    }
    return a;
}
  

Редактировать: пришлось обновить снова — условия в цикле while были в неправильном порядке, поэтому он будет искать следующий индекс массива, прежде чем проверять, достиг ли он конца массива.

Правка 2: как упоминалось в комментариях, я покажу, как написать swap метод, который действительно работает — вместо передачи значений вам придется передать весь массив и вернуть его после. Я бы все же, вероятно, рекомендовал сделать это описанным выше способом, но только в образовательных целях:

 public int[] insertionSort(int[] a) {

    for(int i=0; i<a.length;i  ) {
        int j=i;

        while(j > 0 amp;amp; a[j-1] > a[j]) {
            a = swap(a, j-1, j);
            j--;
        }
    }
    return a;
}


public int[] swap(int[] a, int index1, int index2) {
    int temp = a[index1];
    a[index1] = a[index2];
    a[index2] = temp;
    return a;
}
  

Правка 3: делал что-то глупое и не совсем задал сортировку вставки. Теперь все отсортировано (извините за каламбур).