The content of this article is to share with you the analysis of two practical js sorting algorithms, which has a certain reference value. Friends in need can refer to it
Zero: Data preparation , given array arr=[2,5,4,1,7,3,8,6,9,0];
1: Fake sort
1 Thought: Bubble sort Idea: Each time the size of two adjacent data is compared, the smaller one is ranked first. If the previous data is larger than the later one, swap the positions of the two numbers
To implement the above rules, you need to use Go to a two-layer for loop, the outer layer counts from the first number to the penultimate number, and the inner layer counts from the last number to the last number in the outer layer
2 Features: The basis of the sorting algorithm. It is simple, practical and easy to understand. The disadvantage is that it requires many comparisons and is less efficient.
3 Implementation:
var times=0; var bubbleSort=function(arr){ for(var i=0;i<arr.length-1;i++){ for(var j=i+1;j<arr.length;j++){ if(arr[i]>arr[j]){//如果前面的数据比后面的大就交换 var temp=arr[i]; arr[i]=arr[j]; arr[j]=temp; } console.log("第"+(++times)+"次排序后:"+arr); } } return arr; } console.log("The result is:"+bubbleSort(arr));
4 Efficiency: Array length 10, sorting times 45 times.
2: Quick sort
1 Idea: Quick sort idea: First find a reference point (generally the middle of the index group), then the array is divided into two parts by the reference point, and the array is divided into two parts in turn. Compare the datum point data. If it is smaller than it, place it on the left; otherwise, place it on the right.
Use an empty array on the left and right to store the compared data. Finally, the above operation is performed recursively until the array length is <=1;
2 Features: Fast and commonly used. The disadvantage is that two additional arrays need to be declared, which wastes memory space resources.
3 Implementation:
var times=0; var quickSort=function(arr){ //如果数组长度小于等于1无需判断直接返回即可 if(arr.length<=1){ return arr; } var midIndex=Math.floor(arr.length/2);//取基准点 var midIndexVal=arr.splice(midIndex,1);//取基准点的值,splice(index,1)函数可以返回数组中被删除的那个数arr[index+1] var left=[];//存放比基准点小的数组 var right=[];//存放比基准点大的数组 //遍历数组,进行判断分配 for(var i=0;i<arr.length;i++){ if(arr[i]<midIndexVal){ left.push(arr[i]);//比基准点小的放在左边数组 } else{ right.push(arr[i]);//比基准点大的放在右边数组 } console.log("第"+(++times)+"次排序后:"+arr); } //递归执行以上操作,对左右两个数组进行操作,直到数组长度为<=1; return quickSort(left).concat(midIndexVal,quickSort(right)); }; console.log(quickSort(arr));
4 Efficiency: Array length 10, sorting times 22 times.
Three: Summary
Both methods have their own advantages and disadvantages, but these two methods must be mastered as programmers, because one is the most basic and the other This is the most commonly used one and will be encountered in interviews or daily life.
Related recommendations:
#JS three major sorting algorithm implementation code
JS’s top ten classic algorithm sorting
js implements sorting algorithms (bubble, selection, insertion, binary insertion, fast, hash... .
The above is the detailed content of Analysis of two practical js sorting algorithms. For more information, please follow other related articles on the PHP Chinese website!