Алгоритм поиска и сортировки JavaScript: сортировка вставками

Последнее обновление 9 февраля 2019 08:36:49 (UTC / GMT +8 часов)

script1adsense2code

script1adsense3code

Алгоритм поиска и сортировки JavaScript: упражнение-4 с решением

Напишите программу на JavaScript для сортировки списка элементов с использованием сортировки вставками.

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

Иллюстрированная презентация: вставка сортировки

Графический пример вставки сортировки:

Кредиты на анимацию: Swfung8

Пример решения: -

HTML-код:

<!DOCTYPE html>
  <html>
  <head>
  <meta charset="utf-8">
  <title>JavaScript program of Insertion sort</title>
  </head>
  <body></body>
</html>

Код JavaScript:

function insertion_Sort(arr)
{
  for (var i = 1; i < arr.length; i++) 
  {
    if (arr[i] < arr[0]) 
    {
      //move current element to the first position
      arr.unshift(arr.splice(i,1)[0]);
    } 
    else if (arr[i] > arr[i-1]) 
    {
      //leave current element where it is
      continue;
    } 
    else {
      //find where element should go
      for (var j = 1; j < i; j++) {
        if (arr[i] > arr[j-1] && arr[i] < arr[j]) 
        {
          //move element
          arr.splice(j,0,arr.splice(i,1)[0]);
        }
      }
    }
  }
  return arr;
}
console.log(insertion_Sort([3, 0, 2, 5, -1, 4, 1]));

Пример вывода:

 -1,0,1,2,3,4,5]

Блок - схема:

Демонстрация в реальном времени:

См. Поиск и сортировка-алгоритм-упражнение-4 ручки от w3resource ( @ w3resource ) на CodePen .

Улучшите этот пример решения и опубликуйте свой код через Disqus

Предыдущая: Напишите программу на JavaScript для сортировки списка элементов, используя сортировку кучи.
Далее: Напишите программу на JavaScript для сортировки списка элементов с использованием алгоритма сортировки Selection.