Arrays in javaScript

What is an array

An array object uses a single variable name to store a series of values. Arrays can store all of their values with a single variable name, and can access any value with a variable name. Each element in the array has its own ID,

Create an array

• General mode:

var citys=new Array();
citys[0]="beijing";      
citys[1]="shanghai";
citys[2]="wuhan";
console.log(citys[0]); //beijing
Copy the code

• Concise way:

var citys=new Array("beijing"."shanghai"."wuhan");
console.log(citys[1]); //shanghai
Copy the code

• Literally:

var citys=["beijing"."shanghai"."wuhan"];
console.log(citys[2]); //wuhan
Copy the code

• The array.from () method creates a new, shallow-copy Array instance from an array-like or iterable.

var arr = Array.from('shenzhen'); console.log(arr); / / /"s"."h"."e"."n"."z"."h"."e"."n"]
Copy the code

Sort an array

• The sort () method

Var array = [1, 4, 8, 3,6,12,9,8];function compare(val1,val2){
    return val1-val2;
};
array.sort(compare);
Copy the code

• Reverse array ()

var citys=new Array("beijing"."shanghai"."wuhan"); console.log(citys); / / /"beijing"."shanghai"."wuhan"] citys.reverse(); console.log(citys); / / /"wuhan"."shanghai"."beijing"]
Copy the code

• Bubble sort 1. Compare two adjacent elements, and if the first element is larger than the last, switch places. 2. After the first round of comparison, the last element is the largest. 3. The last element is the largest, so the last element does not need to compare sizes.

function bubbleSort(arr) {
  var len = arr.length;
  for (var i = 0; i < len-1; i++) {
    for(var j = 0; j < len - 1 - i; J++) {// adjacent elements are compared in pairs, the elements are swapped, and the larger elements are swapped behindif(arr[j] > arr[j + 1]) { var temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; }}}returnarr; MyArr = [1, 28, 32, -9, 22]; myArr = [1, 28, 32, -9, 22]; // Use the function bubbleSort(myArr) //[-9, 1, 22, 28, 32]Copy the code

• Select sort 1, algorithm introduction order select sort is a simple and intuitive sorting method, its working principle is very simple, first never find the largest element in the sorted sequence, put the sorted sequence at the end, repeat the above steps, until all the elements sorted. 2, 1) suppose not collating sequence algorithm description of the first is a maximum, write down the element’s position, once upon a time in the future more 2) if an element is bigger than the element, the position of the cover before 3) repeat the second step, until you find not order at the end of the 4) will be the first element of the unordered elements and largest element exchange position 5) repeat the previous steps, Until everything is sorted. 3. The number of switching operations selected by algorithm analysis has been ordered 0 at best and reversed n-1 at worst, so the number of switching operations is between 0 and (n-1) times. Compare the number of operations (N-1 +… +2+1+0) is n(n-1)/2 times; Swap elements are assigned 3 times, and reverse order requires n-1 swap, so the assignment is between 0 and 3(n-1) times. It’s definitely unstable because of the need to switch places.

