Sorting as a classic front-end interview questions, often let us factory workers helpless. But run and can not run away, escape and can not escape, simply brave face, one breath will be the so-called sorting algorithm one breath to eat through. If this article is not emphasized, it will be carried out in descending order.

Bubble sort

I bet it’s something any coder can –. After all, everyone should be able to escape the so-called Tan Ho-keung little Red Book.

Bubble sort:

  1. Compare adjacent elements, and if the former is greater than the latter (the former > the latter), the two numbers are swapped.
  2. One round of comparison. We can guarantee that the smallest number is already at the top of the array.
  3. Do n minus 1 rounds, and we’ll get the sorting result.

The code is as follows:

const arr = [29.10.19.23.33];

Array.prototype.bubbleSort = function () {
  if (this.length === 1) {
    return this;
  }
  for (let i = 0; i < this.length; i += 1) {
    for (let j = i + 1; j < this.length; j += 1) {
      if (this[i] > this[j]) {
        let temp = this[j];
        this[j] = this[i];
        this[i] = temp; }}}return this;
};
Copy the code

Selection sort

Selection sorting is a common sorting algorithm, because it is simple, so in order to ease the awkward scene in the interview, it may also be considered as an interview question. Because the performance of selection sort is not high and unstable, we do not use selection sort very often in actual production.

Code thread:

  1. For the first time, select the smallest element from the data elements to be sorted and place it at the beginning of the array.
  2. Select the smallest element from the remaining data elements to be sorted and place it after the sorted data.
  3. Repeat 2 until all elements are sorted.

Code implementation:

const arr = [29.10.19.23.33];

Array.prototype.selectionSort = function () {
  if (this.length === 1) {
    return this;
  }
  for (let i = 0; i < this.length; i++) {
    let minIdx = i;
    for (let j = i + 1; j < this.length; j++) {
      if (this[minIdx] > this[j]) { minIdx = j; }}const t = this[i];
    this[i] = this[minIdx];
    this[minIdx] = t;
  }
  return this;
};
Copy the code

Insertion sort

Insertion sort refers to starting with the second item in the array, comparing it with the previous item, and switching the positions of the two numbers if the former is greater than the latter (the former > the latter). So, in the first round, the first term is going to be the smallest number. In the second round, the second number is going to be the second smallest number.

Code thread:

  1. The array is iterated from the NTH term (init n = 1,n is the array subscript).
  2. Take the NTH term and compare it with the previous one, and swap if the former is greater than the latter (the former > the latter).
  3. Repeat 12 steps until array traversal is complete.

The code is as follows:

const arr = [29.10.19.23.33];

Array.prototype.insertSort = function () {
    for (let i = 0; i < this.length; i++) {
        const temp = this[i];
        let j = i;
        while(j > 0) {
            if (this[j-1] > this[j]) {
                this[j] = this[j-1];
                this[j-1] = temp; } j--; }}}Copy the code

Merge sort

Merge sort is a very efficient sorting algorithm. FireFox used merge sort to implement sort. We can’t afford to miss out on a little water front.

Merge sort means that recursion is divided into a number of array orderly array (only one element in the array, the array must be orderly array), and then orderly array to merge, merge, compare the head element of an array of first, if the former is greater than the latter, and pushed the latter into the res in the array, the former further push. The remaining array elements are merged until the entire array is merged. I’m going to have a sorted sorted array.

The description is abstract: we can describe it step by step. In general, there are two processes.

1. Points: Divide an array recursively into ordered arrays. Merge: create an RES array, merge the ordered array, compare the header elements of the ordered array, if the former is greater than the latter, the latter will be out of the queue, push the former to the RES array, push the former out of the queue, push to the RES array. The rest of the array is merged according to this rule. Until all the ordered arrays have been merged, an ordered array is formed.

Code implementation:

const arr = [29.10.19.23.33];

Array.prototype.mergeSort = function () {
  const rec = (arr) = > {
    if (arr.length === 1) {
      return arr;
    }
    const midPoint = Math.floor(arr.length / 2);
    const left = arr.slice(0, midPoint);
    const right = arr.slice(midPoint);
    const orderLeft = rec(left);
    const orderRight = rec(right);
    const res = [];
    while (orderLeft.length || orderRight.length) {
      if (orderLeft.length && orderRight.length) {
        res.push(
          orderLeft[0] > orderRight[0]? orderRight.shift() : orderLeft.shift() ); }else if (orderLeft.length) {
        res.push(orderLeft.shift());
      } else if(orderRight.length) { res.push(orderRight.shift()); }}return res;
  };
  return rec(this);
};

Copy the code

Quick sort

Quicksort is also one of the most efficient sorting algorithms on the front end. Chrome uses quicksort as sort. It means that you pick a reference point at random. Then I iterate through the array. Put all numbers larger than the reference point behind the reference point, and all numbers smaller than the reference point in front of the reference point. Then re-select the reference points for the preceding and trailing arrays and re-operate. An array of one length that can select a reference point.

Code thread:

  1. Partition: Select a reference point at random, you can directly specify the first element of the array as the reference point. Compares the numbers in the array to the reference point, placing all numbers greater than the reference point behind it and all numbers less than it in front of it.
  2. Recursive: Partitions subarrays recursively until the subarray length is 1.

The code is as follows:

Array.prototype.quickSort = function () {
  const rec = (arr) = > {
    if (arr.length === 1) {
      return arr;
    }

    const basePoint = arr[0];
    const left = [];
    const right = [];
    for (let i = 1; i < arr.length; i++) {
      if (arr[i] <= basePoint) {
        left.push(arr[i]);
      }
      if(arr[i] > basePoint) { right.push(arr[i]); }}const orderLeft = (left.length && rec(left)) || [];
    const orderRight = (right.length && rec(right)) || [];
    return [...orderLeft, basePoint, ...orderRight];
  };
  return rec(this);
};

Copy the code