Preface:

Front-end time, I was relatively free at work, and I went over “Data Structure and Algorithm javascript Description”. In this period of mind engraved into a sorting algorithm method, has been in the brain whirl, lingering for a long time. The sorting algorithm looks something like this: select a base value in the array, compare that value to the rest of the array, place the larger value behind it, and place the smaller value in front of it. (a vague memory) in order to find the sentence corresponding to which sorting algorithm, will be a good sorting algorithm are knocked over, here to make a simple record.

Bubble sort:

  1. Basic Definition:

With this sorting algorithm, data values float like bubbles from one end of the array to the other. Suppose you are arranging a set of numbers in ascending order. Larger values float to the right of the array, while smaller values float to the left. This happens because the algorithm moves through the array multiple times, comparing adjacent data and swapping them when the value on the left is greater than the value on the right.

  1. Animation demo:

3. Implementation ideas:

1. Compare all adjacent elements and swap them if the first is larger than the second. 2. After a round, the last number is guaranteed to be the largest. 3. Run len-1 to complete the sorting. 4. The inner layer needs to subtract the number of outer sorted layers.Copy the code
  1. Implementation method:
Let arr =,8,3,6,2,1,8,9 [1]; let len = arr.length; // loop all elements for(let j = 0; j < len; J++) {// unsorted data inside loop for(let I = 0; i < len - j; If (arr[I] > arr[I + 1]) {if(arr[I] > arr[I + 1]) {if(arr[I] > arr[I + 1]); arr[i] = arr[i + 1]; arr[i + 1] = temp; }} console.log(' Sort of current line: ${arr} '); } console.log(arr);Copy the code
  1. Function encapsulation:
