Сортировка при вставке с помощью двух массивов

#java #insertion-sort

#java #вставка-сортировка

Вопрос:

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

Я попытался реализовать алгоритм сортировки по вставке с некоторыми изменениями, которые, как я думал, помогут выполнить задачу

 public static void insertionSort(int[] a) {
    int[] temp = new int[a.length];
    for(int indice = 0; indice < a.length; indice  ) {
        int key = a[indice];
        int j = indice - 1;

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

Я пытался использовать это с массивом с такими числами: 5, 1, 4, 14, 21, 144, 3
Но выводится 0 0 0 0 0 0 0 0

1. Для чего вы используете temp ?

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

3. Нет, вы этого не делаете. Вот почему я задал вопрос, чтобы вы проверили свой код.

4. Если вы хотите выполнить сортировку по вставке, реализуйте сортировку по вставке. Смотрите алгоритм в Википедии, en.wikipedia.org/wiki/Insertion_sort или где-либо еще. int[] temp просто не существует.

5. Или, если вы хотите вернуть упорядоченную копию входного массива: 1) убедитесь, что вы используете temp везде, за исключением случаев, когда вы делаете копию в начале 2) также верните ее (возврат void не выполнит работу).

Ответ №1:

Проблема в том, что вы создаете временный массив, но вы не присваиваете никакого значения какой-либо позиции. Итак, когда вы выполняете «a [j 1] = temp [j 1];», в этом массиве ничего нет, поэтому a [j 1] присваивается 0.

Если я правильно понял, temp должен быть копией a, чтобы вы могли сделать что-то вроде этого:

 int[] temp = new int[a.length]; 

for (int i = 0; i < temp.length; i  ) 
{ 
    temp[i] = a[i];
}

1. Сразу после инициализации temp. Предполагая, что вы хотите, чтобы temp был копией

2. Теперь с вашим фрагментом кода все работает идеально. Большое вам спасибо за помощь!

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

Ответ №2:

Вы не используете временный массив. Для temp не выполнено присвоение. У него пустой массив.

Попробуйте ниже, и вы должны отсортировать массив так, как хотите

  public static void main(String[] args) {

        int[] a = { 5, 1, 4, 14, 21, 144, 3 };

        int[] arr2 = insertionSort(a);
        for(int i:arr2){
            System.out.print(i);
            System.out.print(", ");
        }
    }

 public static int[] insertionSort(int[] input){    
         int temp;
         for (int i = 1; i < input.length; i  ) {
             for(int j = i ; j > 0 ; j--){
                 if(input[j] < input[j-1]){
                     temp = input[j];
                     input[j] = input[j-1];
                        input[j-1] = temp;
                    }
                }
            }
            return input;
        }