function selsetSort(arr){
	var len = arr.length;
	var index;
	for(var i=0; i<len-1; i++){ index=i;for(var j=i+1; j<len; j++){if(arr[index]>arr[j]){// find the minimum index=j; // Save the minimum index}}if(index!=i){
		var temp =arr[i];
		arr[i]=arr[index];
		arr[index]=temp;
	}
	}
	returnarr; } myArr =,3,6,7,9,1,23,32,11,8 [5]; SelsetSort (myArr) = selsetSort(myArr) = selsetSort(myArr)Copy the code

• The quicksort array specifies an element as a ruler, placing the larger element after it, and the smaller element in front of it, and so on until everything is in positive order. 1. Pivot: Select an element in the data structure as pivot. According to the size of the value of the base element, the unordered area is divided. All data smaller than the base element is put into one interval, and all data larger than the base element is put into another interval. After the partitioning operation, the position of the base element is the position it should be in after the final sorting. For the first two unordered intervals, the algorithm of step 1 and step 2 is recursively called until there is only one element left in all the unordered intervals.

function quickSort(arr) {
    arr = arr.concat();
    if(arr.length<=1){
        return arr
    }
    let left=[], right=[];
     letThe basis = arr. Splice (0, 1); arr.forEach(function (v) {
        if(v<basis){
            left.push(v)
        }else{
            right.push(v)
        }
    });
    returnQuickSort (left).concat(basis,quickSort(right))} myArr = [1, 28, 32, -9, 22,48,-7848,77]; // Use quickSort(myArr) // [-7848, -9, 1, 22, 28, 32, 48, 77]Copy the code

• Insert sort 1, introduction to the algorithm The working principle of insert sort is to scan the sorted data sequence from back to front to find the corresponding position and insert. Insertion sort usually takes the form of placeholder and the space complexity is O(1). Therefore, in the process of scanning from back to front, it is necessary to repeatedly move the sorted elements backward step by step to provide insertion positions for new inserted elements. 2, algorithm description 1) Start with the first element, which can be considered to have been sorted 2) fetch the next element, Scan backwards in the sorted sequence 3) until you find a position less than or equal to the element 4) move all sorted elements following that position one bit backwards 5) insert the element into that position 6) repeat steps 2 to 5

function insertSort(arr){
    var len = arr.length
    for(var i=1; i<len; i++){ var temp = arr[i] var j = i-1while(arr[j]>temp){
            arr[j+1]=arr[j]
            j--
        }
        arr[j+1]=temp
    }
    returnArr} var myArr = [5,3,2,7,8] insertSort(myArr)Copy the code

• Hill sort hill sort (Shell), also known as reduced incremental sort, is an insertion sort. It’s a more powerful version of the direct insert sort algorithm. The basic idea of Hill sort is to divide the records into gap groups by step size and sort each group of records by direct insertion sort method. As the step size gradually decreases, the group contains more and more records. When the step size value decreases to 1, the whole data is combined into a group to form a group of ordered records, and then the sorting is completed.

function shellSort(array) {
    let gap = Math.floor(array.length / 2);
    while(1 <= gap) {// Group the gap elements into a group, scan all groupsfor (let i = gap; i < array.length; i++) {
            let j = 0;
            lettemp = array[i]; // Sort the group of elements whose distance is gapfor(j = i - gap; j >= 0 && temp < array[j]; j -= gap) { array[j + gap] = array[j]; } array[j + gap] = temp; } gap = Math.floor(gap / 2); // Decrease increment}return array;
}

let arr = [98, 42, 25, 54, 15, 3, 25, 72, 41, 10, 121];
shellSort(arr);  //[3, 10, 15, 25, 25, 41, 42, 54, 72, 98, 121]
Copy the code

• (1) Split an array into two groups, A and B. The two groups continue to split until each group has only one element. (2) Gradually merge groups according to the split process. Since each group has only one element at the beginning, it can be regarded as orderly inside the group. Merging groups can be regarded as a process of merging two ordered arrays. (3) Repeat the second step for the left and right small sequence until each interval has only 1 number. First step: split the array (logN) three times; second step: split the array (logN) three times. The first disassembly into [42,20,17,13], [28,14,23,15], the second disassembly into [42,20], [17,13], [28,14, 15], and the third disassembly into [42], [20], [17], [13], [28], [14], [23], [15]; The second step: The method of merging two ordered arrays is adopted. The algorithm complexity of each step is basically close to O(N). The first merge is [20,42], [13,17], [14,28], [15,23] and the second merge is [13,17,20,42], [14,15,23,28]. The third merge is [13, 14, 15, 17, 20, 23, 28, 42]

function merge(left, right) {
  var tmp = [];
  while (left.length && right.length) {
    if (left[0] < right[0])
      tmp.push(left.shift());
    else
      tmp.push(right.shift());
  }
  return tmp.concat(left, right);
}
 
function mergeSort(a) {
  if (a.length === 1) 
    return a;
  var mid = Math.floor(a.length / 2);
  var left = a.slice(0, mid);
  var right = a.slice(mid);
  return merge(mergeSort(left), mergeSort(right));
}
var arr = [42,20,17,13,28,14,23,15]; //[13, 14, 15, 17, 20, 23, 28, 42]
Copy the code

To compare