Sorting algorithm code in JavaScript_javascript skills-JS Tutorial-php.cn

Sorting algorithm code in JavaScript_javascript skills

WBOY

Release： 2016-05-16 18:10:33

Original

833 people have browsed it

The data item used as the basis for sorting is called the "sorting code", which is the key code of the data element. In order to facilitate search, it is usually hoped that the data table in the computer is ordered by key code. For example, half search in ordered lists has higher search efficiency. Also, the construction process of binary sorting trees, B-trees and B-trees is a sorting process. If the key is a primary key, then for any sequence to be sorted, the result obtained after sorting is unique; if the key is a secondary key, the sorting result may not be unique. This is because data elements with the same key are In the sorting result, the positional relationship between these elements cannot be maintained as before sorting.
If a certain sorting method is used for any sequence of data elements, it is sorted by key: If the positional relationship between elements with the same key is consistent before and after sorting, this sorting method is said to be stable ;A sorting method that cannot maintain consistency is called unstable.
Sort is divided into two categories: internal sorting and external sorting.
Internal sorting: refers to the sorting process in which the column to be sorted is completely stored in memory, and is suitable for element sequences that are not too large.
External sorting: refers to the need to access external memory during the sorting process. Since a large enough element sequence cannot be completely put into the memory, external sorting can only be used.

Now post the JavaScript implementation of 3 sorting algorithms.

The first is the simplest one, which is bubble sorting that everyone knows. Not much to say, just paste the code

Copy the code The code is as follows:

 
/** @name Bubble sort 
* @lastmodify 2010/07/13 
* @desc Comparison sort 
Complexity is O(n*n) 
*/ 
function BubbleSort(list){ 
var len = list.length; 
var cl,temp; 
while(len--){ 
cl = list.length ; 
while(cl--){ 
if(list[cl]>list[len] && cl < len){ 
temp = list[len]; 
list[len] = list[cl]; 
list[cl] = temp; 
} 
} 
} 
return list; 
} 

Then the last Common quick sorting is basically asked in interviews.

Copy code The code is as follows:

 
/**@name Quick sort 
* @lastmodify 2010/07/14 
* @desc Comparison sort 
 Worst running time O(n*n); 
 Best running time O(nlogn) 
*/ 
function QuickSort(list){ 
var i = 0; 
var j = list.length; 
var len = j; 
var left; 
var right; 
var k = findK (i , j); 
if(k != 0){ 
var leftArr = []; 
var rightArr = []; 
var midArr = [list[k]]; 
while(len--) { 
if(len != k){ 
if(list[len] > list[k]){ 
rightArr.push(list[len]); 
} 
else{ 
leftArr.push(list[len]); 
} 
} 
} 
left = QuickSort(leftArr); 
right = QuickSort( rightArr); 
list = left.concat(midArr).concat(right); 
} 
return list; 
} 

function findK(i,j){ 
//Find its middle position by default 
return Math.floor((i j) / 2); 
} 

The main idea of quick sort is the divide and conquer method, which will be sorted The sequence is divided into 2 blocks, thereby reducing the complexity of sorting. The clever use of recursion is also the subtlety of quick sort. In the previous example, first use the findK function to find the "reference element", and then compare other elements with this element in turn. All those larger than it are put into one set, and those smaller than it are put into another set. Sort two collections. The efficiency of quick sort mainly depends on the implementation of the findK function and the orderliness of the elements to be sorted. Therefore, quicksort is an unstable sorting algorithm.

But quick sort is still a comparison-based sorting algorithm. One characteristic of all comparison-based sorting algorithms is that no matter how optimized, the average sorting time for a set of elements always increases as the number of elements in the set increases. Non-comparative sorting overcomes this shortcoming very well. They try to make the sorting time complexity tend to a stable value independent of the number. One of the more representative ones is bucket sorting. Let’s take a look at its JavaScript implementation first.

Copy code The code is as follows:

 
/**@name bucket sorting 
* @author lebron 
* @lastmodify 2010/07/15 
* @desc non-comparative sorting 
*/ 
function BucketSort(list) { 
var len = list.length; 
var range = findMax(list); 
var result = [], 
count = []; 
var i,j; 
for (i = 0; i < range; i ) { 
count.push(0); 
} 

for ( j = 0; j < len; j ) { 
count[list[j]] ; 
result.push(0); 
} 
for ( i = 1; i < range; i ) { 
count[i] = count[i-1] count[i]; 
} 
for (j = len - 1; j >= 0; j--) { 
result[count[list[j]]] = list[j]; 
count[list[j]]--; 
} 
return result; 
} 

function findMax(list) { 
return MAX; 
} 

As you can see, in the implementation of bucket sorting, a findMax is still used function to determine the range of a large array, here it is directly replaced by a constant MAX. First initialize a large array count with a length of MAX. Put the values in the sorted set into the corresponding positions. For example, if there is an element with a value of 24, then the 24th bit of count is marked as 1, and the length of the result array is 1. Then calculate the position of the element marked with 1 in the count array and the position of the element marked with 1 in the entire count array. At this time, the value of the nth element in the count array should be its position after sorting, and n is the value corresponding to this position after sorting. Therefore, finally, map the key values in the count array one by one into the result array.
Bucket sorting cleverly uses the idea that if an element is the nth largest in a set, then it should be ranked nth, without caring about whether the previous or following element is larger than it. Is it bigger or smaller (no need to compare). Obviously, in actual situations, the range of values of the elements of the sorted set is likely to be much larger than the number of elements of the set. Therefore, a corresponding array of huge space needs to be allocated. Therefore, a common scenario for bucket sort is on outer sort.

Interested students can test the time-consuming of three kinds of sorting at different orders of magnitude.