Почему мой код сортировки выбора не работает, когда есть повторяющиеся числа? - PullRequest
Новая
       36

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

0 голосов
/ 27 декабря 2018

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

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

function selectionSort(array) {
 
    for (let i = 0; i < array.length; i++) {

        let min = Math.min(...array.slice(i));
        let indexMin = array.indexOf(min)
        array.splice(indexMin, 1)
        array.splice(i,0,min);
    }
    return array;
}

console.log(selectionSort([3, 0, -5, -5]));

С тестовым массивом [3,0, -5, -5] в первой итерации цикла min равен -5, а indexMin равен 2После сращивания массива я получаю [3,0, -5].Когда я снова склеиваю его (чтобы вставить значение в начало массива), я получаю [-5,3,0, -5], как и ожидалось.Во второй итерации я ожидал бы, что min будет -5 в индексе 3 ... но когда я console.log min, он говорит, что это -5 в индексе 0. Я указал, что хочу найти min из(... array.slice (1)), так почему он устанавливает мин в -5 с индексом 0?

1 Ответ

0 голосов
/ 27 декабря 2018

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

indexOf() принимает необязательный второй параметр, чтобы указать, с чего начать поиск.Вы можете ввести i, чтобы начать с правильного места, пропуская уже отсортированные значения.

function selectionSort(array) {
  for (let i = 0; i < array.length; i++) {
    let min = Math.min(...array.slice(i));
    let indexMin = array.indexOf(min, i); // pass in i
    [array[indexMin], array[i]] = [array[i], array[indexMin]]
  }
  return array;
}

console.log(selectionSort([4, 5, 4, 3, 3, 3, 1, 3, 1]))
...