Какова роль временного целого числа в коде пузырьковой сортировки

Question

int[] array = {4, 5, 7, 6, 9, 10,67,6,45};
for (int i = 0; i < array.length; i++) {
    for (int j = i+1; j < array.length; j++) {
        if (array[i] > array[j]) {
            int temp = array[i];
            array[i] = array[j];
            array[j] = temp;
        }
    }

Просто интересно, какова роль array[j] = temp; Это алгоритм сортировки по пузырькам, новый для обмена в стеке, поэтому форматирование может быть не очень хорошим

Answer 1

Есть способ сделать это без дополнительной переменной, используя XOR:

array[i] ^= array[j];
array[j] ^= array[i];
array[i] ^= array[j];

Идеальная демонстрация

Однако:

• Это довольно непрозрачно для тех, кто не видел этот трюк раньше или кто не понимает, как работает xor-ing
• Это работает только для типов, которые вы можете XOR. Например, вы не можете поменять объекты подобным образом.

Использование временной переменной, как объяснено в других ответах, является хорошо известным простым способом express подкачки.

---

Еще один способ думать об этом: две машины, пытающиеся обойти друг друга на узкой дороге:

         Parking space
             |
Car1 > -----/-\----- < Car2

Чтобы обойти друг друга, Car1 может въехать на парковочное место:

           Car1
             |
       -----/-\----- < Car2

Car2 может проехать:

           Car1
             |
Car2 < -----/-\-----

Затем Car1 может проехать:

             |
Car2 < -----/-\----- > Car1

Временная переменная - это "парковочное место" ».

Answer 2

Представьте, что у вас есть красный шар в левой руке, а синий шар справа.

Теперь переключайте шары ... не бросая их в воздух.

Как? Позволь мне помочь!

Answer 3

В дополнение к ответу @Andy Turner вы можете избежать переменной temp и даже не использовать xor:

array[i] = array[i] + array[j];
array[j] = array[i] - arra[j];
array[i] = array[i] - array[j];

Но, как вы можете видеть (и как объяснили другие ответы), использование temp более понятно, легко читаемый и понятный. Вот почему большинство учебных пособий используют переменную temp, чтобы их было легко понять и изучить алгоритм.

Answer 4

Роль temp состоит в том, чтобы временно удерживать значение.

int temp = array[i];
array[i] = array[j];
array[j] = temp;

Этот тип примитивного значения может содержать только одно значение за раз.

Представьте себя и друга каждый держит очень тяжелый предмет, и вы можете держать только один из них. Если вы хотите обменяться объектами с другом, вам придется сначала поместить объект куда-нибудь, прежде чем получить объект от друга. После того, как он дал его вам, друг может взять другой предмет.

Answer 5

Переменная temp используется для переключения между array[i] и array[j] - вы сохраняете array[i] во временном местоположении, перезаписываете его с помощью array[j], а затем назначаете значение, которое вы откладываете (в temp) до array[j].