Introduction to some common basic algorithms in JS

An algorithm is just a function that converts the input of a certain data structure into the output of a certain data structure. The internal logic of the algorithm determines how to convert.

Basic Algorithm

1. Sorting

1. Bubble sorting

//冒泡排序function bubbleSort(arr) {
  for(var i = 1, len = arr.length; i < len - 1; ++i) { 
     for(var j = 0; j <= len - i; ++j) {    
       if (arr[j] > arr[j + 1]) {     
        let temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }
}

2. Insertion sorting

//插入排序 过程就像你拿到一副扑克牌然后对它排序一样
function insertionSort(arr) {
  var n = arr.length;  
// 我们认为arr[0]已经被排序，所以i从1开始
  for (var i = 1; i < n; i++) {  
// 取出下一个新元素，在已排序的元素序列中从后向前扫描来与该新元素比较大小
    for (var j = i - 1; j >= 0; j--) {   
        if (arr[i] >= arr[j]) { // 若要从大到小排序，则将该行改为if (arr[i] <= arr[j])即可
        // 如果新元素arr[i] 大于等于 已排序的元素序列的arr[j]，
        // 则将arr[i]插入到arr[j]的下一位置，保持序列从小到大的顺序
        arr.splice(j + 1, 0, arr.splice(i, 1)[0]);       
        // 由于序列是从小到大并从后向前扫描的，所以不必再比较下标小于j的值比arr[j]小的值，退出循环
        break;  
      } else if (j === 0) {        
      // arr[j]比已排序序列的元素都要小，将它插入到序列最前面
        arr.splice(j, 0, arr.splice(i, 1)[0]);
      }
    }
  } 
   return arr;
}

When the goal is ascending sorting, the best case is that the sequence is already sorted in ascending order, then It only needs to be compared n-1 times, and the time complexity is O(n). The worst case scenario is that the sequence is originally sorted in descending order, so n(n-1)/2 times need to be compared, and the time complexity is O(n^2).

So on average, the time complexity of insertion sort is O(n^2). Obviously, the power-level time complexity means that insertion sort is not suitable for situations where there is a lot of data. Generally speaking, insertion sort is suitable for sorting small amounts of data.

3. Quick sort

//快速排序
function qSort(arr) {
  //声明并初始化左边的数组和右边的数组
  var left = [], right = [];
 //使用数组第一个元素作为基准值
  var base = arr[0];  
 //当数组长度只有1或者为空时，直接返回数组，不需要排序
  if(arr.length <= 1) return arr;  
 //进行遍历
  for(var i = 1, len = arr.length; i < len; i++) {
    if(arr[i] <= base) {    
    //如果小于基准值，push到左边的数组
      left.push(arr[i]);
    } else {    
    //如果大于基准值，push到右边的数组
      right.push(arr[i]);
    }
  }
  //递归并且合并数组元素
  return [...qSort(left), ...[base], ...qSort(right)];
    //return qSort(left).concat([base], qSort(right));}

Supplement:

In this code, we can see that this The code realizes distinguishing the left and right parts through pivot, and then recursively continues pivot sorting on the left and right parts, realizing the text description of quick sorting. In other words, there is no problem in the implementation of this algorithm.

Although this implementation is very easy to understand. However, this implementation also has room for improvement. In this implementation, we found that two arrays, left/right, are defined within the function to store temporary data. As the number of recursions increases, more and more temporary data will be defined and stored, requiring Ω(n) additional storage space.

Therefore, like many algorithm introductions, the in-place partitioning version is used to implement quick sort. Let us first introduce what an in-place partitioning algorithm is.

Description of in-place partitioning algorithm

• Pick out an element from the sequence, called "pivot" , the position of the first element of the array is used as the index.

• Traverse the array. When the array number is less than or equal to the base value, exchange the number at the index position with the number and index 1

• Exchange the base value with the current index position

After the above three steps, the base value will be centered, and the numbers on the left and right sides of the array will be smaller or larger than the base value respectively. . At this time, the sorted array can be obtained by recursively partitioning in place.

Implementation of in-place partitioning algorithm

// 交换数组元素位置
function swap(array, i, j) {
    var temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}
function partition(array, left, right) {
    var index = left;
    var pivot = array[right]; // 取最后一个数字当做基准值，这样方便遍历
    for (var i = left; i < right; i++) {
    if (array[i] <= pivot) {
        swap(array, index, i);
        index++;
     }
 }
     swap(array, right, index);
     return index;
     }

Because we need to recursively partition in-place multiple times, and at the same time, we do not want additional address space, so when implementing the partitioning algorithm There will be three parameters, namely the original array array, the starting point left of the array that needs to be traversed, and the end point of the array right that needs to be traversed.

Finally, a sorted index value is returned for the next recursion. The value corresponding to this index must be smaller than the array element on the left side of the index and larger than all the array elements on the right side.

Basically again, we can further optimize the partitioning algorithm. We found that 6d8a3792df418a19d6dad836129b9cc0 y，则返回1，这样，排序算法就不用关心具体的比较过程，而是根据比较结果直接排序。

值得注意的例子：

// 看上去正常的结果:
['Google', 'Apple', 'Microsoft'].sort(); // ['Apple', 'Google', 'Microsoft'];
// apple排在了最后:
['Google', 'apple', 'Microsoft'].sort(); // ['Google', 'Microsoft", 'apple']
// 无法理解的结果:
[10, 20, 1, 2].sort(); // [1, 10, 2, 20]

解释原因

第二个排序把apple排在了最后，是因为字符串根据ASCII码进行排序，而小写字母a的ASCII码在大写字母之后。

第三个排序结果，简单的数字排序都能错。

这是因为Array的sort()方法默认把所有元素先转换为String再排序，结果’10’排在了’2’的前面，因为字符’1’比字符’2’的ASCII码小。

因此我们把结合这个原理：

var arr = [10, 20, 1, 2];
    arr.sort(function (x, y) {    
    if (x < y) {        
        return -1;
        }    
            if (x > y) {         
               return 1;
        }        return 0;
    });   
     console.log(arr); // [1, 2, 10, 20]

上面的代码解读一下：传入x，y，如果xec6a33986ca3023cbf194a082708d99dy，返回-1，x后面排，如果x=y，无所谓谁排谁前面。

还有一个，sort()方法会直接对Array进行修改，它返回的结果仍是当前Array，一个例子：

var a1 = ['B', 'A', 'C'];var a2 = a1.sort();
    a1; // ['A', 'B', 'C']
    a2; // ['A', 'B', 'C']
    a1 === a2; // true, a1和a2是同一对象

相关免费学习推荐：js视频教程

The above is the detailed content of Introduction to some common basic algorithms in JS. For more information, please follow other related articles on the PHP Chinese website!