Выбор Сортировка Поведение с дубликатами

Question

Как сортировка сортировки обрабатывает повторяющиеся значения в массивах? Мне сложно найти ответ в Интернете.

Если у меня есть массив, такой как [8, 4, 7, 3, 9, 3], то какой индекс будет выбирать сортировку, чтобы поменять местами на первом проходе массива?

Третий индекс или 5-й индекс?

Answer 1

Хотя ваш конкретный вопрос об обмене в 3 легко ответить, более общая его версия непростая, потому что выбор сортировки не стабильный.

Классический реализация будет выбрать 3 на третьем индексе, так как условие для выбора следующего элемента, чтобы своп

if (a[i] < a[iMin]) 

После первого 3 обменена в положение 0, второй 3 по индексу пять не будет выбирается.

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

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

К примеру, в этом начальном расположении

[3, 3, 1] 

3 индексом ноль будет выбран в прошлом, так как первая итерация будет двигаться весь путь до конца массива.

Answer 2

Это зависит от реализации. Обычно, однако, цикл начнет сканирование слева направо и получит первый 3.

Но, как я говорю, это не стандарт.

Это возможная реализация в соответствии с Wikipedia:

procedure SelectionSort(a: list to sorts); 
    for i = 1 to n - 1 
    posmin ← i 
    for j = (i + 1) to n 
     if a[j] < a[posmin] 
     posmin ← j 
    tmp ← a[i] 
    a[i] ← a[posmin] 
    a[posmin] ← tmp