Community Learn Tools Library Leisure
search
English
Home > Web Front-end > JS Tutorial > Javascript sorting algorithm counting sort example_javascript skills

Javascript sorting algorithm counting sort example_javascript skills

WBOY
Release： 2016-05-16 16:53:07
Original
1267 people have browsed it

Counting sort is a stable sorting algorithm. Counting sort uses an additional array Count_arr, where the i-th element is the number of elements whose value is equal to i in the array Arr to be sorted. Then arrange the elements in Arr to the correct position according to the array Count_arr.
is divided into four steps:
1. Find the largest and smallest elements in the array to be sorted
2. Count the number of occurrences of each element with value i in the array and store it in the array Count_arr Item i
3. Accumulate all counts (starting from the first element in Count_arr, add each item to the previous item)
4. Traverse the original array in reverse: add each element i Place it in the Count_arr(i)th item of the new array, and subtract Count_arr(i) by 1 for each element

Example:

Copy code The code is as follows:

/**
* Counting sort is a non-comparison-based sorting algorithm,
* This algorithm was proposed by Harold H. Seward in 1954.
* Its advantage is that when sorting integers within a certain range,
* Its complexity is Ο(n k) (where k is the range of integers),
* Faster than any comparison sorting algorithm .
*
*/

function countSort(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;
}

// test

var i, arr = [];

for (i = 0; i < 100; i ) {
arr.push(Math.floor (Math.random() * (141)));
}

countSort(arr, 0, 140);
Related labels：
javascript Sorting Algorithm counting sort
source：php.cn
Previous article：JavaScript array operations (creation, element deletion, array copy)_Basic knowledge Next article：A concise summary of regular expressions in JavaScript_Basic knowledge
Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
Latest Articles by Author
Latest Issues
CSS only method to dynamically modify image src on click without using JavaScript I need to change the src of an image on mouse click using only css like img:active{}
From 2024-04-06 19:25:49
0
1
505
Scatterplot points do not maintain values ​​when zooming in d3.js This is my first time using d3.js, so please bear with me. I implemented it as pure JavaSc...
From 2024-04-06 18:16:26
0
1
403
JavaScript hover events on vendor-specific pseudo-elements I have the following htmlinput tag. $("input[type='range']::-webkit-slider-thumb"...
From 2024-04-06 15:35:24
0
1
274
Submit form without button using Javascript/Jquery I'm trying to submit a form without a button by calling a JavaScript function and executin...
From 2024-04-06 14:54:03
0
2
421
Customize the appearance of Bootstrap accordion headers using the CollapseDisplay class I want to style the card title of a panel with class collapseshow. In this example, it's t...
From 2024-04-06 12:53:11
0
1
376
Related Topics
More>
Popular Recommendations
Popular Tutorials
More>
Related Tutorials
Popular Recommendations
Latest courses
Latest Downloads
More>
Web Effects
Website Source Code
Website Materials
Front End Template