Detailed overview of sorting and array deduplication in js algorithm_javascript skills

In fact, it is relatively simple to implement array sorting in js using the sort method in the array:

1. Sorting

Simple implementation of array sorting

Copy code The code is as follows:

var arr = [] ;
for(var i=0;i arr.push(Math.floor(Math.random()*100))
}
arr.sort(function (a,b){
return a>b?1:-1;
})
alert(arr)

You cannot simply use the sort method. By default, sort Methods are sorted in ascii alphabetical order, not by numerical size as we think,

The sort() method can accept a method as a parameter. This method has two parameters. Represents the two array items in each sorting comparison. When sort() sorts, this parameter will be executed every time two array items are compared, and the two compared arrays

The

items are passed as arguments to this function. When the function returns a value of 1, the order of the two array items is swapped, otherwise it is not swapped.

Array sorting of algorithm

Copy code The code is as follows:

var arr = [] ;
for(var i=0;i arr.push(Math.floor(Math.random()*100))
}
//Generate a None Sorted arr array
function sort(arr,start,end){
//Array length is 1
if(start == end ){
return [arr[start]]
}else if(start == end-1){
                                                                                                                                                                                                                                                     ​ [end],arr[start]]
          }else{ l = Math.floor((start end)/2);
//Array on the left
var arrLeft = sort(arr, start,l);
//Array on the right
var arrRight = sort (arr,l 1,end);
//Return result
var result = [];
//Split the left and right arrays into two parts and compare only the first number in the array, that If the value is small, put it into the result and delete the small value. Use the shift method in the array. Once the left array or right array appears and there is no data
//result array is combined with the array with data using concat, and the result is returned
while(arrLeft.length>0 || arrRight.length>0 ){
if(arrLeft.length==0){
result = result.concat(arrRight);
break;
}else if(arrRight.length==0){
result = result.concat(arrLeft);
break;
if(arrLeft[0]                                                                                                                                                                                      length-1);//Parameter array, starting position, ending position

document.write(arr '
' arrSort);


Explanation: Array sorting mainly involves splitting the array into two until it can no longer be done. In the end, the only option is to split the array into one or two, because the length of the array is divided into odd and even numbers. Splitting When there are only one or two in the final array, sorting begins and the results are returned, and these results are compared one by one and merged. You may think why this method is so complicated. Can't you always use the first method? In fact, of course you can, but there is still the word performance in this world. When the data is tens, hundreds, hundreds, everyone's calculated results Time makes no difference. If the data is huge, hundreds of millions or billions, do we still have the confidence to use the first method? In fact, the algorithm of js is divide and conquer, dividing many problems into small ones to solve.

2. Remove duplicates from array

Easy way to remove duplication: first declare an empty array, insert the duplicate array in a for loop, and skip repeated insertions

Copy code The code is as follows:

var arr = [];
for(var i=0;i arr.push(parseInt (Math.random()*10));
}
Array.prototype.indexOf = function(n){
for(var i=0;i If(this[i] == n){
return i;
}
}
return -1;
}
function removeDup(arr){
var result = [];
for(var i=0;i if(result.indexOf(arr[i]) == -1){

result.push(arr[i]);
      }                                          />' arr2)


Algorithm array to remove duplicates

Copy code

The code is as follows:var arr = []; for(var i=0;i arr.push(parseInt(Math.random()*10));

}

Array.prototype.indexOf = function(n){
for(var i=0;i if(this[i] == n){
           return i;                                                  🎜>                                                                                                                                                                                                                               🎜> if(arr[s]==arr[e]){
return [arr[s]]
}else{
return [arr[s],arr[e]];
                                                                                 s,l);
//Right side
var arrR = removeDup(arr,l 1,e);
//Copy the result on the left first
var result = arrL;
//Loop to insert unique data into the result
for(var i=0;i if(result.indexOf(arrR[i])== -1 ) result.push(arrR[i])
}
return result; //Return result
}
var arrDup = removeDup(arr, 0, arr.length-1);
document .write(arr '
' arrDup);


Explanation: Cut the repeated array until there is only one data or two arrays left at the end, put the data on the left into the result, and skip the repeated insertion on the right without repeating the insertion. Until the loop is completed, the result can be returned