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

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

script1adsense2code

script1adsense3code

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

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

Согласно Википедии "В компьютерных науках сортировка подсчета - это алгоритм сортировки коллекции объектов по ключам, которые являются маленькими целыми числами; то есть это алгоритм целочисленной сортировки. Он работает путем подсчета количества объектов, у которых есть каждый отдельный ключ значение и использование арифметики по этим подсчетам для определения позиций каждого значения ключа в выходной последовательности. Время его выполнения линейно по количеству элементов и разности между максимальным и минимальным значениями ключа, поэтому оно подходит только для непосредственного использования в ситуациях, когда изменение в ключах не намного больше, чем количество элементов. Однако оно часто используется в качестве подпрограммы в другом алгоритме сортировки, основанном на сортировке, который может обрабатывать большие ключи более эффективно ».

Алгоритм зацикливается на элементах, вычисляя гистограмму того, сколько раз каждый ключ встречается в коллекции входных данных. Затем он выполняет вычисление суммы префикса (второй цикл по диапазону возможных ключей), чтобы определить для каждого ключа начальную позицию в выходном массиве элементов, имеющих этот ключ. Наконец, он снова зацикливается на элементах, перемещая каждый элемент в его отсортированную позицию в выходном массиве.

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

HTML-код:

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

Код JavaScript:

function countingSort(arr, min, max)
  {
    var i, z = 0, count = [];
 
    for (i = min; i <= max; i++) {
        count[i] = 0;
    }
 
    for (i=0; i < arr.length; i++) {
        count[arr[i]]++;
    }
 
    for (i = min; i <= max; i++) {
        while (count[i]-- > 0) {
            arr[z++] = i;
        }
    }
 return arr;
}
var arra = [3, 0, 2, 5, 4, 1]; 
console.log(arra.length);
console.log("Original Array Elements"); 
console.log(arra); 
console.log("Sorted Array Elements"); 
console.log(countingSort(arra, 0, 5));

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

 6
Оригинальные элементы массива
[3,0,2,5,4,1]
Сортированные элементы массива
[0,1,2,3,4,5]

Блок - схема:

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

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

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

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