Function bubblingAsc(arr) {let len = arr.length; for (let i = 0; i <= len - 1; i++) { for (let j = 0; j <= len - 1 - i; J++) {if (arr [j] > arr [j + 1]) {let tmep = arr [j] arr [j] = arr arr [m + 1] [j + 1) = tmep}} / / console log (` ${I + ${arr} ')} return arr}Copy the code
  1. Time complexity and space complexity:
The time complexity of a loop is O(n), and the time complexity of bubble sort is O(n)*O(n) = O(n^2) because all sorts are sorted on a one-dimensional array, so the space complexity is identical to O(n).Copy the code

Selection sort

  1. Basic Definition:

Starting at the beginning of the array, compare the first element to other elements. After checking all the elements, the smallest element is placed in the first position in the array, and the algorithm continues from the second position. This process continues until you get to the penultimate position of the array, and all the data is sorted.

  1. Animation demo:

3. Implementation ideas:

1. Declare a minimum 2. Loop from left to right, assuming the current value is the minimum 3. Compare the minimum value with the other value (all other elements after it) 4. If the other value is less than the minimum, then the other value is the minimum and its index is assigned to the minimum value 5. If the minimum value is not equal to the index of the current value, the minimum value is switched with the current valueCopy the code
  1. Implementation method:
Let arr =,4,3,2,1 [5]; let len = arr.length; let min; for(let i = 0; i < len; i++) { min = i; for(let j = i + 1; j < len; j++) { if(arr[j] < arr[min]) { min = j; } } if (min ! == i) { let temp = arr[i]; arr[i] = arr[min]; arr[min] = temp; } } console.log(arr);Copy the code
  1. Function encapsulation:
function selectSort (arr) { let len = arr.length; let min; For (let I = 0; i < len; I ++) {min = I // loop from left to right, assuming the current value is the minimum for(let j = I + 1; j < len; If (arr[j] < arr[min]) {if(arr[j] < arr[min]) {if(arr[j] < arr[min]) {if(arr[j] < arr[min]) { Log (' current value :' + arr[I], 'other values :' + arr[j],' Minimum value :' + arr[min]); } // If the minimum is not equal to the index of the current value, the minimum and the current value are swapped if(min! = i) { let tmep = arr[i]; arr[i] = arr[min]; arr[min] = tmep; } } return arr }Copy the code
  1. Time complexity and space complexity:
The time complexity of a loop is O(n), and the time complexity of bubble sort is O(n)*O(n) = O(n^2) because all sorts are sorted on a one-dimensional array, so the space complexity is identical to O(n).Copy the code

Insertion sort

  1. Basic Definition:

Starting at the second position in the array, we compare it in order, and if it is larger, we take the larger number and insert it at a position less than or equal to that value.

  1. Animation demo:

3. Implementation ideas:

1. Loop from the second value; 2. If the first value is greater than the second value, the first value is inserted into the position of the second value. If the value is smaller than the second value, no operation is performed. The logic here is that if the first value is greater than or equal to the second value, the position is switched, if less than the position is unchangedCopy the code
  1. Implementation method:
Let arr =,7,1,3,2 [5]; for(let i = 1; i <= arr.length - 1; i++) { let temp = arr[i]; let j = i; while(j > 0) { if(arr[j - 1] >= temp) { arr[j] = arr[j - 1]; } else { break; } j-- } arr[j] = temp; } console.log(arr);Copy the code
  1. Function encapsulation:
function insertSort (arr) {
    let len = arr.length;
    for(let i = 1; i <= len - 1; i++) {
        let temp = arr[i];
        let j = i;
        while(j > 0) {
            if(arr[j - 1] >= temp) {
                arr[j] = arr[j - 1];
            } else {
                break;
            }
            j--
        }
        arr[j] = temp;
    }
    return arr
}
Copy the code
  1. Time complexity and space complexity:
The time complexity of a loop is O(n), and the time complexity of bubble sort is O(n)*O(n) = O(n^2) because all sorts are sorted on a one-dimensional array, so the space complexity is identical to O(n).Copy the code

Time comparison of basic sorting algorithms:

  1. Random number group;

What we need to do here is compare the time of algorithms for 10 elements, 100 elements, 1000 elements, and even 10,000 elements. Now, if you were to make an array and sort it like you did before, just writing data would be crazy. In this face of different requirements and application scenarios we must adopt different approaches to deal with, so the generation of random number group function was born.

  1. Function specific implementation :(for the time being only numeric sort test)
Function randomNumber(min, Max) {return math.floor (math.random () * (max-min) + min); Function setNumber(len) {let arr = [] for (let I = 0; i <= len - 1; i++) { arr.push(randomNumber(0, len)) } return arr }Copy the code
  1. Combine the above functions into a class:
class arraySort { constructor (len) { this.arr = this.setNumber(len) this.len = this.arr.length; } // bubblingAsc () {const timestart = new Date().gettime (); for(let i = 0; i <= this.len - 1; i++) { for(let j = 0; j <= this.len - 1 - i; J++) {// if the left value is larger than the right value, The swap places the if (this. Arr [j] > this. Arr [j + 1]) {let tmep = this. Arr [j] this. Arr [j] = this. Arr [m + 1] this. Arr = tmep} [m + 1] } // console.log(' ${I + 1} order :${this.arr} ')} const timeEnd = new Date().getTime(); // const duration = timeEnd - timestart console.log(' bubble sort: when ${this.len} elements are present, program execution duration: ${duration} ') return this.arr} // selectSort selectSort () {const timestart = new Date().gettime (); let min; For (let I = 0; i <= this.len - 1; I ++) {min = I // loop from left to right, assuming the current value is the minimum for(let j = I + 1; j <= this.len - 1; If (this.arr[j] < this.arr[min]) {if(this.arr[j] < this.arr[min]) {if(this.arr[j] < this.arr[min]) {if(this.arr[j] < this.arr[min]) { // console.log(' current value :' + this.arr[I], 'other values :' + this.arr[j],' min :' + this.arr[min]); } // Swap the minimum with the current value - essentially putting the minimum at the first position in the array, and the algorithm continues from the second position. let tmep = this.arr[i]; this.arr[i] = this.arr[min]; this.arr[min] = tmep; } const timeEnd = new Date().getTime(); // duration const duration = timeEnd - timestart console.log(' select sort: ${this.len}; ${duration} ') return this.arr} // insertSort insertSort () {const timestart = new Date().gettime (); for(let i = 1; i <= this.len - 1; i++) { let temp = this.arr[i]; // let j = I; While (j > 0) {if(this.arr[j-1] >= temp) {this.arr[j] = this.arr[j-1]; } else { break; // if the value is greater than or equal to the first value, then the position is not changed. } const timeEnd = new Date().getTime(); // duration const duration = timeEnd - timestart console.log(' Insert sort: ${this.len}; ${duration} ') return this.arr} ${duration} ') return this.arr} max) { return Math.floor(Math.random() * (max - min) + min); SetNumber (len) {let arr = [] for (let I = 0; i <= len - 1; i++) { arr.push(this.randomNumber(0, len)) } return arr } }Copy the code
  1. Test cases:

Code: 10

    let arr = new arraySort(10);
    console.log(arr.bubblingAsc())
    console.log(arr.selectSort())
    console.log(arr.insertSort())
Copy the code

Results:

Bubble sort: with 10 elements, program execution duration: 0 [0, 1, 1, 1, 3, 3, 4, 6, 7] select sort: with 10 elements, program execution duration: 0 [0, 1, 1, 1, 1, 3, 3, 4, 6, 7] Insert sort: when there are 10 elements, the program execution duration: 0 [0, 1, 1, 1, 1, 3, 3, 4, 6, 7]Copy the code

Code: 100

    let arr = new arraySort(100);
    console.log(arr.bubblingAsc())
    console.log(arr.selectSort())
    console.log(arr.insertSort())
Copy the code

Results:

Bubble sort: program execution duration: 1 when there are 100 elements Select sort: program execution duration: 0 when there are 100 elements Insert sort: program execution duration: 0 when there are 100 elementsCopy the code

Code: 1000

    let arr = new arraySort(1000);
    console.log(arr.bubblingAsc())
    console.log(arr.selectSort())
    console.log(arr.insertSort())
Copy the code

Results:

Bubble sort: when there are 1000 elements, program execution duration: 5 Select sort: when there are 1000 elements, program execution duration: 3 Insert sort: when there are 1000 elements, program execution duration: 0Copy the code

Code: 10000

    let arr = new arraySort(10000);
    console.log(arr.bubblingAsc())
    console.log(arr.selectSort())
    console.log(arr.insertSort())
Copy the code

Results:

Bubble sort: when 10000 elements, program execution duration: 202 Select sort: when 10000 elements, program execution duration: 78 Insert sort: when 10000 elements, program execution duration: 2Copy the code

To sum up: Insert sort is the fastest in basic sort with the same number of elements!

Merge sort:

  1. Basic Definition:

To combine a series of ordered subsequences into a large complete ordered sequence.

  1. Animation demo:

3. Implementation ideas:

1. Divide the array into two parts until it is recursively divided into the smallest single element; Compare the size of individual elements and sort them. 3. Merge the sorted data into an array with the sorted original dataCopy the code

4. Code implementation:

Const arr =,3,8,9,10,4,6,94,3 [1]; function mergeSort (arr) { if (arr? .length <= 1) { return arr } let mid = Math.floor(arr? .length/2); let left = arr.slice(0, mid); let rigth = arr.slice(mid); return merge(mergeSort(left), mergeSort(rigth)) } function merge(left, rigth) { let temp = []; while (left? .length && rigth? .length) { if (left[0] < rigth[0]) { temp.push(left.shift()); } else { temp.push(rigth.shift()); } } return [...temp, ...left, ...rigth] } console.log(mergeSort(arr)); // [1, 3, 3, 4, 6, 8, 9, 10, 94]Copy the code
  1. Time complexity and space complexity
Time complexity: the time complexity of recursive binary is O (logN), the time complexity of loop is O (n), and the time complexity of nesting is multiplied by O (logN)* O (n).Copy the code

Quicksort:

  1. Basic Definition:

The algorithm starts by selecting an element in the list as a reference value. Data sorting is done around the base value. Move elements in the list that are less than the reference value to the bottom of the array, and elements that are larger than the reference value to the top of the array.

  1. Animation demo:

3. Implementation ideas:

1. Set the first value of the array to the base value. If it is greater than the base value, write it to the right; if it is less than the base value, write it to the left. 2. Merge the sorted array with the reference valueCopy the code
  1. Concrete implementation:
function quickSort (list) { if (! list? .length) { return [] } let left = []; let rigth = []; let pivot = list[0]; for (let i = 1; i < list? .length; i++) { if (list[i] > pivot) { rigth.push(list[i]); } else { left.push(list[i]); } } return [...quickSort(left), pivot, ...quickSort(rigth)]; } let arr = [8,7,9,5,6,1]; console.log(quickSort(arr)); // [1, 5, 6, 7, 8, 9]Copy the code
  1. Time complexity and space complexity
Time complexity: The time complexity of recursion is O (logN), the time complexity of loop is O (n), the time complexity of nesting is multiplied by O (logN)* O (n)Copy the code

Note: The nesting level of Hill sorting is too deep and time complexity is too high to discuss

Sort (you must be working with the built-in sort method!)

  1. The sort method is used in the following scenarios:
1. Normal array sort (if it is a number sort normally, if it is a letter sort by the first letter, but if it is a Chinese character sort??) 2. Sort array objects (sort by a field in an array object)Copy the code
  1. Test case generation:

The test case should include numbers, letters, words (sorted by the first letter of the word), and array objects. (Self-test should be tested from multi-dimensional, multi-angle, multi-situation, in order to minimize the probability of bugs!)

class arraySort { constructor (len) { this.arr = this.setLetter(len) this.len = this.arr.length; } // Generate random number randomNumber(min, Max) {return math.floor (math.random () * (max-min) + min); SetNumber (len) {let arr = [] for (let I = 0; i <= len - 1; I++) {arr.push(this.randomnumber (0, len))} return arr} setLetter(len) {let letterArr = []; for (var i = 0; i < len; i++) { letterArr[i] = String.fromCharCode(this.randomNumber(65, 91)); } return letterArr; SetWord (){return ['my', 'word', 'apple']} setWord(){return ['my', 'word', 'apple']} setWord(){return [{id: 1, name: 'zhangsan'},{id: 4, name: 'lisi'}, {id: 2, name: 'wanger'}] } }Copy the code
  1. The test case
  1. digital
class arraySort { constructor (len) { this.arr = this.setNumber(len) this.len = this.arr.length; } // Generate random number randomNumber(min, Max) {return math.floor (math.random () * (max-min) + min); SetNumber (len) {let arr = [] for (let I = 0; i <= len - 1; I++) {arr.push(this.randomnumber (0, len))} return arr} setLetter(len) {let letterArr = []; for (var i = 0; i < len; i++) { letterArr[i] = String.fromCharCode(this.randomNumber(65, 91)); } return letterArr; SetWord (){return ['my', 'word', 'apple']} setWord(){return ['my', 'word', 'apple']} setWord(){return [{id: 1, name: 'zhangsan'},{id: 4, name: 'lisi'}, {id: 2, name: 'wanger'}] } sort(type = 'asc') { return this.arr.sort((a,b) => { if(type == 'asc') return a - b else if(type == 'desc') Return b - a})}} // number :(descending) let arr = new arraySort(10); console.log(arr.sort()); // [0, 0, 1, 3, 3, 5, 6, 9, 9, 9, 9]- generate random number group, each number is different // number :(descending order) console.log(arr.sort('desc')); // [9, 9, 9, 6, 5, 3, 3, 1, 0, 0]Copy the code
  1. The letter
class arraySort { constructor (len) { this.arr = this.setLetter(len) this.len = this.arr.length; } // Generate random number randomNumber(min, Max) {return math.floor (math.random () * (max-min) + min); SetNumber (len) {let arr = [] for (let I = 0; i <= len - 1; I++) {arr.push(this.randomnumber (0, len))} return arr} setLetter(len) {let letterArr = []; for (var i = 0; i < len; i++) { letterArr[i] = String.fromCharCode(this.randomNumber(65, 91)); } return letterArr; SetWord (){return ['my', 'word', 'apple']} setWord(){return ['my', 'word', 'apple']} setWord(){return [{id: 1, name: 'zhangsan'},{id: 4, name: 'lisi'}, {id: 2, name: 'wanger'}]} sort(type = 'asc') {return this.arr.sort((a,b) => {if(type = 'asc') return a-b else if(type == 'desc') return b - a})} sortLetter(type = 'asc') {return this.arr.sort((a,b) => {if(type == 'asc') return A.charcodeat (0) -b.charcodeat (0) else if(type == 'desc') return b.charcodeat (0) -a.charcodeat (0)})}} Let arr = new arraySort(10); console.log(arr.sortLetter()); / / / 'C', 'D', 'D', 'E', 'G', 'O', 'P', 'R', 'T', 'T'] - the generated random number groups, with each letter is not the same as / / letters: (descending) console. The log (arr. SortLetter (' desc ')); // ['T', 'T', 'R', 'P', 'O', 'G', 'E', 'D', 'D', 'C']Copy the code
  1. Words:
class arraySort { constructor (len) { this.arr = this.setWord() // this.len = this.arr.length; } // Generate random number randomNumber(min, Max) {return math.floor (math.random () * (max-min) + min); SetNumber (len) {let arr = [] for (let I = 0; i <= len - 1; I++) {arr.push(this.randomnumber (0, len))} return arr} setLetter(len) {let letterArr = []; for (var i = 0; i < len; i++) { letterArr[i] = String.fromCharCode(this.randomNumber(65, 91)); } return letterArr; SetWord (){return ['my', 'word', 'apple']} setWord(){return ['my', 'word', 'apple']} setWord(){return [{id: 1, name: 'zhangsan'},{id: 4, name: 'lisi'}, {id: 2, name: 'wanger'}]} sort(type = 'asc') {return this.arr.sort((a,b) => {if(type = 'asc') return a-b else if(type == SortLetter (type = 'asc') {return this.arr.sort((a,b) => {if(type ==) 'asc') return a.charCodeAt(0) - b.charCodeAt(0) else if(type == 'desc') return b.charCodeAt(0) - a.charCodeAt(0) }) } } // 标 签 : arraySort = new arraySort(); console.log(arr.sortLetter()); / / [' apple ', 'my', 'word'] / / word: (descending) console. The log (arr. SortLetter (' desc ')); // ['word', 'my', 'apple']Copy the code
  1. Array objects:
class arraySort { constructor (len) { this.arr = this.setArrObj() // this.len = this.arr.length; } // Generate random number randomNumber(min, Max) {return math.floor (math.random () * (max-min) + min); SetNumber (len) {let arr = [] for (let I = 0; i <= len - 1; I++) {arr.push(this.randomnumber (0, len))} return arr} setLetter(len) {let letterArr = []; for (var i = 0; i < len; i++) { letterArr[i] = String.fromCharCode(this.randomNumber(65, 91)); } return letterArr; SetWord (){return ['my', 'word', 'apple']} setWord(){return ['my', 'word', 'apple']} setWord(){return [{id: 1, name: 'zhangsan'},{id: 4, name: 'lisi'}, {id: 2, name: 'wanger'}]} sort(type = 'asc') {return this.arr.sort((a,b) => {if(type = 'asc') return a-b else if(type == SortLetter (type = 'asc') {return this.arr.sort((a,b) => {if(type ==) 'asc') return a.charCodeAt(0) - b.charCodeAt(0) else if(type == 'desc') return b.charCodeAt(0) - a.charCodeAt(0) }) } // SortArrObj (key,valueType = 'number', type = 'asc') { return this.arr.sort((a,b) => { if (valueType == 'number') { if(type == 'asc') return a[key] - b[key] else if(type == 'desc') return b[key] - a[key] } else if (valueType == 'word') { if(type == 'asc') return a[key].charCodeAt(0) - b[key].charCodeAt(0) else if(type == 'desc') return b[key].charCodeAt(0) - a[key].charCodeAt(0) }  }) } } let arr = new arraySort(); // // array object :(ascending by id) console.log(json.stringify (arr.sortarrobj ('id')); / / / {" id ": 1," name ":" zhangsan "}, {" id ": 2," name ":" wanger "}, {" id ": 4," name ":" lisi "}] / / / / an array of objects: Console. log(json.stringify (arr.sortarrobj ('id', 'desc')); / / / {" id ": 4," name ":" lisi "}, {" id ": 2," name ":" wanger "}, {" id ": 1," name ":" zhangsan "}] / / an array of objects: Console. log(json.stringify (arr.sortarrobj ('name', 'word')); / / / {" id ": 4," name ":" lisi "}, {" id ": 2," name ":" wanger "}, {" id ": 1," name ":" zhangsan "}] / / an array of objects: Console. log(json.stringify (arr.sortarrobj ('name', 'word', 'desc')); // [{"id":1,"name":"zhangsan"},{"id":2,"name":"wanger"},{"id":4,"name":"lisi"}]Copy the code
  1. What’s the difference between no reference and passing reference?
Let arr = [30,10,111,35,1899,50,45]; let arr = [30,10,111,35,1899,50,45]; console.log(arr.sort()); // [10, 111, 1899, 30, 35, 45, 50] console.log(arr.sort((a,b) => a - b)); // [10, 30, 35, 45, 50, 111, 1899]Copy the code
  1. What algorithm is used to implement the sort method?
The sort() method sorts the elements of an array using an in-place algorithm and returns the array. In computer science, an in place algorithm is an algorithm that does not use auxiliary data structures to transform input.Copy the code
  1. Descending implementation?
sort((a,b) => b - a)
Copy the code
  1. Does it change the original array?
Let arr =,2,8,7,3 [5]; console.log(arr.sort((a, b) => a - b)) // [2, 3, 5, 7, 8] console.log(arr) // [2, 3, 5, 7, 8]Copy the code

References:

  1. Image credit: VisualGo
  2. Javascript Description of Data Structures and Algorithms

Reservation questions:

  1. If we use sort to sort Chinese characters, what sort is it?

Postscript:

The above is the interview process and the actual project will encounter some sort of questions, here to make a record and summary, I hope to help partners in need. I am a front-end side dish chicken, has been on the way of learning, if I have any mistakes, I hope you can criticize and correct, thank you very much!