This article has participated in the good article call order activity, click to see: back end, big front end double track submission, 20,000 yuan prize pool for you to challenge!

preface

The main thing about blogging is to restate knowledge, summarize knowledge, and make a deep impression.

Recently, I visited an insurance company. After a year, I went out again. Before that, I did not have much preparation.

The interviewer asked, “What about data structures and algorithms?”

To tell you the truth, I was doing pretty well a year ago. Because that will not be all postgraduate entrance examination, examination is the data structure and algorithm, many classical data structure and algorithm are skilled in the heart.

But the whole year of business, no touch, coupled with no review in advance, at the beginning of the sorting algorithm was asked, the answer process stumbled, knowledge confusion.

Programmer interview, sorting algorithm is basic fuck ah!

Today’s post is kind of a summary of sorting algorithms of its own.

Here’s what the interviewer asked in the sorting algorithm:

1. What sort algorithms do you know? And their time and space complexity?

2. Handwriting Bubble sort? Pass the second parameter to control ascending and descending?

Two Numbers exchange

Appetizer: Sorting inevitably involves swapping two numbers.

General operations: Use temporary variablestempSave the value

function swap(arr, indexA, indexB) {
  let temp;
  temp = indexA
  indexA = indexB
  indexB = temp
}
Copy the code

Deconstruct assignments based on ES6

function swap(arr, indexA, indexB) {
  [arr[indexA], arr[indexB]] = [arr[indexB], arr[indexA]];
}
Copy the code

The Bubble Sort

Bubble sort is a kind of exchange sort. The basic idea is to compare the keywords of adjacent records in pairs and exchange them if they are in reverse order until there are no records in reverse order.

Algorithm description

  1. From the beginning, the size of the two elements is compared, and the reverse order is swapped until the largest element is placed at the end.
  2. The last position has been determined, continue to compare the remaining n-1 elements, repeat the operation of step 1, the second largest element is determined;
  3. Repeat the preceding steps.

Dynamic graph demonstration

Code implementation

function bubbleSort(arr) {
  for (let i = arr.length - 1; i > 0; i--) {
    for (let j = 0; j < i; j++) {
      if (arr[j] > arr[j + 1]) {
        swap(arr, j, j + 1); }}}return arr;
}
Copy the code

Pass the second parameter to control ascending and descending?

