Selection sort

concept

Selection sort is a simple and intuitive sorting algorithm. Whatever data goes in is O (N2) time complexity. So when you use it, the smaller the data, the better. The only benefit might be that it doesn’t take up any extra memory.

Train of thought

First, find the largest (small) element in the unsorted sequence, store it in the actual position of the sorted sequence and then search for the largest (small) element in the remaining unsorted elements. Then, put it at the end of the sorted sequence and repeat the second step until all sorted elements are sorted.

Code implementation

function selectionSort(arr) {
    // Save the minimum index
    let minIndex,temp

    for (let i = 0; i < arr.length - 1; i++) {
      minIndex = i;
      // Find the minimum value from a position after I
      for (let j = i + 1; j < arr.length; j++) {
        if(arr[j]<arr[minIndex]){
          minIndex = j
        }
      }
      temp = arr[i]
      arr[i] = arr[minIndex]
      arr[minIndex] = temp
    }
    return arr
  }
  console.log(selectionSort([3.4.9.2.6.1.8.7.5]))
  console.log(selectionSort([3.2.1]))
  //[1, 2, 3, 4, 5, 6, 7, 8, 9]
  / / [1, 2, 3]
Copy the code

Insertion sort

concept

Insertion sort is a simple and intuitive sorting algorithm. Its working principle is to take the first element in the sequence as an ordered sequence, then take out the subsequent unordered elements, scan from back to front in the sorted sequence, and find the corresponding position to insert.

Train of thought

Construct the ordered sequence with the first element, scan the unordered sequence with the second to last element as the unordered sequence, take out each element and scan the ordered sequence from back to front to find the corresponding position to insert

Code implementation

function insertionSort(arr) {
    let preIndex, current
    for (let i = 1; i < arr.length; i++) {
      preIndex = i - 1
      current = arr[i]

      while (arr[preIndex] > current) {
        arr[preIndex+1] = arr[preIndex]
        preIndex--
      }
      arr[preIndex + 1] = current
    }
    return arr
  }
  console.log(insertionSort([3.4.9.2.6.1.8.7.5]))
  console.log(insertionSort([3.2.1]))
  //[1, 2, 3, 4, 5, 6, 7, 8, 9]
  / / [1, 2, 3]
Copy the code

Quick sort

concept

The basic idea of quicksort is: divide and conquer + recursion

Train of thought

A random element in the disordered sequence is used as the base point and the remaining elements are sorted recursively on the left and the right of the small and large elements

Code implementation

Left (0)-- right(len-1) to sort the elements */
 function quickSort(arr, left, right) {
    var partitionIndex,
    len = arr.length,
      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
  }
  //partition Partition function
  function partition(arr, left, right) {
    var pivot = left;
    var index = pivot + 1;//index is used to record the next sorted position
    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
  }
  function swap(arr, i, j) {
    var temp = arr[i]
    arr[i] = arr[j]
    arr[j] = temp
  }

  console.log(quickSort([3.4.9.2.6.1.8.7.5]))
  console.log(quickSort([3.2.1]))
  //(9) [1, 2, 3, 4, 5, 6, 7, 8, 9]
  / / (3) [1, 2, 3]
Copy the code

Bubble sort

concept

Bubble Sort is a simple sorting algorithm in the field of computer science. It repeatedly walks through the column of elements to be sorted, comparing two adjacent elements in turn, and swapping them if the order is wrong (from largest to smallest, Z to A). The task of visiting an element is repeated until no neighboring elements need to be swapped, that is, the element column has been sorted. The algorithm gets its name from the fact that smaller elements slowly “float” to the top of the sequence (ascending or descending) through exchange, just as bubbles of carbon dioxide in a carbonated drink eventually rise to the top.

Train of thought

Loop through the array and compare two adjacent elements. The largest element is pushed to the end of the last loop (excluding the last one) until one element is left

Code implementation

function bubbleSort(arr){
    var len = arr.length;
    for(var i = 0; i < len - 1; i++){
        for(var j = 0; j < len - 1 - i; j++){
            if(arr[j]>arr[j+1]) {var temp = arr[j+1]
                arr[j+1] = arr[j]
                arr[j] = temp
            }
        }
    }
}

console.log(bubbleSort([3.4.9.2.6.1.8.7.5]))
console.log(bubbleSort([3.2.1]))
//(9) [1, 2, 3, 4, 5, 6, 7, 8, 9]
/ / (3) [1, 2, 3]
Copy the code

Hill sorting

concept

Shell’s Sort, also known as “Diminishing Increment Sort”, is a more efficient and improved version of direct insert Sort. Hill sort is an unstable sort algorithm. The method is named after D.L.Shell, who proposed it in 1959.

Train of thought

Firstly, the whole sequence of records to be sorted is divided into several sub-sequences for direct insertion sort respectively. When the records in the whole sequence are “basically ordered”, the direct insertion sort of all records is carried out successively.

Code implementation

  function shellSort(arr) {
    var len = arr.length,
    gap = Math.floor(len / 2)
    for (gap; gap > 0; gap = Math.floor(gap / 2)) {
      for (var i = gap; i < len; i++) {
        temp = arr[i]
        for (var j = i - gap; j >= 0 && arr[j] > temp; j -= gap) {
          arr[j + gap] = arr[j]
        }
        arr[j + gap] = temp
      }
    }
    return arr
  }
  console.log(shellSort([3.4.9.2.6.1.8.7.5]))
  console.log(shellSort([3.2.1]))
  //[1, 2, 3, 4, 5, 6, 7, 8, 9]
  / / [1, 2, 3]
Copy the code

Count sorting

concept

Counting sort is a non – comparison – based sorting algorithm, which was proposed by Harold H. Seward in 1954. Its advantage is that it has the complexity of n+k (where K is the range of integers) when sorting integers in a certain range, which is faster than any comparison sorting algorithm. Of course, this is a way to sacrifice space for time, and when O(k)>O(n * log(n)), it is not as efficient as the time complexity of comparison based sorting (the theoretical lower limit of comparison based sorting is O(n * log(n)), such as merge sort, heap sort).

Train of thought

Count the number of occurrences of the element with the value I in the original array ARr, which exists in the ith position of array C

Arr [sortedIndex] = I, C(I)-1, sortedIndex+1

Code implementation

  function countingSort(arr) {
    var bucket = [];
    var sortedIndex = 0;
    for(var i = 0; i < arr.length; i++){if(! bucket[arr[i]]){ bucket[arr[i]] =0
        }
        bucket[arr[i]] ++
    }
    for(var i = 0; i < bucket.length; i++){while(bucket[i]>0){
            arr[sortedIndex++] = i
            bucket[i]--
        }
    }
    return arr
  }
  console.log(countingSort([3.4.3.4.9.2.6.1.8.7.5]))
  console.log(countingSort([3.2.1]))
  //[1, 2, 3, 3, 4, 4, 5, 6, 7, 8, 9]
  / / [1, 2, 3]
Copy the code