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

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

script1adsense2code

script1adsense3code

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

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

Согласно Википедии «Сортировка оболочки или метод Shell является сортировкой сравнения на месте. Это можно рассматривать как обобщение сортировки по обмену (пузырьковая сортировка) или сортировку по вставке (вставка сортировки). Метод начинается с сортировки пар элементы находятся далеко друг от друга, а затем постепенно сокращается разрыв между сравниваемыми элементами. Начиная с далеко расположенных элементов, можно перемещать некоторые неуместные элементы в положение быстрее, чем простой обмен ближайшими соседями ».

Пример запуска Shellsort с пробелами 5, 3 и 1 показан ниже.

Первый проход, 5-сортировка, выполняет сортировку вставки на отдельных подмассивах (a1, a6, a11), (a2, a7, a12), (a3, a8), (a4, a9), (a5, a10). Например, он изменяет подмассив (a1, a6, a11) с (62, 17, 25) на (17, 25, 62). Следующий проход, сортировка 3, выполняет сортировку вставки для подмассивов (a1, a4, a7, a10), (a2, a5, a8, a11), (a3, a6, a9, a12). Последний проход, 1-сортировка, является обычной сортировкой вставки всего массива (a1, ..., a12). Как показано в примере, подмассивы, на которых работает Shellsort, изначально короткие; позже они длиннее но почти заказаны. В обоих случаях сортировка вставок работает эффективно. Сортировка оболочки нестабильна: она может изменить относительный порядок элементов с равными значениями. Это адаптивный алгоритм сортировки, который выполняется быстрее при частичной сортировке входных данных.

Shell Sort

Shellsort с пробелами 23, 10, 4, 1 в действии .

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

HTML-код:

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

Код JavaScript:

function shellSort(arr) {
    var increment = arr.length / 2;
    while (increment > 0) {
        for (i = increment; i < arr.length; i++) {
            var j = i;
            var temp = arr[i];
    
            while (j >= increment && arr[j-increment] > temp) {
                arr[j] = arr[j-increment];
                j = j - increment;
            }
    
            arr[j] = temp;
        }
    
        if (increment == 2) {
            increment = 1;
        } else {
            increment = parseInt(increment*5 / 11);
        }
    }
  return arr;
}
console.log(shellSort([3, 0, 2, 5, -1, 4, 1]));

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

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

Блок - схема:

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

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

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

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