function bubbleSort(arr, compareFunc) {
  for (let i = arr.length - 1; i > 0; i--) {
    for (let j = 0; j < i; j++) {
      if (compareFunc(arr[j], arr[j + 1) >0) {
        swap(arr, j, j + 1); }}}return arr;
}
Copy the code

Algorithm of attribute

  • stable
  • The time complexity is O(n²)
  • Space complexity O(1)

Selection Sort

Select-sort is a simple and intuitive sorting algorithm. The general idea is to find the smallest value in the data structure and place it first, then find the second smallest value and place it second, and so on

Dynamic graph demonstration

Code implementation

❌ I write the following code, a look to say that this does not conform to the principle of selection sort, selection sort is not like the code implementation, encounter two opposite order, immediately perform the exchange operation:

function selectSort(arr){
  for(let i = arr.length-1; i > 0; i--){
    for(let j = 0; j<=i; j++){if(arr[j]>arr[i]){
        [arr[j], arr[i]]= [arr[i], arr[j]]
      }
    }
  }
  return arr
}
Copy the code

✅ code: you should use a minimum index variable to remember the index of the minimum value in each traverse comparison

function selectSort(arr){
  let len = arr.length,indexMin;
  for(let i = 0; i < len - 1; i++){
    indexMin = i
    for(letj = i; j < len; j++){if(arr[indexMin] > arr[j]){
        indexMin = j
      }
    }
    [arr[i], arr[indexMin]]= [arr[indexMin],arr[i]]
  }
  return arr
}
Copy the code

Algorithm of attribute

  • unstable
  • The time complexity is O(n²)
  • Space complexity O(1)

Why is selection sort unstable?

A 90 B 90 C 80

The first sort is going to replace C with A and get CBA

The stable sorting algorithm should be CAB.

Insertion Sort

The description of Insertion Sort algorithm is a simple and intuitive sorting algorithm. It works by building an ordered sequence, and for unsorted data, it scans the sorted sequence from back to front to find the corresponding position and insert it.

Algorithm description

  • Starting with the first element, the element can be considered sorted;
  • Take the next element and scan backwards through the sequence of sorted elements;
  • If the element (sorted) is greater than the new element, move the element to the next position;
  • Repeat step 3 until you find the place where the sorted element is less than or equal to the new element;
  • After inserting the new element into that position;
  • Repeat steps 2 to 5.

Dynamic graph demonstration

Code implementation

function insertionSort(arr) {
    let len = arr.length;
    let preIndex, current;
    for (let i = 1; i < len; i++) {
        preIndex = i - 1;
        current = arr[i];
        while (preIndex >= 0 && arr[preIndex] > current) {
            arr[preIndex + 1] = arr[preIndex];
            preIndex--;
        }
        arr[preIndex + 1] = current;
    }
    return arr;
}
Copy the code

Algorithm of attribute

  • stable
  • The time complexity is O(n²)
  • Space complexity O(1)

Merge Sort

The JavaScript Array class defines a sort function (array.prototype.sort) to sort JavaScript arrays (we don’t have to implement this algorithm ourselves). ECMAScript does not define a sorting algorithm, so browser vendors can implement it themselves. For example, Mozilla Firefox uses merge sort as its implementation of Array.prototype.sort, while Chrome uses a variant of quicksort (which we’ll learn about next). — JavaScript Algorithms and Data Structures

Merge sort is a divide and conquer algorithm. The idea is to divide the original array into smaller arrays until each has only one position, and then merge the smaller arrays into larger arrays until there is only one sorted large array.

Algorithm description

  • Divide: Divide n elements into n/2 element subsequences.
  • Conquer: Sort two subsequences recursively with merge sort.
  • Combine: Combine two sorted subsequences to obtain sorted results.

Dynamic graph demonstration

Code implementation

function mergeSort(arr){
  let len = arr.length
  if(len === 1) return arr;
  let min = Math.floor(len / 2),
  left = arr.slice(0,min),
  right = arr.slice(min,len);
  return merge(mergeSort(left),mergeSort(right))
}

function merge(left,right) {
  let result = [];
  while(left.length>0 && right.length>0) {if(left[0]>=right[0]){
      result.push(right.shift());
    }else{ result.push(left.shift()); }}while(left.length){
    result.push(left.shift());
  }
  while(right.length){
    result.push(right.shift());
  }
  return result;
}
Copy the code

Algorithm of attribute

  • stable
  • Time complexity O(nlogn)
  • Space complexity O(1)

Quick sort

The basic idea of quick sort is that the records to be sorted are separated into two independent parts by one sorting. The keywords in one part of the records are smaller than those in the other part. Then the two parts of the records can be sorted to achieve the order of the whole sequence.

Algorithm description

  • First, select the middle item from the array as the pivot.
  • Create two Pointers, one on the left to the first item in the array and one on the right to the last item. We move the left pointer until we find an element that is larger than the pivot, and then we move the right pointer until we find an element that is smaller than the pivot, and then we swap them, and we repeat the process until the left pointer exceeds the right. This is going to make everything smaller than the pivot entry come before it, and everything larger than the pivot entry comes after it. This step is called the partition operation.
  • The algorithm then repeats the previous two steps for the partitioned smaller array (a subarray of values smaller than the principal and a subarray of values larger than the principal) until the array is fully sorted.

Algorithm for video

Station B found a quick arrangement through dancing video demonstration: the sorting algorithm of dancing quick sort

This dance algorithm is also a classic, and the whole series is worth watching as it is more vivid than many GIFs.

Code implementation

function quickSort(arr, left, right) {
    let len = arr.length,
        partitionIndex,
        left = typeofleft ! ='number' ? 0 : left,
        right = typeofright ! ='number' ? len - 1 : right;
 
    if (left < right) {
        partitionIndex = partition(arr, left, right);
        quickSort(arr, left, partitionIndex-1);
        quickSort(arr, partitionIndex+1, right);
    }
    return arr;
}
 
function partition(arr, left ,right) {     // Partition operation
    let pivot = left,                      // Set the pivot value.
        index = pivot + 1;
    for (var i = index; i <= right; i++) {
        if (arr[i] < arr[pivot]) {
            swap(arr, i, index);
            index++;
        }       
    }
    swap(arr, pivot, index - 1);
    return index-1;
}
Copy the code

Summary of algorithm complexity

Standing on the shoulders of giants

Seriously refer to the following articles, which are far better written than the author 👌 :

1. Elegant JavaScript sorting algorithm (ES6)

2. Top 10 Classic Sorting Algorithms (GIF demonstration)

Special note: this article is not the author of the GIF, picture resources from the article -> top ten classic sorting algorithm (GIF demonstration)