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

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

script1adsense2code

script1adsense3code

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

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

Согласно Википедии «Сортировка слиянием (также обычно пишется слиянием) является алгоритмом сортировки на основе сравнения O (n log n). Большинство реализаций производят стабильную сортировку, что означает, что реализация сохраняет порядок ввода равных элементов в отсортированном выводе. "

Алгоритм:

Концептуально сортировка слиянием работает следующим образом:

Разделите несортированный список на n подсписков, каждый из которых содержит 1 элемент (список из 1 элемента считается отсортированным).
Повторно объединяйте подсписки для создания новых отсортированных подсписков, пока не останется только 1 подсписок. Это будет отсортированный список.

Пример сортировки слиянием :

Сортировка слиянием: графическое представление

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

HTML-код:

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

Код JavaScript:

  function merge_sort(left_part,right_part) 
{
	var i = 0;
	var j = 0;
	var results = [];
	while (i < left_part.length || j < right_part.length) {
		if (i === left_part.length) {
			// j is the only index left_part
			results.push(right_part[j]);
			j++;
		} 
      else if (j === right_part.length || left_part[i] <= right_part[j]) {
			results.push(left_part[i]);
			i++;
		} else {
			results.push(right_part[j]);
			j++;
		}
	}
	return results;
}
console.log(merge_sort([1,3,4], [3,7,9]));

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

 [1,3,3,4,7,9]

Блок - схема:

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

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

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

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