Минимальное количество перестановок для сортировки массива без дубликатов

Question

Я хочу найти минимальное количество перестановок для сортировки массива. (Массив гарантированно не содержит дубликатов.) Я нашел сообщение, в котором это делается в основном с использованием графика: Вычислить минимальное количество перестановок, чтобы упорядочить последовательность

Но мне было интересно, Я также могу сделать это, запустив sort selection и посчитав количество перестановок. (См. Код ниже.) Является ли этот подход правильным? Или есть случай, когда это даст неправильный результат?

int minSwaps(int[] A, int n) {
    int numSwaps = 0;
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < n; j++) {
            if (A[j] < A[minIndex])
                minIndex = j;
        }
        if (minIndex != i) {
            numSwaps++;
            int temp = A[minIndex];
            A[minIndex] = A[i];
            A[i] = temp;
        }
    }
    return numSwaps;
}

Answer 1

Ваш подход правильный. Как объясняет Википедия :

Одна вещь, которая отличает сортировку выбора от других алгоритмов сортировки, состоит в том, что она делает минимально возможное количество обменов, n - 1 в наихудший случай.

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

Фактически, ваш подход является лишь частным случаем подхода в вопрос, на который вы ссылаетесь . Этот вопрос на самом деле не использует график; ответ просто использует теорию графов, чтобы попытаться доказать, что подход работает. Таким образом, приведенные там аргументы также применимы к вашему подходу.

Тем не менее, ваш точный подход требует O ( n ² ) сравнений, тогда как другие варианты этого подхода можно сделать за O ( n log n ). Только вы можете решить, стоит ли простота вашего варианта большей временной сложности.