В сортировке выбора, если у нас есть два повторяющихся элемента, каково поведение алгоритма?

Question

Если мы удаляем часть, начинающуюся с if (indexMax != i), из кода ниже (последняя часть), Алгоритм разбивается, почему?

public static void selectionSort(int[] array) {
    for (int i = 0; i < array.length; i++) {
        int indexMax = i;

        for (int j = i + 1; j < array.length; j++) {
            if (array[indexMax] < array[j]) {
                indexMax = j;
            }
        }

        if (indexMax != i) {
            int temp = array[i];
            array[i] = array[indexMax];
            array[indexMax] = temp;
        }
    }
}

Answer 1

Ваш код будет делать следующее:

arr[] = 1, 5, 2, 4, 3

// find the max from arr[0..4]
// substitute it with the index 0, if it is not of that index already
arr[] = 5, 1, 2, 4, 3

// find the max from arr[1..4]
// substitute it with the index 1, if it is not of that index already
arr[] = 5, 4, 2, 1, 3 

// find the max from arr[2..4]
// substitute it with the index 2, if it is not of that index already 
arr[] = 5, 4, 3, 1, 2

// find the max from arr[3..4]
// substitute it with the index 3, if it is not of that index already 
arr[] = 5, 4, 3, 2, 1

заменяет его индексом i, если он уже не является этим индексом , это оператор if

---

Для более длинного массива с дубликатами отметьте это Kotlin Код игровой площадки , который я создал для вас. Вы можете изменить массив при помощи sh и отследить переключение значений.

Answer 2

На рисунке вы можете увидеть, как дубликаты перемещают свое положение. Это создает нестабильность.

Для трех дубликатов:

Для двух дубликатов:

Answer 3

Из кода, который вы отправили с моими комментариями:

    int indexMax = i;  // initial value of indexMax

    for (int j = i + 1; j < array.length; j++) {
        // please note that j starts with (i+1)
        if (array[indexMax] < array[j]) {
            indexMax = j;  // index of Max candidate  
        }
    }

    if (indexMax != i) {   // means that the above loop reassigned indexMax
        int temp = array[i];  // so we are swapping
        array[i] = array[indexMax];
        array[indexMax] = temp;
    }

Итак, if (indexMax != i) означает " Мы нашли лучшего Макса? "